CODEWITHSUNDEEP
c++algorithmpermutation
odbhut.shei.chhele
odbhut.shei.chhele

Reputation: 6224

Is there any algorithm for permutations?

I need an algorithm or pseudo code for generating permutations. Suppose, I have been given two numbers which denote the number of letters and the number of permutations.

I have to write all the permutations from the 26 ENGLISH letter. I have written a code but there is a problem. The problem is for input 3 and 6, my code generates ABC, ACB, BAC, BCA, CBA, CAB. But I need it to generate 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;
}

Upvotes: 0

Views: 779

Answers (4)

BLUEPIXY
BLUEPIXY

Reputation: 40145

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

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

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

Upvotes: 1

sonnet
sonnet

Reputation: 21

you can try this one. I use c programming. You can easily convert this code into c++. My code is ::

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

Upvotes: 1

qehgt
qehgt

Reputation: 2990

Look at std::next_permutation function

Upvotes: 8

Related Questions