wu :: forums - Print Page


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

        riddles >> cs >> CS: STRING PERMUTATIONS
        
(Message started by: srowen on Aug 3^rd, 2002, 3:55pm)

Title: CS: STRING PERMUTATIONS
Post by srowen on Aug 3^rd, 2002, 3:55pm

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?

Title: Re: CS: STRING PERMUTATIONS
Post by AlexH on Aug 3^rd, 2002, 4:18pm

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.

Title: Fixed printPermutations
Post by srowen on Aug 3^rd, 2002, 9:04pm

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)

Title: Re: CS: STRING PERMUTATIONS
Post by ponkere on Oct 29^th, 2004, 12:12pm

"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!) ?

Title: Re: CS: STRING PERMUTATIONS
Post by John_Gaughan on Oct 29^th, 2004, 1:16pm

on 10/29/04 at 12:12:10, 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 log₂(n!) for an input string of length n.

Title: Re: CS: STRING PERMUTATIONS
Post by ponkere on Nov 1^st, 2004, 8:40am

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!).

Title: Re: CS: STRING PERMUTATIONS
Post by Eros on Nov 2^nd, 2004, 10:03am

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++;
}
}