[Tutor] Generating Unique Permutations

[spir]

Michael Morrissey <gdoghomes at gmail.com> dixit:

> I'm just a philosophy teacher, and I don't know much about mathematics or
> computers. I'm writing a python program (not the best language for this
> topic, but it is what I know), and I need to solve a problem which requires
> more knowledge than I have. I'm hoping you can help me. =)
> 
> I'm looking for an efficient way to create all the unique, non-duplicated
> permutations of a list (I believe these are called "necklaces" in
> combinatorics). I need to do this without actually generating every possible
> permutation (which includes all the duplicates).
> 
> For example:
> 
> List = [a,a,b,b]
> 
> My output would be something like:
> 
> a,a,b,b
> a,b,a,b
> a,b,b,a
> b,a,a,b
> b,a,b,a
> b,b,a,a
> 
> Importantly, you'll see that these are only generated once. There are four
> permutations which can be generated from the list which all look like
> (a,a,b,b), but I only want to generate this output a single time.
> 
> My problem is large enough that I can't feasibly generate all the
> permutations (60! I think) and eliminate the duplicates from there, but I
> could feasibly generate the unique ones (a much small search space),
> especially if I use an efficient algorithm (I'm sorry to focus so much on
> efficiency, but it matters).
> 
> What is the best way to do this? If you don't know how it would work in
> Python, can you explain in psuedocode? As I said, I'm not very smart about
> these things, so treat like a child to the topic (because I am a child to
> the topic, an interested child!).
> 
> Oh, and thanks for this mailing/reading list! I spend countless hours
> browsing and reading other people's code. It is a lot of fun =).
> 
> 
> 
> 
> Sincerely,
> Michael

The critical point is indeed to generate every unique permutation without generating all. I don't know of any standard algorithm for this, but I think a key point may be: instead of starting with a list of characters considered individually, start with a list of (char, count) _pairs_. For instance:

List = [a,a,a,b,b,c]
==>
List = [(a,3), (b,2), (c,1)]

From there, you can certainly generate permutations without duplicates. However, I don't exactly know how to ;-) Don't remember of this problem at school, but the overall number of permutations should be IIRC:
   n! / (n1! x n2! x n3! ...)
So, in the case above:
   6! / (3! x 2! x 1!) = 60
?

The process will be to sequentially place characters of each (char, count) pair at all possible places. Eg the a's will be at positions 123, 124, 125, 126, 134... For each of these positionings 
of a's, walk through all permutations for other letters. Then start with placing b's, then c's -- but only combine for positions that where not yet considered when starting with a's, then with a's & b's; this is the difficult part.


Denis
________________________________

la vita e estrany

http://spir.wikidot.com/