大家都来写CODE，写得好的给高分！（一个关于全排列的程序）
看谁的CODE写得妙！
题目：写一个能打印出全排列的程序，用C或者C＋＋均可。
要求从键盘输入一个数字，如3，则可打印出以下信息：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
写得好的给高分！
问题点数：100、回复次数：33Top
1 楼fastzch（红领巾）回复于 2003-02-04 19:15:36 得分 0
难道就这么难写吗，没一个人愿意拿分？
真是惨，有分送不出呀!Top
2 楼ehom（？！）回复于 2003-02-04 20:15:28 得分 15
#include <iostream.h>
#define Num 5
int a[Num];
void exchange(int& x);
void swap(int& a, int& b);
void main()
{
int i;
int y=1;
int x;
for (i=1;i<=Num;i++)
a[i]=i;
do
{
for (i=1;i<=Num;i++)
cout<<a[i];
cout<<endl;
x=0;
y++;
exchange(x);
}while (x!=0);
}
void exchange(int& x)
{
int i;
int j;
for (i=1;i<=Num-1;i++)
if (a[i]<=a[i+1])
x=i;
if (x!=0)
{
for (i=x;i<=Num;i++)
if (a[x]<=a[i])
j=i;
swap(a[x],a[j]);
for (i=x+1;i<=Num;i++)
{
if (i!=Num+x+1-i)
swap(a[i],a[Num+x+1-i]);
if ((i+1)*2>Num+x+1)
break;
}
}
}
void swap (int& a, int& b)
{
a=a+b;
b=a-b;
a=a-b;
}Top
3 楼fiveyes（天才的剽窃如羚羊挂角无迹可寻）回复于 2003-02-04 20:44:37 得分 13
真希望这个程序是我写的……
可惜不是，是来自《数据结构算法与应用－－C++语言描述》的第一章。
程序1-10 使用递归函数生成排列
template<class T>
void Perm(T list[], int k, int m)
{ / /生成list [k：m ]的所有排列方式
int i;
if (k == m) {//输出一个排列方式
for (i = 0; i <= m; i++)
cout << list [i];
cout << endl;
}
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]);
}
}
程序1 - 11 交换两个值
template <class T>
inline void Swap(T& a, T& b)
{// 交换a和b
T temp = a; a = b; b = temp;
}Top
4 楼fiveyes（天才的剽窃如羚羊挂角无迹可寻）回复于 2003-02-04 20:47:13 得分 1
这是程序前面的一大堆分析：
例1-3 [排列] 通常我们希望检查n 个不同元素的所有排列方式以确定一个最佳的排列。比如，a，b 和c 的排列方式有：a b c, a c b, b a c, b c a, cab 和c b a。n 个元素的排列方式共有n ！种。
由于采用非递归的C + +函数来输出n 个元素的所有排列方式很困难，所以可以开发一个递归函数来实现。令E= {e1 , ..., en }表示n 个元素的集合，我们的目标是生成该集合的所有排列方式。令Ei 为E中移去元素i 以后所获得的集合，perm (X) 表示集合X 中元素的排列方式，ei . p e r m(X)表示在perm (X) 中的每个排列方式的前面均加上ei 以后所得到的排列方式。例如，如果E= {a, b, c}，那么E1= {b, c}，perm (E1 ) = ( b c, c b)，e1 .perm (E1) = (a b c, a c b)。
对于递归的基本部分，采用n = 1。当只有一个元素时，只可能产生一种排列方式，所以perm (E) = ( e)，其中e 是E 中的唯一元素。当n > 1时， perm (E) = e1 .perm (E1 ) +e2 .p e r m(E2 ) +e3.perm (E3) + . +en .perm (En )。这种递归定义形式是采用n 个perm (X) 来定义perm (E), 其中每个X 包含n- 1个元素。至此，一个完整的递归定义所需要的基本部分和递归部分都已完成。
当n= 3并且E=（a, b, c）时，按照前面的递归定义可得perm (E) =a.perm ( {b, c} ) +b.perm ( {a,c} ) +c.perm ( {a, b} )。同样，按照递归定义有perm ( {b, c} ) =b.perm ( {c} ) +c.perm ( {b}), 所以a.perm ( {b, c} ) = ab.perm ( {c} ) + ac.perm ( {b}) = a b . c + ac.b = (a b c, a c b)。同理可得b.perm ( {a, c}) = ba.perm ( {c}) + bc.perm ( {a}) = b a . c + b c . a = (b a c, b c a)，c.perm ( {a, b}) =ca.perm ( {b}) + cb.perm ( {a}) = c a . b + c b . a = (c a b, c b a)。所以perm (E) = (a b c, a c b, b a c, b c a,c a b, c b a)。
注意a.perm ( {b, c} )实际上包含两个排列方式：abc 和a c b，a 是它们的前缀， perm ( {b, c} )是它们的后缀。同样地，ac.perm ( {b}) 表示前缀为a c、后缀为perm ( {b}) 的排列方式。
程序1 - 1 0把上述perm (E) 的递归定义转变成一个C++ 函数，这段代码输出所有前缀为l i s t [ 0：k-1], 后缀为l i s t [ k：m] 的排列方式。调用Perm(list, 0, n-1) 将得到list[0: n-1] 的所有n! 个排列方式，在该调用中，k=0, m= n - 1，因此排列方式的前缀为空，后缀为list[0: n-1] 产生的所有排列方式。当k =m 时，仅有一个后缀l i s t [ m ]，因此list[0: m] 即是所要产生的输出。当k<m时，先用list[k] 与l i s t [ k：m] 中的每个元素进行交换，然后产生list[k+1: m] 的所有排列方式，并用它作为list[0: k] 的后缀。S w a p是一个inline 函数，它被用来交换两个变量的值，其定义见程序1 -11。P e r m的正确性可用归纳法来证明。Top
5 楼gladiatorcn（角斗士）回复于 2003-02-04 20:47:54 得分 0
这是一个简单的算法题Top
6 楼qhgary（Gary）回复于 2003-02-04 22:46:40 得分 12
大家看看我写的如何？
#include <iostream>
#define MAX 10
using namespace std;
bool used[MAX];//各个数字的使用情况
int number = 0; //产生的排列个数
void init(int total) //所有数字均没有使用
{
for (int i = 0;i < total;i ++){
used[i] = false;
}
}
void order(int loc,int total)
{
static int result[MAX];//保存结果用的数组
if(loc < total){
for (int i = 0;i < total;i ++){
if (used[i] == false) {
result[loc] = i+1;
used[i] = true;
order(loc+1,total);
used[i] = false;
}//if
}//for
}//if
if (loc == total-1){//如果各个数字均产生则输出结果
for (int j = 0;j < total;j ++) cout << result[j];
number ++;
cout << endl;
}//if
}
void main(void)
{
int num;
cout << "Input num:";
cin >> num;
init(num);
order(0,num);
cout << "Total number:" << number << endl;
system("Pause");
}Top
7 楼xdspower（杂食菜熊）回复于 2003-02-05 09:39:19 得分 0
如果你的题目没有最大数的限制，这个程序是没法写好的Top
8 楼sea_lover（CodePlus）回复于 2003-02-05 12:12:10 得分 0
现在无法给你，在我的电脑上有源代码！
Top
9 楼SilverChariot（丁丁在CSDN）回复于 2003-02-05 13:04:28 得分 0
gzTop
10 楼fastzch（红领巾）回复于 2003-02-08 18:34:07 得分 0
谢谢各位！来日一定多多给分（当然是写得好的才给分）。Top
11 楼Solstice（大佛）回复于 2003-02-08 18:48:36 得分 16
我也凑个热闹：
// C++
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> perm(n);
for (int i = 0; i < n; ++i)
perm[i] = i + 1;
do {
copy(perm.begin(), perm.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
} while (next_permutation(perm.begin(), perm.end()));
}
Top
12 楼fastzch（红领巾）回复于 2003-02-08 18:59:48 得分 0
上面这位仁兄写得好，看来是位高手！我一定多给分。
不知可否留下联系方式？Top
13 楼fastzch（红领巾）回复于 2003-02-08 19:15:49 得分 0
大家知道吗？我写的也有两个，不过暂且不公布。我输入个30，我的P4算了一个上午呀，唉，真是辛苦我的爱机了。Top
14 楼chujidiy（George）回复于 2003-02-08 22:37:14 得分 0
你好象是在哄小孩子哦，我的楼主啊！！！！
我知道也不想说哦！！
去！
GET LOST！Top
15 楼SilverChariot（丁丁在CSDN）回复于 2003-02-09 12:15:50 得分 0
还是用泛型算法好些。Top
16 楼jtjl（醉里挑凳看片，梦回吹牛连赢！）回复于 2003-02-09 17:26:41 得分 0
这应该是一个算法题吧
用STL来写
不是要笑死人吗
其实写全排列的关键有两个
一个是用递归
另一个是用局部静态变量
还有一个技巧是多加一个参数
来达到传递一个常量的目的
有空写一个给大家看
Top
17 楼ALNG（?）回复于 2003-02-09 17:42:29 得分 0
排序树的空编历就产生了所有的全排列。不过不是按顺序的。
搂主没有说要自己写算法， Solstice(大佛)的是有效的，这也几乎是对C++有一定了解的人的标准写法。不过还要加上输出
...
#include <iterator>
...
std::copy(perm.begin(),perm.end(),ostream_iterator<unsigned,char>(cout,' ');
std::cout<<endl;
...
这是一个阶乘复杂度的问题，不要说30，就是13都够你算的了。全世界的电脑联网来输出30的全排列都不容易啊。Top
18 楼ricetons（饭桶）回复于 2003-02-09 17:47:08 得分 3
我也来玩玩。
Pascal Version，兄弟要c的也只要改改就是。
未调试.不过应该没问题。
const n=3;
var
used:array[1..n] of boolean;
lst:array[1..n] of integer;
procedure try(dep:integer);
var
i:integer;
begin
if dep=n then begin
for i:=1 to n do write(lst[i]);
writeln;
end;
i:=1;
while not used[i] do inc(i);
lst[dep]:=i;
used[i]:=true;
try(dep+1);
used[i]:=false;
end;
begin
fillchar(used,sizeof(used),false);
fillchar(lst,sizeof(lst),0);
try(1);
end.Top
19 楼Set067（兮）回复于 2003-02-09 17:48:20 得分 0
我提供个思路，改天有空写出来。
输入数字后，顺序（倒序）建立个循环链表，在控制打印输出该数字次数后换行。Top
20 楼fastzch（红领巾）回复于 2003-02-09 21:13:00 得分 0
哦，各位，其实我觉得只要能真正贴上去代码的人都应该得高分，当然我会根据算法的优秀程序来决定给分的多少，但是大家放心，我这一百分一定会一分不留的送出去的。
至于那些只说话不写CODE的朋友，虽然他们说得天花乱坠，但不能令我们大家信服呀，所以我觉得有一句话说得真是太好了：
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊少说话，多做事！
当然我写的两个算法也会过两天放上去的，大家不要认为我是在骗小孩子！
好了，大家尽情的写吧！
Top
21 楼airdot（airdot）回复于 2003-02-10 12:28:57 得分 13
#include<stdio.h>
#define MAXNUM 9
int A,B,C,D,E,F,G,H,I;
int *pt[]={&A,&B,&C,&D,&E,&F,&G,&H,&I};
/*若要更多数位,直接改变上面三个定义就行
25位以上可用两个字母定义*/
main()
{
int i,j,t,n;
while(1){
printf("Please input again(0<n<%d):",MAXNUM);
scanf("%d",&n);
getchar();
if(n<10&&n>0) break;
else printf("\nYou input is wrong, Please input again(0<n<%d):",MAXNUM);
}/*输入数n并进行捡测*/
for(j=0;j<n;j++)
*pt[j]=j+1;/*置初始排列1,2,3,4,5,6,7,8,9 */
while(1){
for(j=0;j<n;j++)
printf("%d",*pt[j]);/*打印当前排列*/
printf("\n");
/*寻找下一个排列的交换点*/
for(j=n-1;j>0;j--)
if(*pt[j]>*pt[j-1]) break;
if(j==0) break;/*已没有更大的排列*/
for(i=n-1;i>=j;i--)/*寻找交换元素*/
if(*pt[i]>*pt[j-1]) break;
t=*pt[j-1];*pt[j-1]=*pt[i];*pt[i]=t;/*交换*/
for(i=n-1;i>j;i--,j++){/*后部分元素颠倒*/
t=*pt[j];*pt[j]=*pt[i];*pt[i]=t;
}
}
}
Top
22 楼kbsoft（让世界充满爱!）回复于 2003-02-10 13:48:32 得分 0
hehe,ALNG也来这里了Top
23 楼fangrk（加把油，伙计！）回复于 2003-02-10 13:58:52 得分 12
STL的next_permutation可以达到这个目的。
下面是我一年前些的代码，供参考：
/*初始字符串str[0,n)组成一个最小数（升序），从尾巴开始向头判断，
如果涵盖的字符串可以组成一个更大的数，则转换成最小的较大数并且
重新从尾巴向头判断。
比如1234，34可以组成更大的数字，将34变成43:1243。243可以组成比
它大的最小数324:1324。24又可以变成42:1342。342->423:1423。
23->32:1432...
*/
//BC++3.1
#include <iostream.h>
#include <string.h>
void sort(char*,char*);//排序成为升序
void display(const char*,const char*);//显示
int canGreater(const char*,const char*);
void beGreater(char*,char*);
void main()
{ char buff[10],ch;
int i,length;
cout<<"Input numbers:"<<endl;
cin>>buff;
length=strlen(buff);
sort(buff,buff+length);
cout<<"The result is:"<<endl;
display(buff,buff+length);
i=length-2;
while(canGreater(buff,buff+length)){
if(canGreater(buff+i,buff+length)){
beGreater(buff+i,buff+length);
display(buff,buff+length);
i=length-1;
}
else i--;
}
}
void sort(char*first,char*end)
{ char *p1,*p2,ch;
for(;first<end-1;first++){
ch=*first;p2=first;
for(p1=first+1;p1<end;p1++){
if(ch>*p1){
ch=*p1;
p2=p1;
}//if
}//for(p1
*p2=*first;
*first=ch;
}//for
}
void display(const char*first,const char*end)
{
for(;first<end;first++)
cout<<*first;
cout<<' ';
}
//判断[first,end)涵盖的字符串是否可以组成更大的数字
int canGreater(const char*first,const char*end)
{ const char *p;
for(p=end-1;p>first;p--)
if(*p>*(p-1)) return 1;
return 0;
}
//把[first,end)涵盖的字符串组成最小的更大数，
//其中[first+1,end)为降序
void beGreater(char*first,char*end)
{ char *p,ch=*first;
for(p=end-1;p>first;p--)
if(*p>*first)
{ ch=*p;
break;
}
*p=*first;
*first=ch;
sort(first+1,end);
}Top
24 楼xjtufans（浮云）回复于 2003-02-10 15:18:46 得分 0
Solstice(大佛)写的太好了！
Top
25 楼fastzch（红领巾）回复于 2003-02-12 21:31:20 得分 0
还有好的算法快快写来呀！Top
26 楼lbaby（春天来了...）回复于 2003-02-16 09:47:58 得分 0
学习中...Top
27 楼sea_lover（CodePlus）回复于 2003-02-16 09:53:49 得分 10
这是一个4个数的全排列。
------------Arrange.cpp-----------------
#include"Arrange.h"
#include<stdio.h>
void Print(Data *a,char N)
{
static long m=1;
printf("%ld ",m++);
for(int i=0;i<N;i++)
printf("%d ",a[i].n);
printf("\n");
}
void main()
{
Arrange a(4);
a.Run(Print);
}
--------------Arrange.h-----------------------
#ifndef Arrange_h
#define Arrange_h
struct Data
{
char n; //The Index
bool Dir; //The Direction of the exchange:false for left and true for right
char Tim; //The number the data exchanged
};
class Arrange
{
private:
char N; //The number of the data
Data *a;
char *pos;
public:
Arrange(char);
~Arrange();
void Run(void (*)(Data *,char));
};
Arrange::Arrange(char n):N(n)
{
a=new Data[n];
pos=new char[n];
for(char i=0;i<n;i++) //Init
{
a[i].n=i;
a[i].Dir=false;
a[i].Tim=i;
pos[i]=i;
}
}
Arrange::~Arrange()
{
delete []a;
delete []pos;
}
void Arrange::Run(void (*Visit)(Data *,char))
{
Visit(a,N);
while(1)
{
for(char i=1;i<N;i++) //find i
if(a[pos[i]].Tim>0) break;
if(i>=N) break;
char j;
if(a[pos[i]].Dir) //find j
{
for(j=pos[i]+1;j<N;j++)
if(a[j].n<i) break;
}
else
for(j=pos[i]-1;j>=0;j--)
if(a[j].n<i) break;
Data temp=a[pos[i]]; //exchange data
a[pos[i]]=a[j];
a[j]=temp;
char temd=pos[i]; //exchange position
pos[i]=j;
pos[a[temd].n]=temd;
if(--a[j].Tim==0) //refresh Tim and Direction
if(a[j].Dir)
a[j].Dir=false;
else
a[j].Dir=true;
for(j=1;j<i;j++) //reset Tim
a[pos[j]].Tim=j;
Visit(a,N);
}
}
#endif
------------------------------------------------------
【◇SeaLover◆〗
/ \
★---CSDN---☆
\ /
【○Trust Me●〗
Top
28 楼fastzch（红领巾）回复于 2003-02-19 22:19:07 得分 0
好的，等两天我有空了贴上我写的代码，然后就给大家散分了！Top
29 楼fastzch（红领巾）回复于 2003-03-05 23:45:32 得分 0
//今天我先贴一个简单的完全用泛型算法写的。（这样不需要什么算法知识）
/********************************
一个生成排列的程序,size为排列数大小。
Author:Zhang-Star.
*********************************/
#include<iostream>
#include<vector>
#include<algorithm>
void main(){
void mydisplay(vector<int> &vecname);
int size;
bool flag=1;
cin>>size;
vector<int> a(size);
for(int i=1;i<=size;i++) //初始化一个vector.
a[i-1]=i;
int total=0;
for(;flag;total++)
{
mydisplay(a);
flag=next_permutation(a.begin(),a.end()); //key sentence.
}
cout<<"total: "<<total<<endl;
}
void mydisplay(vector<int> &vecname)
{
for(vector<int>::iterator iter=vecname.begin();iter<vecname.end();iter++)
cout<<*iter<<' ';
cout<<endl;
}Top
30 楼rebbie（好Nick都有人用了）回复于 2003-03-06 04:16:40 得分 0
请各位大哥移步看看小弟的疑惑
http://expert.csdn.net/Expert/topic/1496/1496726.xml?temp=.6323053Top
31 楼fastzch（红领巾）回复于 2003-03-18 00:05:08 得分 0
还有没有人有CODE贴呀，不然的话我就贴上我的第二份代码，然后散分了！Top
32 楼fastzch（红领巾）回复于 2003-04-17 10:20:42 得分 0
我的第二份代码也该贴出来了，这么久了，再不贴都让人笑话了，现在也该是给大家散分的时候了！
/********************************
一个生成排列的程序,size为排列数大小。
Author:Zhang-Star.
*********************************/
#include<iostream>
#include<vector>
void swap(int *p,int *q)
{ int temp;
temp=*p;
*p=*q;
*q=temp;
}
void reverse(vector<int> & vec,int m,int n)
{
for(int i=0;i<(n-m+1)/2;i++)
swap(&vec[m+i],&vec[n-i]);
}
void mydisplay(vector<int> &vecname)
{
for(vector<int>::iterator iter=vecname.begin();iter<vecname.end();iter++)
cout<<*iter<<' ';
cout<<endl;
}
int jc(int size)
{ int m=2;
if(size==1) return 1;
if(size==2) return 2;
if(size>2)
{
for(int i=3;i<=size;i++)
m=m*i;
return m;
}
}
void main()
{
int maxj=0,maxk=0,size;
int m,total;
cin>>size;
vector<int> a(size);
//total
total=jc(size);
cout<<total<<endl;
//initializtion vector
for (int i=0;i<size;i++)
a[i]=i+1;
//display source vector .
mydisplay(a);
for(int n=1;n<total;n++)
{
maxj=0;maxk=0;
for(m=1;m<size;m++)
if(a[m-1]<a[m])
maxj=m;
for(m=0;m<size;m++)
if(a[maxj-1]<a[m])
maxk=m;
swap(&a[maxj-1],&a[maxk]);
reverse(a,maxj,size-1);
mydisplay(a);
}
} //end
Top
33 楼fzel_net（蓝色天际）回复于 2003-04-17 10:59:23 得分 5
在 清华大学出版的 那本 高级程序员 有一个很简短的程序!Top
