//N个数全排列的非递归算法
#include"stdio.h"
void swap(int &a, int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
/* 根据当前的排列p,计算下一个排列。
原则是从1234–>4321,若p已经是最后一个排列,传回false,否则传回true。
p是一个n维向量。 */
bool nextPermutation(int *p, int n)
{
int last=n-1;
int i,j,k;
//从后向前查找,看有没有后面的数大于前面的数的情况,若有则停在后一个数的位置。
i=last;
while(i>0&&p[i]<p[i-1])
i--;
//若没有后面的数大于前面的数的情况,说明已经到了最后一个排列,返回false。
if(i==0)
return false;
//从后查到i,查找大于p[i - 1]的最小的数,记入k
k=i;
for(j=last;j>=i;j--)
if(p[j]>p[i-1]&&p[j]<p[k])
k =j;
//交换p[k]和p[i - 1]
swap(p[k],p[i-1]);
//倒置p[last]到p[i]
for (j=last,k=i;j>k;j--,k++)
swap(p[j],p[k]);
return true;
}
//显示一个排列
void showPermutation(int *p, int n)
{
for(int i=0;i<n;i++)
printf("%d ",p[i]);
printf("\n");
}
int main(int argc,char *argv[])
{
int n;
int *p;
scanf("%d",&n);
p=new int[n];
for(int i=0;i<n;i++)
p[i]=i+1;
showPermutation(p,n);
while(nextPermutation(p,n))
{
showPermutation(p,n);
}
//delete[] p;
return 0;
}
分享到:
相关推荐
输入N,输出1-N全排列c语言算法,非递归算法................
(一)非递归全排列算法基本思想是: 1.找到所有排列中最小的一个排列P. 2.找到刚刚好比P大比其它都小的排列Q, 3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P = A1A2A3...
网易游戏笔试题算法题之一,可以用C++,Java,Python,由于Python代码量较小,于是我选择...然后再交换替换点后面的第一个数和最后一个数,即交换5,1。就得到下一个序列[2,4,1,3,5] 代码如下: def arrange(pos_in
其实排列实现了,组合也就实现了,组合C(N,R)就是P(N,R)/P(R,R) ,实现这一功能比较简单的是递归算法,但考虑到递归的性能,下面采用了2种非递归的方法,具体代码如下 using System; using System.Collections....
结合数组操作,写了个非递归的全排列生成。原理是插入法,也就是在一个有n个元素的已有排列中,后加入的元素,依次在前,中,后的每一个位置插入,生成n+1个新的全排列。因为Python切割数组或者字符串,以及合并比较...
上楼梯(非递归) 金额大小写转换 求一元二次方程的根(二分法) 数字与IP地址间的转换 八皇后问题(回溯法) 求N阶幻方 计算分数的精确值 找零钱 求一元二次方程的根(公式法) 比赛日程(分治法) 两个有序数组的合并 统计投...
| 二分图最佳匹配(KUHN MUNKRAS 算法 O(M*M*N)) 11 | 无向图最小割 O(N^3) 12 | 有上下界的最小(最大)流 12 | DINIC 最大流 O(V^2 * E) 12 | HLPP 最大流 O(V^3) 13 | 最小费用流 O(V * E * F) 13 | 最小...
7.13 递归函数的非递归求解 7.14 任意长度整数加法 第8章 数值计算问题 8.1 递推化梯形法求解定积分 8.2 求解低阶定积分 8.3 迭代法开平方运算 8.4 牛顿法解方程 8.5 欧拉方法求解微分方程 8.6 改进的欧拉方法求解...
主要内容 需要掌握的内容 字符串循环左移 LCS最长递增子序列 字符串全排列 递归、非递归 KMP Huffman编码 需要了解的内容 Manacher算法 BM算法 数据结构-字符串全文共87页,当前为第3页。 字符串循环左移 4/88 给定...
54.上楼梯(非递归) 55.金额大小写转换 56.求一元二次方程的根(二分法) 57.数字与IP地址间的转换 58.八皇后问题(回溯法) 59.求N阶幻方 60.计算分数的精确值 61.找零钱 62.求一元二次方程的根(公式法) 63.比赛日程...
54 <br>0075 用回溯法找出n个自然数中取r个数的全排列 55 <br>0076 约瑟夫环问题 56 <br>0077 猴子选大王 57 <br>0078 如何判断IP是否正确 57 <br>0079 如何将小写金额转换为大写金额 57...