Re: combinatorics problem
- To: mathgroup at smc.vnet.net
- Subject: [mg7603] Re: [mg7552] combinatorics problem
- From: Daniel Lichtblau <danl>
- Date: Thu, 19 Jun 1997 15:53:21 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Daniel Lichtblau wrote: > > Xah Lee wrote: > > > > 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. > > ... > > Xah > > xah at best.com > > http://www.best.com/~xah/SpecialPlaneCurves_dir/specialPlaneCurves.html > > Mountain View, CA, USA > > It seems that for every "equivalence class" there is exactly one element > that is a list whose first entry is 1. Hence it may be faster, not to > mention easier to code, to simply generate all permutations of 2..n and > then prepend 1 to each. > ... I guess I should publicly repair the error of my ways. As Xah noted (private e-mail), and others have explained, for each element in the equivalence class, there are 2*n (not just n) permutations. I had not correctly accounted for reversals. So a corrected version would be In[1]:= reducedPerms[n_] := Select[Map[Prepend[#,1]&, Permutations[Range[2,n]]], (#[[2]]>#[[n]])&] In[2]:= reducedPerms[5] Out[2]= {{1, 3, 4, 5, 2}, {1, 3, 5, 4, 2}, {1, 4, 2, 5, 3}, {1, 4, 3, 5, 2}, > {1, 4, 5, 2, 3}, {1, 4, 5, 3, 2}, {1, 5, 2, 3, 4}, {1, 5, 2, 4, 3}, > {1, 5, 3, 2, 4}, {1, 5, 3, 4, 2}, {1, 5, 4, 2, 3}, {1, 5, 4, 3, 2}} Daniel Lichtblau Wolfram Research danl at wolfram.com