数学,数论

质数

./archives/24/

约数

./archives/89/

排列

STL:

next_permutation(): next_permutation(a+1,a+n+1); prev_permutation(): prev_permutation(a+1,a+n+1);

实现

一种消重的字符串全排列算法 在字符串全排列中，如果该字符串中存在相同的两个元素，这个字符串的全排列的个数不再是n!，所以要考虑相同元素的情况。下面的实现是利用交换的思想，递归地求解字符串的全排列算法：

void permute(char *str, int i, int n)
{
   int j;

   if (i == n)
     printf("%s\n", str);
   else{
        for (j = i; j <= n; j++){
          if(str[i] == str[j] && j != i)  continue; //为避免生成重复排列，不同位置的字符相同时不交换
          swap((str+i), (str+j));
          permute(str, i+1, n);
          swap((str+i), (str+j));
       }
   }
}

康托展开

展开: 即求这是1~n的第几个排列

#include <bits/stdc++.h>
using namespace std;

int n,ans,a[10];
char s[10];
bool tag[10];
int main(){
    cin>>n;
    scanf("%s",s+1);
    a[1]=1;
    for (int i=2;i<=n;++i) a[i]=a[i-1]*i;  //预处理阶乘
    for (int i=1;i<=n;++i){
        int t=s[i]-'0',tmp=0;
        for (int j=1;j<=n;++j){
            if (j==s[i]-'0') break;
            if (!tag[j]) tmp++; //tmp计算剩余的集合中,s[i]排第几
        }
        tag[t]=1;
        ans+=tmp*a[n-i];
    }
    cout<<ans+1;  //要加上自己
    return 0;
}

逆展开: 即求出1~n的所有排列中,第K个排列是什么

#include <bits/stdc++.h>
using namespace std;

int n,s[10],tag[10],a[10],ans;

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&s[i]);
    a[0]=1;
    for (int i=1;i<=n;++i) a[i]=a[i-1]*i;
    for (int i=1;i<=n;++i){
        int t=s[i],tmp=0;
        for (int j=1;j<=n;++j){
            if (j==s[i]) break;
            if (!tag[j]) tmp++;
        }
        tag[t]=1;
        ans+=tmp*a[n-i];
    } //映射为数值
    ans--; //求前一个
    if (ans==-1){ //如果已经是第一个
        cout<<"ERROR"<<endl;
        return 0;
    }
    memset(tag,0,sizeof(tag));
    for (int i=1;i<=n;++i){
        int t=ans/a[n-i];
        ans%=a[n-i];
        for (int j=1;j<=n;++j){
            if (t==0&&!tag[j]){
                t=j;
                break;
            }
            if (!tag[j]) t--;
        }
        tag[t]=1;
        s[i]=t;
    }
    for (int i=1;i<=n;++i) printf("%d ",s[i]); //输出序列
    return 0;
}

另一种做法:

#include <bits/stdc++.h>
using namespace std;

int n,s[10];

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&s[i]);
    if (prev_permutation(s+1,s+n+1)) for (int i=1;i<=n;++i) cout<<s[i]<<' ';
    else cout<<"ERROR"<<endl;
    return 0;
}

康托展开适合求间隔较大的两个排列,STL适合求较近的两个排列 康拓展开和逆展开可以用vector优化

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/5/