<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.E-postmall17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;}
@page Section1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 70.85pt 70.85pt;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=SV link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>/Robert<o:p></o:p></span></p>
<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'>
<p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:
"Tahoma","sans-serif"'>Från:</span></b><span lang=EN-US style='font-size:10.0pt;
font-family:"Tahoma","sans-serif"'> tutor-bounces+robert.johansson=math.umu.se@python.org
[mailto:tutor-bounces+robert.johansson=math.umu.se@python</span><span
style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>.org] <b>För </b>Michael
Morrissey<br>
<b>Skickat:</b> den 18 december 2009 06:54<br>
<b>Till:</b> tutor@python.org<br>
<b>Ämne:</b> [Tutor] Generating Unique Permutations<o:p></o:p></span></p>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<div>
<p class=MsoNormal>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. =)<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>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).<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>For example:<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>List = [a,a,b,b]<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>My output would be something like:<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>a,a,b,b<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal>a,b,a,b<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal>a,b,b,a<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal>b,a,a,b<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal>b,a,b,a<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal>b,b,a,a<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>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.<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>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).<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>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!).<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>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
=).<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal>Sincerely,<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal>Michael<o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
<div>
<p class=MsoNormal><o:p> </o:p></p>
</div>
</div>
</body>
</html>