All permutations of a string - PrismoSkills

All permutations of a string - PrismoSkills
static void permute(char[] s, int i)
{
    if (i==s.length-1)
    {
        count++; // count no of words output and print the permutation.
        System.out.println(count + ") " + new String(s));
        return;
    }
    int curr = i;
    for (; i<s.length; i++)
    {
        swap (s, i, curr);
        permute (s, curr+1);
        swap (s, i, curr);
    }
}
Code to handle duplicate characters

To handle duplicate characters, we need to use a hash-set which will make sure a character already used in an index does not come there again.
This code works for non-repeated characters too.

void permute(char[] s, int i)
{
    if (i==s.length-1)
    {
        count++;
        System.out.println(count + ") " + new String(s));
        return;
    }
    HashSet<Character> charsDone =
        new HashSet<Character> (); //  <== initialize a hash-set at each recursion level
    int curr = i;
    for (; i<s.length; i++)
    {
        if (charsDone.contains(s[i])) //  <== if char is used, do not re-process it
            continue;
        charsDone.add(s[i]);
        swap (s, i, curr);
        permute (s, curr+1);
        swap (s, i, curr);
    }
}
http://www.geeksforgeeks.org/permutations-string-using-iteration/

Recursion is always costly and iteration is preferred. Below are steps of iterative approach.

1. Find no of permutations of the string by calculating value of n!. Then use this value to iterate.
2. Store the original string in an auxiliary string and use that string to do the math.
3. Fix the first position(character), and swap all the j’th and (j+1)’th characters till (n-1)!.
4. At the end of first (n-1)! all the (n-1)th characters will be permuted.
5. Now again store the original string to the auxiliary string and swap i’th and (i+1)’th characters and repeat the 3rd and 4th process.

Concept Used : We keep swapping a character only till it reaches the end

1. Fix ‘a’. Swap ‘b’ with its next neighbors till b reaches the end.
   ( “acbd”, “acdb”)
2. Now ‘c’ will be at the 2nd position, do the same thing with it.
   ( “adcb”, “adbc”)
3. Now ‘d’ will be at the 2nd position, do the same thing with it.
   ( “abdc”, “abcd”)
4. All 6 i.e., (4!/4)permutations of the first cycle obtained.
5. Repeat the above process by bringing swapping ‘a’ with ‘b’
6. The new string to “play” will be “bacd”.

int fact(int n)

{

    return (n==1)? 1 : n*fact(n-1);

}

void printPermutation(string s)

{

    // Find length of string and factorial of length

    int n = s.length();

    int fc = fact(n);

 

    // Point j to the 2nd position

    int j = 1;

 

    // To store position of character to be fixed next.

    // m is used as in index in s[].

    int m = 0;

 

    // Iterate while permutation count is

    // smaller than n! which fc

    for (int perm_c = 0; perm_c < fc; )

    {

        // Store perm as current permutation

        string perm = s;

 

        // Fix the first position and iterate (n-1)

        // characters upto (n-1)!

        // k is number of iterations for current first

        // character.

        int k = 0;

        while (k != fc/n)

        {

            // Swap jth value till it reaches the end position

            while (j != n-1)

            {

                // Print current permutation

                cout << perm << "\n";

 

                // Swap perm[j] with next character

                swap(perm[j], perm[j+1]);

 

                // Increment count of permutations for this

                // cycle.

                k++;

 

                // Increment permutation count

                perm_c++;

 

                // Increment 'j' to swap with next character

                j++;

            }

 

            // Again point j to the 2nd position

            j = 1;

        }

 

        // Move to next character to be fixed in s[]

        m++;

 

        // If all characters have been placed at

        if (m == n)

           break;

 

        // Move next character to first position

        swap(s[0], s[m]);

    }

}

http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Algorithm Paradigm: Backtracking
Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.

/* Function to swap values at two pointers */

void swap(char *x, char *y)

{

    char temp;

    temp = *x;

    *x = *y;

    *y = temp;

}

 

/* Function to print permutations of string

   This function takes three parameters:

   1. String

   2. Starting index of the string

   3. Ending index of the string. */

void permute(char *a, int l, int r)

{

   int i;

   if (l == r)

     printf("%s\n", a);

   else

   {

       for (i = l; i <= r; i++)

       {

          swap((a+l), (a+i));

          permute(a, l+1, r);

          swap((a+l), (a+i)); //backtrack

       }

   }

}

    permute(str, 0, n-1);
http://www.geeksforgeeks.org/permutations-of-a-given-string-using-stl/

void permute(string str, string out)

{

    // When size of str becomes 0, out has a

    // permutation (length of out is n)

    if (str.size() == 0)

    {

        cout << out << endl;

        return;

    }

 

    // One be one move all characters at

    // the beginning of out (or result)

    for (int i = 0; i < str.size(); i++)

    {

        // Remove first character from str and

        // add it to out

        permute(str.substr(1), out + str[0]);

 

        // Rotate string in a way second character

        // moves to the beginning.

        rotate(str.begin(), str.begin() + 1, str.end());

    }

}

We can use next_permute() that modifies a string so that it stores lexicographically next permutation. If current string is lexicographically largest, i.e., “CBA”, then next_permute() returns false.

We first sort the string, so that it is converted to lexicographically smallest permutation. Then we one by one call next_permutation until it returns false.

void permute(string str)

{

    // Sort the string in lexicographically

    // ascennding order

    sort(str.begin(), str.end());

 

    // Keep printing next permutation while there

    // is next permutation

    do {

       cout << str << endl;

    } while (next_permutation(str.begin(), str.end()));

}

Read full article from All permutations of a string - PrismoSkills