Jump to content




Recent Status Updates

  • Photo
      30 Sep
    rhossis

    laptop hard disk seated beneath motherboard but with no access panel. 7 hours to replace :(

    Show comments (3)
  • Photo
      19 Sep
    Chall

    I love it when you go to write a help thread, then while writing, you reach an enlightenment, and figure it out yourself.

    Show comments (3)
View All Updates

Developed by Kemal Taskin
Photo
- - - - -

How to generate all Permutations

java

  • Please log in to reply
1 reply to this topic

#1 fkl

fkl

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 415 posts

Posted 10 July 2011 - 01:34 PM

Problem: Given a string, print it’s all permutations

This is a situation that might arise in a programmer’s every day project activities. It mainly tests some one’s grip on recursion too. At the same time is a pretty small problem. Hence by all means, it serves as a great programming interview question and to the best of my direct knowledge, has been asked at around many big guns among others.

Also it has often been what many people stumbled against on this forum
http://forum.codecal...i-generate.html
http://forum.codecal...ding-order.html
http://forum.codecal...y-2d-array.html

So to do a bit of revision, a permutation of a string is basically achieved by reordering the position of elements. It is also famously known that given a string of length n, there are n! (factorial) permutations i.e. if we have a string of length 3 i.e. “xyz” here is a list of all permutations

xyz xzy yxz yzx zxy zyx

As you can see there are no more possibilities and these are total of 6 permutations i.e. 3! = 3X2.

Also please bear in mind that permutation is different from a combination i.e. combination usually says like given 4 players, how many ways are there to pick a team of 3 players. This would be combination in which ORDER of elements does not matter. Two combinations always differ by at least one element. Whereas no such restriction applies to permutations in which ORDER matters.

So getting back, our problem says, if we are given “xyz” we are required to print all permutations as the case above shows.

Looking at the outputs, can you devise an algorithm? Any ideas?

Like I said before, this sounds like a problem that can be done naturally with recursion. Well, until now we haven’t seen a relationship or a recursive pattern.

Let’s take a closer look, given a string of 3 elements i.e. “xyz”, how did you go about printing all permutations on paper?

Here is how we went,
“x followed by all permutations of y and z” (yz and zy)
“y followed by all permutations of x and z” (xz and zx)
And finally “z followed by all permutations of x and y” (xy and yx)

So to break down the problem, we fix one element in the initial position and try to change the rest of them for all possible situations. To achieve this, we call the same function recursively again, with one less element since the first one’s possibilities are already figured out.

To do this in code practically, we have a function called permutation. It takes two understandable arguments, a string (char array in c) and its length (excluding the terminating null).

However, there is one more parameter that we will need. Because we have to move ahead in the array with every call i.e. first we fix first element, then second and so on. So this basically means we are going to increase the starting index of array.

Now we are passing a character array, so each time we have to add another parameter called “starting or current index” of the permutations to be explored in the current call.

If this index is 0, for the example above it means x is fixed and we generate further permutations of y and z, when this is 1, it means first two places are fixed and it is the third and onwards positions that need to be moved.

Next we get inside our actual function. It has two main parts.

The first part prints a permutation when it is ready. We will get to this in a minute.

The second part is the meat of the function. It runs a loop from our current index to size of array. In each iteration of that loop it swaps the current index and loop variable. Right at that point it calls the permutation function again recursively to generate all further permutations of this swapped state. Once that call is done, it swaps back the variables to original state. This is required because for e.g. after we are done with generating for x (yz and zy) we want to start from the original state again i.e. original state was xyz so now we move y to the first place by swapping it with x, so y followed by xz and then zx would be the sequence. Code follows

void swap(char *fir, char *sec)
{
    char temp = *fir;
    *fir = *sec;
    *sec = temp;
}

/* arr is the string, curr is the current index to start permutation from and size is sizeof the arr */
void permutation(char * arr, int curr, int size)
{
    if(curr == size-1)
    {
        for(int a=0; a<size; a++)
            cout << arr[a] << "\t";
        cout << endl;
    }

    else
    {
        for(int i=curr; i<size; i++)
        {
            swap(&arr[curr], &arr[i]);
            permutation(arr, curr+1, size);
            swap(&arr[curr], &arr[i]);
        }
    }
}

int main()
{

    char str[] = "abcd";

    permutation(str, 0, sizeof(str)-1);
    return 0;
}


Following is the output of the above code run with string “abcd”’

permutations1.jpg

There was no special reason for making swap a separate function and pass the array elements as pointers and swap inside the function. It just makes the main loop appear more tidy and understandable. Feel free to insert two 3 assignments each for the swaps if you are not comfortable with the pointer manipulation.

As you can see with each new call to permutation, we are increasing the current index by 1. Soon there will be a time when it reaches to one less than the size of string. This is our base case as there is only one more element whose position we cannot swap with another. All previous possible orderings have received a separate recursive function call. It is at this point that we print the entire permutation from index 0 up to size. This part is in the beginning of the function under the if block.

The running time of this algorithm is of course n! Simple analysis tells that there is a for loop running from start to end of string. For each element of the string there is a recursive call which keeps decreasing string length by one with every successive call.

The standard c++ STL also provides a built in function for achieving the same task (generating next permutation) though it uses vector (c++ arrays) and iterators. However, it is pretty handy so I thought of adding a sample of its usage along

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> vec; 

void print()
{
    //for(int i=0; i<vec.size(); i++)
    //    cout << vec[i] << " ";
    for(vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
        cout << *it << "\t";
    cout << endl;
}

int main()
{

    for(int i = 1; i < 5 ; i++) { 
        vec.push_back(i); 
        cout << vec[i-1] << "\t";
    }

    cout << endl;

    while(next_permutation(vec.begin(), vec.end()) ){
        print();
        // do some processing on vec
    }

    return 0;
}


And here is the output of above STL function usage. We have basically inserted numbers 1234 and generated all of their permutations

permutations2.jpg
  • 0
Today is the first day of the rest of my life

#2 ZekeDragon

ZekeDragon

    CC Leader

  • Retired Mod
  • PipPipPipPipPipPipPip
  • 1,263 posts

Posted 11 July 2011 - 03:45 AM

It should be noted that when you specify that next_permutation() takes an iterator, that means any iterator, not just the std::iterator class set. This could include pointer addresses of an array of some kind.
int main(void)
{
  char some_str[] = "abcd";
  int len = strlen(some_str);

  do
  {
    for (int i = 0; i < len; ++i)
    {
      std::cout << some_str[i] << '\t';
    }
    std::cout << std::endl;
  } while (std::next_permutation(some_str, some_str + len));
}
This is because next_permutation is a template function, so a new instance of that function is generated for each type passed, and all that's important is that the type successfully compiles when treated as a Bidirectional iterator. Also, next_permutation() will return the array to it's equivalent sorted array after a failed call to next_permutation(). In essence, the last permutation (which results in next_permutation returning false) will modify the array back to a lexicographically sorted state.
  • 0
If you enjoy reading this discussion and are thinking about commenting, why not click here to register and start participating in under a minute?





Also tagged with one or more of these keywords: java