# Permutation Program...



## sourishzzz1234 (Apr 24, 2008)

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 (Apr 24, 2008)

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


----------



## sourishzzz1234 (Apr 24, 2008)

Pathik said:


> 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 (Apr 24, 2008)

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


----------



## dheeraj_kumar (Apr 24, 2008)

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


----------



## subratabera (Apr 24, 2008)

Try this...


> #include<stdio.h>
> #define ARRSIZE 3
> 
> int main()
> ...


_ 
Change according to your requirements._


----------



## QwertyManiac (Apr 24, 2008)

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 (Apr 24, 2008)

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 (Apr 25, 2008)

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 (Apr 25, 2008)

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 (Apr 25, 2008)

Non-lexicographic is the easiest really.


----------



## Sykora (Apr 25, 2008)

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 (Apr 25, 2008)

QwertyManiac said:


> 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 (Apr 25, 2008)

> 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 (Apr 25, 2008)

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

Thanks.


----------



## dheeraj_kumar (Apr 25, 2008)

@Querty_Maniac

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


----------



## QwertyManiac (Apr 25, 2008)

Sykora said:


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


----------

