next_permutation与使用
现在有一道很简单的题目,那就是输出1——n的所有排列数!
比如说,输入n=5;那么要求求出1,2,3,4,5这几个数所有的排列数!
c++中有一个next_permutation函数,它包含在algorithm头文件中,可以方便的求出所有的排列
数,可是你知道它是怎么实现的么?
对那个函数进行了简单的模拟,模拟函数如下:
- /**************************
- 输出所有排列数的非递归算法,经过演算测试,可行!
- 模拟next_permutation函数!
- 说简单一点,用 1,2,3,4 可以得到:
- 原排列中间转换值
- 1,2,3,43,2,1((3 * (3) + 2) * (2) + 1) * (1) = 23
- 1,2,4,33,2,0((3 * (3) + 2) * (2) + 0) * (1) = 22
- 1,3,2,43,1,1((3 * (3) + 1) * (2) + 1) * (1) = 21
- 1,3,4,23,1,0((3 * (3) + 1) * (2) + 0) * (1) = 20
- 1,4,3,23,0,1((3 * (3) + 0) * (2) + 1) * (1) = 19
- ...
- ...
- ...
- 4,3,2,10,0,0((0 * (3) + 0) * (2) + 0) * (1) = 0
- 上面的中间转换指的是:每一个数字后面比当前位数字大的数字的个数。比如:
- 1,3,4,2中,1 后面有(3, 4, 2) 他们都大于1,所以第一位是 3
- 3 后面有(4, 2), 但只有4大于3,所以第二位是 1
- 4 后面有(2), 没有比4 大的,所以第三位是 0
- 最后一位后面肯定没有更大的,所以省略了一个0。
- 经过这种转换以后,就得到了一种表示方式(中间转换),这种表达方式和原排列一一对应,可以相互转化。
- 仔细观察这种中间表达方式,发现它的第一位只能是(0,1,2,3),第二位只能是(0,1,2),第三位只能是(0,1)。
- 通常,数字是用十进制表示的,计算机中用二进制,但是现在,我用一种特殊的进制来表示数:
- 第一位用1进制,第二位用2进制。。。
- 于是就得到了这种中间表示方式的十进制值。如:
- 阶
- |||
- 1,1,0---->((1 * (3) + 1) * (2) + 0) * (1) = 8
- 3,1,0---->((3 * (3) + 1) * (2) + 0) * (1) = 20
- 这样,就可以得到一个十进制数和一个排列之间的一一对应的关系。
- 现在排列数和有序的十进制数有了一一对应的关系(通过改变对应关系,可以使十进制数升序)。
- 到这里已经可以很容易的得到任意一个排列了;
- 按照上面的对应关系,一共可能的取值有(最高位可取四个值,次位取3个'''')4*3*2*1=24种;
- 上面的其实只是一种形式罢了,为了便于理解设立的模型!
- **************************/
- #include
- usingnamespacestd;
- constMAX=50;
- inta[MAX];
- intpermutation(intn)//排列函数
- {
- inti,j,tmp,flag=1;
- for(i=n; i>=2 && flag/*这一点新学的,可以方便的退出多重循环*/; i--)
- if(a[i]>a[i-1])//从最后每相邻的两个进行比较,如果有前面一个比后面的小(i为较小位置,ii,为较大位置),那么此时一定存在一个排列比当前的大
- {
- for(j=n; j>=2 && flag; j--)//应该找这个较小的数的后面从最后开始比它大的第一个数
- {
- if(a[j]>a[i-1])//将它换到当前较小的位置上
- {
- tmp=a[j]; a[j]=a[i-1]; a[i-1]=tmp; flag=0/*找到了这样的数,就相当于找到了一个序列,就可以返回了*/;
- }
- }
- if(!flag)//较大数ii到最后进行逆序,即交换,这样就产生了下一个排列,原理类似于,找到下一个较大的作为开始位的数,然后将后面的数字从最小开始即升序
- {
- tmp=a[i]; a[i]=a[n]; a[n]=tmp; /*这种做法实际上是将排列的逆序数按照上面的方式加1*/
- }//当逆序数最大时,便不能再排列
- }
- if(flag)return0;
- elsereturn1;
- }
- intmain(intargc,char*argv[])
- {
- intn,i;
- while(1)
- {
- cin>>n;
- for(i=1; i<50; i++) a[i]=i;
- do
- {
- for(i=1; i<=n; i++) cout<"";
- cout<
- }while(permutation(n)); //一直产生排列,直到逆序数<按照上面的方式>(按从大到小)数为0;
- }
- return0;
- }
// next_permutation(begin(),end()+1)存在返回正数,否则返回0
// prev_permutation(begin(),end()+1)#include
#include
using namespace std;
int main()
{
int n;
int num[50];
scanf ("%d",&n);
for (int i = 1 ;
i <= n ;
i++)
{
num[i] = i;
}
do
{
for (int i = 1 ;
i <= n ;
i++)
printf ("%d%c",num[i],i == n ? '\n' : ' ');
}while(next_permutation(num+1,num+1+n));
return 0;
}
#include
#include
#include
#define MAX 100
using namespace std;
int main()
{
int length;
char str[MAX];
gets(str);
length = strlen(str);
sort(str, str + length);
puts(str);
while (next_permutation(str, str + length))
{
puts(str);
}
return 0;
}
【next_permutation与使用】
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- Docker应用:容器间通信与Mariadb数据库主从复制
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 第326天
- Shell-Bash变量与运算符
- 逻辑回归的理解与python示例
- Guava|Guava RateLimiter与限流算法
- 我和你之前距离
- CGI,FastCGI,PHP-CGI与PHP-FPM
- 原生家庭之痛与超越