Re: combinatorics p

*To*: mathgroup at smc.vnet.net*Subject*: [mg7554] Re: [mg7514] combinatorics p*From*: "David Carraher" <David_Carraher at TERC.edu>*Date*: Fri, 13 Jun 1997 19:38:05 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Reply to: RE>[mg7514] combinatorics problem >The solution answers the question: Given n points in space, in how many >ways can one connect them together to form a loop. Xah, Let's call a necklace "formal" if it has a clasp that requires being fastened so that the maker's name will be upright on the wearer's neck. We can make N! formal necklaces strung from N distinct beads. Now what happens if we string those same N beads on a loop, that is, a necklace with no clasp? Many formerly distinct necklaces are interchangeable as loops. Put otherwise, each loop can be turned into N formal necklaces, depending where one breaks the loop and inserts the clasp. So if there were N! necklaces, there should be only N!/N, or (N-1)! loops. But reversed or flipped loops are the same thing as the unflipped loop--unlike for the formal necklace. By this logic their should be (N-1)!/2 loops of beads. And presumably, an identical number of ways to loop through N points in space. Without the clasp there should be (N! - -------------------------------------- >From: Xah Lee A combinatorics related programing problem. I have a list Permutations[Range[n]]. I want to reduce the list by the following criteria: (1) Two lists are considered the same if one is the other shifted. (RotateRight). (2) Two lists are considered the same if one is the other reversed. The following code captures my criteria. Clear[sameTestQ]; sameTestQ[li1_?PermutationQ,li2_?PermutationQ]:= Or@@(SameQ[li1,#]&/@ Flatten[{#,Reverse at #}&/@Table[RotateRight[li2,i],{i,Length at li2}], 1])/;(Length at li1==Length@li2) Ideally, I should get what I want by Union[Permutation[Range at n], SameTest->sameTestQ] but that doesn't work. The reason can be seen in the example: Union[{{2,1,3,4},{3,4,1,2},{3,4,2,1}},SameTest->sameTestQ] It returns the argument unchanged. The first and last elements are the same, but wasn't filtered out probably because Union only compare adjacent pairs after sorting. I'm working my way using DeleteCases or Select and I'll get it sooner or later. I'm wondering if you had similar problems and solutions before. It does looks like the best way is simply try to generate my list directly, perhaps by writing my own fuction. The problem is then a mathematical one. The solution answers the question: Given n points in space, in how many ways can one connect them together to form a loop. Xah xah at best.com http://www.best.com/~xah/SpecialPlaneCurves_dir/specialPlaneCurves.html Mountain View, CA, USA ------------------ RFC822 Header Follows ------------------ id AA14907; Tue, 10 Jun 1997 13:35:07 -0400 by smc.vnet.net (8.8.5/8.8.5) id KAA11164 for mathgroup-out; Tue, 10 Jun 1997 10:48:49 -0400 (EDT) by smc.vnet.net (8.8.5/8.8.5) id KAA11157 for mathgroup-send; Tue, 10 Jun 1997 10:48:47 -0400 (EDT) From: Xah Lee <xah at best.com> To: mathgroup at smc.vnet.net Subject: [mg7554] [mg7514] combinatorics problem