[Date Index] [Thread Index] [Author Index]

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