Chinaunix

标题: 输出比给定排列更大的所有排列(相当于STL算法 net_permutation的实现) [打印本页]

---

作者: djkpengjun    时间: 2009-12-12 20:14
标题: 输出比给定排列更大的所有排列(相当于STL算法 net_permutation的实现)

例如排列112253321的下一个稍大的排列是112312235。
也就是说，任给一个排列，我可以找到一个比它稍大的排列，因此只要给我最小的那个排列（对本例来说即111222335）,则我可以依次找出所有排列。
(注：由112253321计算出112312235的算法是：
先从右往左找，后五个数一直都上升，直到2处首次下降。
将2与后面比其稍大的数3互换得到112353221
然后将后五个数倒序即得到112312235.)




/*输出给排列及更大的所有排列*/
#include
#define N 5
print(int a[])//打印排列
{   
for(int z=0;z=0;i--)//从后往前走
{
  if(a右一直升
{
  return false;//返回false说明没有下一个了
}
int remberi=i;//把i值记录下来
for(j=N-1;j>=remberi+1;j--)//在N-1至remberi+1段上从左往右走
{
  if(a[j]>a[remberi])
   break;
}//找到第一个大于a[remberi]的数a[j]
//交换a[j]与a[remberi]
int temp=a[remberi];
a[remberi]=a[j];
a[j]=temp;
remberi++;//remberi前是一步
//将前当remberi至N-1段反序
for(k=1;k
main()
{
int a[N];
cout>a[z];
print(a);
int count=1;
while(nextlin(a)!=false)
{
  print(a);
  count++;
}
cout
}

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/104733/showart_2119450.html

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2