MathGroup Archive 1997

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

Search the Archive

Re: combinatorics problem

On Tue, 10 Jun 1997, 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.
> ...

Hi Xah,

How about the following approach. Define a function which generates a
canonical form for each loop:

canon[a_?PermutationQ] := 
Module[{len = Length[a],
	i1  = Position[a,1][[1,1]],
	i2  = Position[a,2][[1,1]]},

	If[ Mod[ i2-i1, len ] < len/2,

The above function converts a loop specification into a canonical form,
which is described by starting with 1, and then going in the direction
where 2 is reached first. 

Now, let's apply this function on your example

> ...
> Union[{{2,1,3,4},{3,4,1,2},{3,4,2,1}},SameTest->sameTestQ]
> ...

Union[ canon /@ {{2,1,3,4},{3,4,1,2},{3,4,2,1}} ]

which returns


In terms of canon, your test function could be written


Of course, generating all the loops by doing something like

Union[ canon /@ Permutations[Range[n]] ]

will become slow very quickly.

Also, there may be a canned routine which does this for you in
DiscreteMath`Combinatorica`, for example, something along the lines of


  • Prev by Date: Mathematica in Quantum Field Theory (II)
  • Next by Date: Set of numbers in Mma 3.0 is smaller tha
  • Previous by thread: Re: combinatorics problem
  • Next by thread: Re: combinatorics problem