Re: Cyclic permutations
- To: mathgroup at smc.vnet.net
- Subject: [mg79411] Re: Cyclic permutations
- From: Peter Pein <petsie at dordos.net>
- Date: Thu, 26 Jul 2007 05:30:43 -0400 (EDT)
- References: <f7pon7$prc$1@smc.vnet.net><f7sgu2$ss8$1@smc.vnet.net> <f84juv$qpq$1@smc.vnet.net> <200707250614.CAA23554@smc.vnet.net> <f8754d$pkk$1@smc.vnet.net>
King, Peter R schrieb:
> I have a set of permutations eg.
>
> {a,b,c,d}, {a,c,b,d} {b,c,d,a}
>
> Some of which are just cyclic variations of others (ie. {b,c,d,a} is a
> cyclic variant of {a,b,c,d}). Is there a simple way of getting rid of
> these, so that the above set just becomes
>
> {a,b,c,d}, {a,c,b,d}
>
> I am quite happy to select the cyclic variant to be kept arbitrarily (or
> using lexical ordering, I'm not particularly concerned).
>
> Thanks in advance for your help.
>
> Peter King
>
> (by the way I am still using version 5.1 so V6 specific methods wouldn't
> help I'm afraid)
>
>
Hi Peter,
Union[] together with an appropriate SelfTest works fine:
In[1]:=
permset = {{a, b, c, d}, {a, c, b, d}, {b, c, d, a}};
Union[permset, SameTest -> (MemberQ[Partition[Join[#1, #1], Length[#1],
1], #2] & )]
Out[2]=
{{a, b, c, d}, {a, c, b, d}}
In[3]:=
Union[permset, SameTest ->
(MemberQ[Function[x, (RotateLeft[x, #1] & ) /@ Range[Length[x] -
1]][#1],
#2] & )]
Out[3]=
{{a, b, c, d}, {a, c, b, d}}
but it is a bit slow.
The fastest I have found is ~10 times faster than the Partition[] method
above and ~20 times faster than the RotateLeft[] version and probably at
least 10 times slower than any solution by Carl Woll ;-) :
removeRotations[permset_] :=
First /@ Rest[NestWhileList[
Block[{nr1 = #1[[2,1]]},
{nr1,
DeleteCases[Rest[#1[[2]]],
Alternatives @@ NestList[RotateLeft, nr1, Length[nr1] - 1], {1}]
}] & ,
{{}, permset}, #1[[2]] =!= {} & ]]
Regards,
Peter
- References:
- Re: Mathematica to .NET compiler
- From: David Bailey <dave@Remove_Thisdbailey.co.uk>
- Re: Mathematica to .NET compiler