Author |
Topic: Permutations of a string with repeated elements (Read 1163 times) |
|
Eros
Newbie
Gender: 
Posts: 7
|
 |
Permutations of a string with repeated elements
« on: Nov 2nd, 2004, 5:31am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Permutations of a string with repeated element
« Reply #1 on: Nov 2nd, 2004, 5:49am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 2nd, 2004, 5:50am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eros
Newbie
Gender:
Posts: 7
|
|
Re: Permutations of a string with repeated element
« Reply #2 on: Nov 2nd, 2004, 7:30am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Permutations of a string with repeated element
« Reply #3 on: Nov 2nd, 2004, 2:47pm » |
Quote Modify
|
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.
|
| « Last Edit: Nov 2nd, 2004, 2:52pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print