不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

小弟写的关于排列的程序，望高手给予指点。谢谢

楼主next163（U鱼）2006-12-02 10:34:39 在 C/C++ / C++ 语言提问

#include <cstdlib>
#include <iostream>
const char num[]={'A','B','C','D','E','A','B','C','D','E'};
int flag=0;
using namespace std;
void display( int no[])
{
int *so=new int[5];
int m;
int *bu=new int[4];
bu[0]=no[0];
for(m=1;m<4;m++)
{
bu[m]=bu[m-1]+no[m];//用步长算出剩余4个元素在数组中的位置
if(bu[m]>=5)
bu[m]-=5;//防止越界
}
for(m=0;m<5;m++)//输出
{
so[0]=static_cast<char>(m+65);
for(int n=1;n<5;n++)
so[n]=num[bu[n-1]+m];//
for(int c=0;c<5;c++)
cout<<static_cast<char>(so[c])<<' ';
cout<<endl;
flag++;
}
delete[] bu;
delete[] so;
}
bool check(const int no[])//检测步长
{
for(int size=1;size<4;size++)
for(int hi=0;hi+size<4;hi++)
{ int so=0;
for(int c=0;c<=size;c++)
so+=no[c+hi];
if(so%5==0)
return false;
}
return true;
}
int main(int argc, char *argv[])
{
int *high=new int[4];
for(int a=1;a<=4;a++)
{
high[0]=a;
for(int b=1;b<=4;b++)
{
high[1]=b;
for(int c=1;c<=4;c++)
{
high[2]=c;
for(int d=1;d<=4;d++)
{
high[3]=d;//四个for循环生成步长数组
if(check(high))
{
display(high);
}
else
continue;
}
}
}
}
delete[] high;
cout<<flag;//输出总共的排列方式。
system("pause");
return 0;
}
这个程序输出的是ABCDE的120种排列方式。可惜太低效了，希望高手能简化改进。
问题点数：40、回复次数：15Top

1 楼expter（Give to dream of a new height，My2007！）回复于 2006-12-02 10:42:15 得分 10

用递归...
template <class T>
inline void Swap(T& a,T& b)
{
T temp=a;
a=b;
b=temp;
}

template <class T>
void Permutation(T list[],int k,int n) //全排列函数
{
int i;
if(k==n-1)
{
for(i=0;i<n;i++)
{
cout<<list[i];
}
cout<<endl;
}
else
{
for(i=k;i<n;i++)
{
Swap(list[k],list[i]);
Permutation(list,k+1,n);
Swap(list[k],list[i]);
}
}
}
Top

2 楼wellsnow2002（IT·汽车）回复于 2006-12-02 10:45:37 得分 0

递归就不慢吗？Top

3 楼next163（U鱼）回复于 2006-12-02 10:50:30 得分 0

k和n是啥意思了？Top

4 楼chary8088（天使鱼儿）回复于 2006-12-02 10:54:35 得分 0

用分组算法Top

5 楼next163（U鱼）回复于 2006-12-02 10:56:22 得分 0

麻烦ls写出代码，谢谢，我是C++新手Top

6 楼next163（U鱼）回复于 2006-12-02 11:10:43 得分 0

再没人管我，就又沉底了。55555555555555555Top

7 楼OOPhaisky（异化$渴望成功~~）回复于 2006-12-02 11:52:37 得分 10

如果要求某一个区间[first, last)的下一个排列，思路如下：
首先，从最尾端开始往前寻找两个相邻元素，令第一个元素为i，第二个元素为ii，且满足i<ii，。找到这样一组相邻元素之后，再从最尾端开始往前检查，找出第一个大于i的元素,另它为j，将i，j元素对调，再将ii之后的所有元素颠倒排列。此即所求职下一个排列组合。Top

8 楼lyy1089（月落无痕）回复于 2006-12-02 12:02:45 得分 0

先帮你顶上。Top

9 楼next163（U鱼）回复于 2006-12-02 12:06:00 得分 0

不太明白
OOPhaisky(异化$渴望成功~~)
所说的。
Top

10 楼DonaldKnuth（克努特）回复于 2006-12-02 12:15:41 得分 10

考察一般的全排列问题,假定N个元素本身是有序的(可以有相同的元素),在N个元素组成
的所有排列中,必有一个"最小"的排列,即N个元素从小到大的排列;也必有一个"最大"的排列
,即N个元素从大到小的排列;所有的排列根据字典序可以按由"小"到"大"构成一个队列,任意
一个排列都有唯一的后继,只有"最大"的排列除外。
不难发现,从一个排列求出其后继排列,可由以下步骤完成
(1)从排列的末尾开始,逐步向前搜索,直到找到比其后面相邻的数小的数:(如果未找到
,表明不再有下一个排列,程序终止);
(2)从该数后面的回溯序列中寻找比该数大的最小的数来替换它(使用交换);
(3)将余下的数从小到大排列:因回溯序列从后往前从小到大排列,将其反转即可。
测试程序如下
//test.cpp
#include <iostream>

//pa为指向生成排列的数组，注意是按从小到达顺序排列的有序数组
template<typename T>
void arrange(T * pa, int size)
{
while(1)
{
//将每一次生成的排列显示出来
for(int m=0; m < size; ++m)
std::cout<<pa[m]<<" ";
std::cout<<'\n';

int i = size-1;
//从排列的末尾开始,逐步向前搜索
//找到第一个前面的数比后面的数小的数
for( ; (i > 0) && (pa[i-1] > pa[i]); --i);
if( i-- == 0)
break;
int j = size -1;
//从该数后面的回溯序列中寻找比该数大的最小的数来替换它
for( ; pa[i] >= pa[j]; --j);
std::swap<T>(pa[i], pa[j]);
//将余下的数从小到大排列:因回溯序列从后往前从小到大排列
for(i++,j=size-1; i<j; ++i, --j)
std::swap<T>(pa[i], pa[j]);
}
}

void main()
{
int a[] = {1, 2, 3, 4, 5};
arrange<int>(a, sizeof(a)/sizeof(int)); //生成整型元素的排列

char carray[] = {'a', 'b', 'c', 'd', 'e'};
arrange<char>(carray, sizeof(carray));
}
Top

11 楼next163（U鱼）回复于 2006-12-02 12:31:55 得分 0

up
ls的有意思。Top

12 楼Benjaminzbj（）回复于 2006-12-02 13:31:09 得分 0

C++
包涵个algorithm
自己去找函数吧Top

13 楼longjing_g（龙睛）回复于 2006-12-02 17:06:49 得分 10

递归
//n个数的数组p[n]
for(int j=1;j<=n;j++)
{
p[j] = 0;
}
perm(n);

void perm(m)
{
if(m==0)
//输出排列p[1...n]
else
{
for(int j=1;j<=n;j++)
{ if(p[j]==0)
{
p[j] = m;
perm(m-1);
p[j] = 0;
}
}
}
}Top

14 楼longjing_g（龙睛）回复于 2006-12-02 17:10:43 得分 0

for(int j=1;j<=n;j++)
{ if(p[j]==0)
{
p[j] = m;
！！！！这里要改成 p[j] = //原数组第m个数相应的值

perm(m-1);
p[j] = 0;
}
那个是用来生成1-n的数写的！Top

15 楼next163（U鱼）回复于 2006-12-06 10:48:33 得分 0

有时候我们是否想的过多了？
这是我一个为过二级C还要伤脑筋的同学用C写的。
main()
{
char c[5]={'a','b','c','d','e'};
int i,j,k,l,m;
int flag=0;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
for(k=0;k<5;k++)
for(l=0;l<5;l++)
for(m=0;m<5;m++)
{
if(i!=j&&i!=k&&i!=l&&i!=m&&j!=k&&j!=l&&j!=m&&k!=l&&k!=m&&l!=m)
{
printf("%c%c%c%c%c\n",c[i],c[j],c[k],c[l],c[m]);
flag++;
}
}
printf("\n%d",flag);
getchar();
}Top