有排列的算法嗎？

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

看std::next_permutation功能

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

#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 4

#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); 
    } 
}