[Tutor] Generating Unique Permutations

[Robert Johansson]

I think you mean a multiset not a necklace. A necklace is invariant under
rotations and reflections aabb=abba=bbaa=baab and abab=baba. Seems that some
people name them bags instead of multiset. Maybe this can help you finding
more examples? I see that you got a few already.

 

/Robert

Från: tutor-bounces+robert.johansson=math.umu.se at python.org
[mailto:tutor-bounces+robert.johansson=math.umu.se at python.org] För Michael
Morrissey
Skickat: den 18 december 2009 06:54
Till: tutor at python.org
Ämne: [Tutor] Generating Unique Permutations

 

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

 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20091218/7cc6362f/attachment-0001.htm>