Permutation Program...

[sourishzzz1234]

Please give me a working code to print the permutation of a given no..for example if i enter the no. 1234 it will print
1234
1243
1342
1324
1423
1432
and so on... till
it will print 24 possible permutations...
like this i can enter any number of any digit(max 6)... and the output will be it's all possible permutations...
Thanks in advance...
Please help me as this may come in my exams...

 

[Pathik]

In case of 4 digit nos, it ll show 24 permutations. Not 16.

 

[sourishzzz1234]

In case of 4 digit nos, it ll show 24 permutations. Not 16.

Ya sorry......i corrected it....but please give me the code.....

 

[Sykora]

A search for "generating permutations" gives you more than you'll ever need.

 

[dheeraj_kumar]

Its all loops... for a simple program, no. of digits to generate = no. of loops. Hope you get it.

 

[subratabera]

Try this...

#include<stdio.h>
#define ARRSIZE 3

int main()
{
int i,j,k;
char arr[ARRSIZE]="123";

for (i = 0; i < ARRSIZE; i++)
{
for (j = 0; j < ARRSIZE; j++)
{
for (k = 0; k < ARRSIZE; k++)
{
printf("%d %d %d\n",i,j,k);
if (i != j && i != k && j != k)
{
printf("%c%c%c",arr,arr[j],arr[k]);
printf("\n");
}
}
}
}
}

Change according to your requirements.

 

[QwertyManiac]

subratabera - What kind of an approach is that? Its so silly that you do so many loops just for the sake of displaying 3! = 6 numbers.

dheeraj_kumar - Nope, just one loop is more than enough. You can do it without a loop too.

Follow one of the standard algorithms, its just a 2-3 liner than this long 'thing' you've written which wont work for anything but ARRSIZE of 3.

Sykora's already given the tip to find some of the good permutation algorithms and it wasn't a "JFGI" point.

 

[subratabera]

Well this is just another approach for solving a problem. I will appreciate your comment if you give me an actual example (2-3 liner). Also you can change the program easily to work with larger arrays (e.g. ARRSIZE 30).

I repeat, please support your answer with an example...

 

[QwertyManiac]

Well, all you had to do was learn at Wiki or even other places far better.

A fully running C++ program for "1234":

#include <iostream>
#include <string>

using namespace std;

int fact(int n, int f=1)
{
    while (n>0)
        f*=n--;
    return f;
}

string permutation(string s, int n)
{
    if(s.size()<2) return s;
    [I]int quot = n/fact(s.size()-1); n = n % fact(s.size()-1);
    return s[quot] + permutation(s.substr(0,quot)+s.substr(quot+1),n);[/I]
}

int main()
{
    string s="1234";
    cout<<"Lexicographic permutation"<<endl<<endl;
    for (int i=0; i<fact(s.size()); i++)
    {
        cout<<"No. "<<i+1<<" Permutation is: "<<permutation(s,i)<<endl;
    }        
    return 0;
}

Using strings in C++ is easier, thus the preference of it over C. If you want me to prove it in C itself, hit me with it again.

P.s. Just changing ARRSIZE would work, you really think so? What about your strong check for a!=b!=c thing, it'd increase with increase in loops which would change each time with change in amount of digits as well. It works for what he's exampled above, but apart from that it doesn't satisfy a thing.

 

[fun2sh]

wel there r three approaches.
1.lexicographic
2.johnson trotter
3.bottom up minimal change algorithm.

search abt these and u wil get good explanation.
i m not in mood to do the prog. but lexicographic is easiest to implement

 

[QwertyManiac]

Non-lexicographic is the easiest really.

 

[Sykora]

There is a next_permutation function in the C++ STL algorithms header. just start off with the lowest lexicographical permutation (all digits sorted in ascending order) and call that n! times.

 

[subratabera]

P.s. Just changing ARRSIZE would work, you really think so? What about your strong check for a!=b!=c thing, it'd increase with increase in loops which would change each time with change in amount of digits as well. It works for what he's exampled above, but apart from that it doesn't satisfy a thing.

Anyone who modify the AARSIZE must also modify the other variables/things also. That's just a common sense. Is'nt it? By the way, I agree that your code is far better than mine. Thanks for that.

 

[Sykora]

Anyone who modify the AARSIZE must also modify the other variables/things also. That's just a common sense.

Changing ARRSIZE to 30 will require you to make up to 30 loops. That doesn't fit under common sense nor "modified easily" Brute force solutions are never extensible.

 

[subratabera]

Ya, you are right. I need to think seriously about my C skills... .

Thanks.

 

[dheeraj_kumar]

@Querty_Maniac

Nice code there, and I agree with subratabera, I need to seriously brush up my c/c++ skills.

 

[QwertyManiac]

There is a next_permutation function in the C++ STL algorithms header. just start off with the lowest lexicographical permutation (all digits sorted in ascending order) and call that n! times.

Cool, I didn't know that! (Never used STL so much really)

Well this looks far far easy now:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int a[] = {1,2,3,4};
    do
    {
        cout<<a[0]<<a[1]<<a[2]<<a[3]<<endl;
    } while (next_permutation(a,a+4));
    
    return 0;
}