wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Permutations of a string with repeated elements
        
(Message started by: Eros on Nov 2^nd, 2004, 5:31am)

Title: Permutations of a string with repeated elements
Post by Eros on Nov 2^nd, 2004, 5:31am

The problem is as follows:
Generate permutations of a given string. Some of the elements of the string might be repeated. Generate only unique permutation.
i already know a solution but it computes all the permutations and checks if the string is already present.
can we save on some work, by not computing a string, identical to any of the already computed ones.

Title: Re: Permutations of a string with repeated element
Post by towr on Nov 2^nd, 2004, 5:49am

I'm sure you can save a lot of work.
Obviously the first step is finding which elements are repeated and how often. This can simply be done by sorting them.
I suppose then you just pick elements from each non-empty bag (which contains all elements of the same kind) and then concatenate them.

Title: Re: Permutations of a string with repeated element
Post by Eros on Nov 2^nd, 2004, 7:30am

sorry to start another string i should have checked atleast some recent thread. Will do that from next time.
Towr i haven';t as yet understood ur solution properly :-[
are u saying that u will keep a seperate array, storing that a similar element has already occured at this position.
lets say we are having abbcd

we get all the permutations of the string bbcd putting a in the first slot.

and then as we proceed
we put b in the first slot now and store that b has already been in the first position and all the permutation of these have been accounted of.

space taken up is huge. i.e. if this works correctly (i think some case get left out.)

oh i forgot to mention that we will have to sort the string to find out the repeated elements and then apply this.

Title: Re: Permutations of a string with repeated element
Post by towr on Nov 2^nd, 2004, 2:47pm

I had a very nice and long reply written, but the world hates me and made my browser crash. So you'll have to make do with this.

The time complexity is linear in the output, and the space complexity is linear in the alfabet of the string.

The program would be something like:

Code:

vector<int> bag(256); // alphabet is all characters
string s;

void make(int pos)
{
if (pos == s.size())
cout << s << endl;
else
for(int i=0; i < 256; i++)
if (bag[i] > 0)
{
bag[i] --;
s[pos] = i;
make(pos+1);
bag[i] ++;
}
}

main(int argc, char **argv)
{
s=argv[1];
while (*s)
bags[*s++]++; // count elements

make(0);
}

This can be improved by using a better bagging method, but the idea should be clear.