[Tutor] Generating Unique Permutations

[Shashwat Anand]

create your desired list
>>> l = ['a', 'a', 'b', 'b']

do a permutation and take unique values
>> import itertools
>> set(itertools.permutations(l))

HTH

On Fri, Dec 18, 2009 at 11:24 AM, Michael Morrissey <gdoghomes at gmail.com>wrote:

> 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
>
>
>
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20091218/90e60973/attachment.htm>