Author |
Topic: CS: STRING PERMUTATIONS (Read 2094 times) |
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
CS: STRING PERMUTATIONS
« on: Aug 3rd, 2002, 3:55pm » |
 Quote  Modify
|
Here's my idea in pseudo-code:
printPermutations(String s, int offset)
if offset == s's length
write s to output
return
for swapWith = offset to s's length-1
swap s[offset] with s[swapWith]
printPermutations(s, offset+1)
swap back s[offset] with s[swapWith]
printAllPermutations(String s)
printPermutations(s, 0)
Basically you attack the problem by first leaving s's first character in place, and printing all permutations of the rest of s recursively. Once that's done, you swap the first character with another one in the s, and do the same thing. Repeat until you've swapped and repeated on every character in s. It works...
Now of course this algorithm is Theta(n!), but anything that prints all permutations of a string of n characters is Omega(n!). Maybe this can be made a little faster, but not significantly faster in the theoretical sense.
Right? Better ideas?
|
|
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: CS: STRING PERMUTATIONS
« Reply #1 on: Aug 3rd, 2002, 4:18pm » |
Quote Modify
|
Assuming we want to print out each permutation exactly one, then there is a problem. The question does not make this requirement explicit so I'm not saying you're wrong, just that you might want to consider what to do when there are repeated letters in the string so that you get only 1 copy of each different permutation. In cases where there are several repeated letters it will save quite a bit of time to only do unique strings.
There is also some tricky stuff you could do if you if you were allowed to print out all the permutations mashed together as one giant string which had every possible permutation as a (contiguous) substring but I don't think that was the intent of the problem.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Fixed printPermutations
« Reply #2 on: Aug 3rd, 2002, 9:04pm » |
Quote Modify
|
Good point, this should take care of it:
printPermutations(String s, int offset)
if offset == s's length
write s to output
return
Set seenCharacters
for swapWith = offset to s's length-1
if seenCharacter doesn't contain s[swapWith]
swap s[offset] with s[swapWith]
printPermutations(s, offset+1)
swap back s[offset] with s[swapWith]
add s[swapWith] to seenCharacters
printAllPermutations(String s)
printPermutations(s, 0)
|
|
IP Logged |
|
|
|
ponkere
Guest
|
|
Re: CS: STRING PERMUTATIONS
« Reply #3 on: Oct 29th, 2004, 12:12pm » |
Quote Modify
 Remove
|
"There is also some tricky stuff you could do if you if you were allowed to print out all the permutations mashed together as one giant string which had every possible permutation as a (contiguous) substring but I don't think that was the intent of the problem. "
How can this be done in < O(n!) ?
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: CS: STRING PERMUTATIONS
« Reply #4 on: Oct 29th, 2004, 1:16pm » |
Quote Modify
|
on Oct 29th, 2004, 12:12pm, ponkere wrote:| How can this be done in < O(n!) ? |
|
Calculating permutations is inherently O(n!). Obviously, Theta and Omega are also n!. Anyway, the answer to your question is "it can't."
To address a previous message, a data set with repeated elements will have n! permutations. Unique permutations will be lower, but two identical output strings both count.
One easy way to ensure unique output is to store the output in a binary tree using only keys (no values). A concrete example is using C++'s std::set data structure. Adding a value already in the tree does nothing. Given the potentially large size of the result tree, random access is fast at log2(n!) for an input string of length n.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
ponkere
Guest
|
|
Re: CS: STRING PERMUTATIONS
« Reply #5 on: Nov 1st, 2004, 8:40am » |
Quote Modify
Remove
|
Yes, the process is O(n!) even if we want to print only the unique strings. In fact, we'd need to do a little more work since we have to find out which strings are unique.
I was referring to the "tricky stuff" (I'm not sure if this is about printing unique strings) mentioned in the same post which printed the long string. I figured it must have a time complexity of < O(n!) as you are making some assumptions about the output. Of course, splitting this string to print n! perms is trivially O(n!).
|
|
IP Logged |
|
|
|
Eros
Newbie
Gender:
Posts: 7
|
|
Re: CS: STRING PERMUTATIONS
« Reply #6 on: Nov 2nd, 2004, 10:03am » |
Quote Modify
|
A c# code to print only the unique permutations of a string with repeated elements.
void UniquePermutation(char [] list, int k, int m)
{
if (k == m)
{
Console.Write (list);
Console.WriteLine (" ");
}
else
{
for (int i = k; i < m; i++)
{
swap (ref list[k],ref list[i]);
UniquePermutation(list, k+1, m);
swap (ref list[k],ref list[i]);
while( (i<m-1)&& (list[i] == list[i+1]))
i++;
}
}
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print