排列有什么算法吗？

Question

我需要一个生成置换的算法或伪代码。假设给我两个数字，表示字母的数量和排列的数量。

我必须编写26个英文字母的所有排列。我写了一段代码，但有一个问题。问题是对于输入3和6，我的代码生成ABC、ACB、BAC、BCA、CBA、CAB。但我需要它来生成ABC、ACB、BAC、BCA、CAB、CBA。

#include<iostream>

using namespace std;

int c, K, N;

void permute(char a[], int i);
void swap(char* x, char* y);

int main(void)
{
    int t;
    char a[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    cin >> t;
    for(int i=1; i<=t; i++)
    {
        cin >> N >> K;//N denotes number of letters and K denotes number of permutations
        cout << "Case " << i <<":" << endl;
        c=0;
        permute(a,0);
    }
    return 0;
}

void permute(char* a, int i)
{ 
    if(i==N-1)
    {
        for(int j=0; j<N; j++)
            cout << a[j];
        cout << endl;
        c++++;
        return;
    }
    else
    {
        for(int j=i; j<N && c<K; j++)
        {
            swap(&a[i],&a[j]);
            permute(a,i+1);
            swap(&a[i],&a[j]);
        }
    }
    return;
}

void swap(char* x, char* y)
{
    char temp;
    temp=*x;
    *x=*y;
    *y=temp;
    return;
}

Answer 1

#include <algorithm>
#include <iostream>
#include <ostream>
#include <vector>
#include <iterator>

using namespace std;

void print(vector<char> &v){
    copy(v.begin(), v.end(), ostream_iterator<char>(cout));
    cout << endl;
}

void permute(vector<char> &v, int k){
    int c=0;
    do {
        print(v);
        ++c;
    }while(c < k && next_permutation(v.begin(), v.end()));
}

int main(){
    char a[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int t;

    cout << "Input number of trials:";
    cin >> t;
    for(int i=1; i<=t; ++i){
        int n, k;
        cout << "letter length:";
        cin >> n;
        cout << "permutation length:";
        cin >> k;
        vector<char> v(&a[0], &a[n]);
        cout << "Case " << i <<":" << endl;
        permute(v, k);
    }
}

Answer 2

你可以试试这个。我使用c编程。您可以轻松地将此代码转换为c。我的代码是：：

 #include<stdio.h>
 #include<stdlib.h>
 #include<ctype.h>

 int com(const void *a,const void *b)   {
    char c,d;
    c=*((char *)a);
    d=*((char *)b);
return (c-d);
 }

int main()   {
   char a[600];
   int i,j,l,flag=0,count=0,cs,c;
   scanf("%d",&cs);
   getchar();

   for(;cs;cs--)  {
    gets(a);
    for(l=0;a[l];l++);
    qsort(a,l,sizeof(char),com);
    puts(a);
    if(a[0]==0)
        break;
    while(1) {
        for(i=l-1;a[i]>=a[i+1]&&i;i--);
        if(a[i]>=a[i+1])
            break;
        for(j=l-1;a[i]>=a[j];j--);
        c=a[i];
        a[i]=a[j];
        a[j]=c;
        for(j=i+1,i=l-1;i>j;i--,j++)
        {
            c=a[i];
            a[i]=a[j];
            a[j]=c;
        }
        puts(a);
      }
   }
   return 0;
 }

Answer 3

查看std：：next\u permutation函数