       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:= reducedPerms[n_] := Select[Map[Prepend[#,1]&,
Permutations[Range[2,n]]], (#[]>#[[n]])&]

In:= reducedPerms
Out= {{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

```

• Prev by Date: Re: mathematica problem
• Next by Date: MatrixExp[DiagonalMatrix[{1,1,-1,-1}]] & MMA 3.0
• Previous by thread: Re: combinatorics problem