Bipins Dot Net daily bits and pieces

Non Recursive approach to generate possible combinations of characters in password

Q). Given a password : Write an algorithm to print all possible combinations of that password.

/*
A non recursive approach to the problem and similar problems which has to generate permutation of certain set of characters.

The idea here is to first find the number of possible combinations of output.
Say, n is the length : possible combination  = n!
Then to find the formula that would repeat the pattern. The recursive method broken down into linear/ incremental formula.

The recursion is converted to a loop of   size n!.

A technique should be generated that could give us the combination output given any instance of value of loop index.

Say if n=4,  n! = 24.
So at any instance, say when loopindex = 11 then it should give the sequence that would be generated on 11th position.

For that, we find out position of each character in the remaining set.
say, for    given  "1234"
1st char will be  at position  index / (n-1)!  =  11/ 6 = 1  , so first char = 2;
now the given set should exclude the output char =>   remaining "134"
now in the remaining set , the index also decreases
the decrement of index , ie. 11   will be = index % (n-1)! = 11 % 6 = 5

Again,   index / (n-1)! = 5 / (3-1)! = 0 , so char = 1
remaining set = "34"

and so on

It can be used for any amount of number or characters.

*/

#include<iostream>
#include<string>

using namespace std;
int facto(int x)
{
    int fact=1;
    while(x>0) fact*=x--;
    return fact;
}

int main(int argc, char **argv)
{
    string s;
    int len,fact,rem=0,pos=0;

    cin>>s; // Input is take as string, it can be checked if it is a number or not, I'm just making it generic
    len=s.size();
    fact = facto(len);
    // Main loop
    for(int i=0;i<fact;i++)
    {
        string str = s;
        rem = i;
        cout<<i+1<<". ";
        for(int j=len;j>0;j--)
        {
            int div = facto ( j-1);
            pos = rem / div; // finding out position
            rem = rem % div; // adjusting the index value
            cout<<str.at(pos); // output char
            str = str.erase(pos,1); // decreasing the problem set size
        }
        cout<<endl;
    }
}