Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1997
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1997

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

Search the Archive

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


  • Prev by Date: Re: mathematica problem
  • Next by Date: MatrixExp[DiagonalMatrix[{1,1,-1,-1}]] & MMA 3.0
  • Previous by thread: Re: combinatorics problem
  • Next by thread: Re: Won't Read Entire Soundfile; Why?