0

我需要一种算法或伪代码来生成排列。假设，我得到了两个数字，分别表示字母的数量和排列的数量。

我必须写出 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;
}
4

4 回答 4

8

看std::next_permutation功能

于 2012-07-20T19:32:36.190 回答
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);
    }
}
于 2012-07-21T13:02:37.300 回答
1

你可以试试这个。我用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;
 }
于 2012-07-20T21:04:41.740 回答
0 
#include <algorithm>
#include <iostream>
#include <ostream>
#include <vector>
#include <iterator>

using namespace std;

vector<int> n2pat(int n, int len){
    vector<int> v;

    for(int i=1;i<=len;++i){
        v.push_back(n % i);
        n /= i;
    }
    reverse(v.begin(), v.end());
    return v;
}

template<typename T>
vector<T> pat2perm(vector<T> v, vector<int> &pat){
    vector<T> perm;
    for(vector<int>::const_iterator i=pat.begin();i!=pat.end();++i){
        perm.push_back(v[*i]);
        v.erase(v.begin()+ *i);
    }
    return perm;
}

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

template<typename T>
void permute(vector<T> &v, int k){
    int size=v.size();
    for(int c=0;c<k;++c){
        vector<int> pat = n2pat(c, size);
        vector<T> perm = pat2perm(v, pat);
        print<T>(perm);
    }
}

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);
    }
}
于 2012-07-21T17:00:29.933 回答