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