全排列的递归算法_c语言吧

210.77.5.*

1楼

复习了数据结构与算法，把其中的全排列算法贴出来。

#include <stdio.h>
inline void Swap(char& a, char& b)
{// 交换a和b
    char temp = a;
    a = b;
    b = temp;
}

void Perm(char list[], int k, int m)
{ //生成list [k：m ]的所有排列方式
    int i;
    if (k == m) {//输出一个排列方式
        for (i = 0; i <= m; i++)
            putchar(list[i]);
        putchar('\n');
    }
    else // list[k：m ]有多个排列方式
        // 递归地产生这些排列方式
        for (i=k; i <= m; i++) {
            Swap (list[k], list[i]);
            Perm (list, k+1, m);
            Swap (list [k], list [i]);
        }
}

int main()
{
    char s[]="123";
    Perm(s, 0, 2);
    return 0;
}

2005-3-27 15:27
回复

202.114.117.*	2楼 hao
2005-6-30 21:25 回复

202.114.117.*	3楼 excellent!
2005-6-30 21:25 回复

221.226.224.*	4楼 hao
2005-11-14 12:48 回复

211.68.33.*	5楼重复字符的能处理吗？
2005-11-22 11:08 回复

202.114.118.*	6楼重复字符的不能处理。。。
2005-12-18 20:53 回复

202.114.118.*	7楼建议作小小修改： void Perm(char list[], int k, int m) { //生成list [k：m ]的所有排列方式 int i; static int s = k; if (k == m) {//输出一个排列方式 for (i = k; i <= m; i++) putchar(list[i]); putchar('\n'); } … }
2005-12-18 23:16 回复

210.25.133.*

8楼

上述算法输出不是按顺序的
建议改进：
算法如下：
#include <stdio.h>

#define MAX 10
int used[MAX];
int result[MAX];
int N;

void print(){
int i;
for(i = 0; i < N; i++)
printf("%d ", result[i]);
printf("\n");
}
void proc(int step){
int i;
if(step == N)
print();
else{
for(i = 0; i < N; i++){
if(!used[i]){
used[i] = 1;
result[step] = i + 1;
proc(step + 1);
used[i] = 0;
}
}
}
}

main(){
scanf("%d", &N);
proc(0);
}

不是我做的
是我的一个哥们
现在在微软亚洲研究院
北航

2006-3-1 19:32
回复

222.154.52.*	9楼强,我正在学这个算法,
2006-3-4 16:11 回复

211.158.24.*	10楼时间复杂度怎的求啊
2006-3-5 15:01 回复

childeyihong
0位粉丝

11楼

这个比楼主的麻烦

#include<iostream>
using namespace std;
int n=1;
//将i移动到j;
void move(char *str,int i,int j){
//移到后面
if(i<j){
char temp=str[i];
for(int n=i;n<j;n++)
str[n]=str[n+1];
str[j]=temp;
}
//移到前面
else{
char temp=str[i];
for(int n=i;n>j;n--)
str[n]=str[n-1];
str[j]=temp;
}
}
void perm(char *str,int k,int m){
if(k==m)cout<<str<<" "<<n++<<endl;

for(int i=m;i>=k;i--){
move(str,i,k);
perm(str,k+1,m);
move(str,k,i);
}
}

main(){
char str[]="1234567";
perm(str,0,6);
}

2006-3-6 23:25
回复

kingstarer
0位粉丝

12楼

#include <stdio.h>
int M;
void ZH(int n,int m,int s[],int total)
{ int i,j,k,flag=0;
if(m==0)
{for(i=1;i<=n;i++)
{flag=0;
for(k=M-1;k>0;k--)
if (s[k]==i) {flag++;break;}
if (flag==0)
{
s[0]=i;
for(j=0;j<M;j++)
printf("%d ",s[j]);
total++;
printf("\n");
}

}
}
else for(i=1;i<=n;i++)
{for(k=M-1;k>m;k--)
if (s[k]==i) {flag++;break;}
if (flag==0)
{
s[m]=i;
ZH(n,m-1,s,total);
}
}
}
main()
{
int s[100],n,m,total=0;
printf("input n m\n");
scanf("%d %d",&n,&m);
s[m]=0;
M=m;
ZH(n,m-1,s,total);

getchar();
getchar();

}
我写的超简单功能排序

2006-4-8 14:38
回复

luogeng2005 0位粉丝	13楼好
2006-4-17 16:37 回复

anshixinshou 0位粉丝	14楼谢谢了，正需要呢
2006-4-25 23:27 回复

DeityZ 0位粉丝	15楼 11楼都用C++了，我也来一个C++版本，调用的是STL里algorithm的库函数 #include<stdio.h> #include<algorithm> using namespace std; #define n 3 int a[n]={1,2,3}; int main() { int i; while(1) { for(i=0;i<n;i++) printf("%d ",a[i]); printf("\n"); if(!next_permutation(a,a+n)) break; } return 0; }
2006-4-25 23:38 回复

lize012345 0位粉丝	16楼晕！太难了！
2006-5-5 15:27 回复

210.25.133.*

17楼

前面贴了一个递归的全排列，现在写一个非递归的，我自己写的，呵呵
很高兴能和大家交流
#include <stdio.h>

#define MAX 10
int N;

int solution[MAX];
int used[MAX];

void pailie()
{
int i, j;
int begin = 0;
int step = 1;

while(step != 1 || begin != N)
{
for(i = begin + 1; i <= N; i++)
{
if(!used[i])
{
used[i] = 1;
solution[step++] = i;
begin = 0;
break;
}
}

if(i == N + 1)
{
begin = solution[--step];
used[begin] = 0;
}

if(step == N + 1)
{
for(j = 1; j <= N; j++)
printf("%d ", solution[j]);
printf("\n");

begin = solution[--step];
used[begin] = 0;
}

}

}

main()
{
scanf("%d", &N);
pailie();
}

北航计算机

2006-6-29 13:35
回复

59.77.16.*

18楼

//非递归全排列
//厦门大学csd03
void align(vector<int> v)
{
int amount=v.size();
vector<int> count(amount,1);
int temp,i=amount-2;

print(v); //打印
while(1)
{
while(i+count[i]>=amount)
{
count[i]=1;
i--;
if(i<0) break;
else if(count[i]!=1)
{
temp=v[i];
v[i]=v[i+count[i]-1];
v[i+count[i]-1]=temp;
}
}
if(i>=0)
{
temp=v[i];
v[i]=v[i+count[i]];
v[i+count[i]]=temp;
print(v);
count[i]++;
i++;
}
else break;
}
}

2006-9-11 14:37
回复

xiaouqun 0位粉丝	19楼高
2006-9-19 11:12 回复

211.139.151.*	20楼触动了我学英语和数学的信心!
这条留言是通过手机发表的，我也要用手机发表留言！ 2006-10-6 01:45 回复

222.18.23.*	21楼有没有输出N个元素数组的所有排列组合的算法（递归）？
2006-10-6 13:57 回复

219.239.109.*

22楼

按照

非递归实现不重复序列的全排列（三）选择自 northwolves 的 Blog

的想法，我自己写的全排列

程序太耗内存，9个全排列就搞不定了。

#include <iostream.h>
#include <windows.h>
#include "LinList.h"

void main()
{
int num;
cout<<"请输入全排列数字的个数：";
cin>>num;

int * array = new int [num];

for(int i=0; i<num; i++)
{
cout<<"please input the "<<i+1<<" resistance's value:";
cin>>array[i];
}

DWORD dwStart=GetTickCount();

int numjie=1;
for( i=1; i<=num; i++)
{
numjie*=i;
}

LinList<int> *total;
if((total = new LinList<int>[numjie]) == NULL)
{
cout<<"can't allocate more memory,terminating."<<endl;
exit(1);
}

for(i=0; i<num; i++)
{
for(int j=0; j<numjie; j++)
{
int k=j%(i+1);
total[j].Insert(array[i],k);
}
}
/* for(int j=0; j<numjie ; j++)
{
for(int i=0; i<num; i++)
{
cout<<total[j].GetData(i)<<" ";
}
cout<<endl;
}
*/
cout<<endl<<endl<<"总耗时："<<GetTickCount() - dwStart<<"毫秒"<<endl;
}

2006-10-9 23:19
回复

wzf13 0位粉丝	23楼等我学到这里的时候我再来看
2006-10-10 00:02 回复

121.69.28.*	24楼强人太多
2006-11-5 20:18 回复

58.213.38.*	25楼 15楼的能否把你的非递归实现的的思想说下啊？我看不懂啊
2006-11-8 13:01 回复

221.220.58.*

26楼

static int MAX=10;
int user[MAX];
int result[MAX];
int rp=0;
int N
void printall()
{
for ( int r=0;r<rp;rp++ ) printf("%d ",result[r]);
for ( int u=0;u<N;u++ )
if ( ! user[u] ) printf("%d ",u+1);
}
void choose(int n)
{
int nn=0;

for ( int i=0;i<=n;i++,nn++ )
while ( user[nn] ) nn++;
nn--;
user[nn]=1;
result[rp++]=nn;
}
void perm()
{
long mx=1;
int i,j;
for ( i=2;i<=N;i++ ) mx *= i;
for ( long l=0;l<mx;l++ )
{
memset(user,0,sizeof(int)*MAX);
rp=0;
for ( i=N;i>2 && l;i-- )
{
j=l%i;l=l/i;
choose(j);
}
printall();
}
}
void main(char *argv[],int argc)
{
N=10;
perm();
}

2006-11-9 14:43
回复

221.7.104.*	27楼大哥们,有空要教教小弟啊? 我初学者
2007-2-17 22:11 回复

风雨破老鼠 3位粉丝	28楼没看懂但是似乎是用冒泡法是么
2007-2-22 17:48 回复

mjl86
0位粉丝

29楼

任意字符串全排列
#include<stdio.h>
#include<string.h>
char a[20];
int lenth;
long count=0;
void main()
{void move(int,int);
int i,j=0;
printf("input:");
gets(a);
lenth=strlen(a);
for(i=0;i<lenth;i++)
move(j,i);//move a[i] to the front of a[j];
printf("\ntotal=%d\n",count);
}
void move(int here,int which)//move a[which] to the front of a[here];
{char b[20];
char temp;
int m,n;
if(here<lenth-1)
{if(here!=which)
{for(m=0;m<lenth;m++)
b[m]=a[m];
temp=a[which];
for(m=which;m>here;m--)
a[m]=a[m-1];
a[m]=temp;
}
for(n=here+1;n<lenth;n++)
move(here+1,n);
if(here!=which)
for(m=0;m<lenth;m++)
a[m]=b[m];
}
else
{printf("%-10s",a);
count++;}
}

2007-5-17 19:17
回复

221.5.224.*	30楼好难呀!
2007-6-13 21:10 回复



内　容:
用户名:
验证码:	请点击后输入验证码，加入会员后本吧发贴免验证码。

全排列的递归算法

发表回复