O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg41869] O(n^2) complexity of ToCycles in Combinatorica
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Sat, 7 Jun 2003 11:44:54 -0400 (EDT)
- Organization: University of Washington
- Sender: owner-wri-mathgroup at wolfram.com
Hi all,
Spurred on by the recent thread on multiplying permutations, I noticed that
the complexity of ToCycles in the Combinatorica package seems to be O(n^2).
I was wondering if anyone had written a function to multiply two
permutations as represented by their cycles, and whether it would be faster
just to convert into the permutation form, multiply the permutations as
discussed in that thread, and then converting back into the cyclic form.
Since ToCycles seemed to have O(n^2) complexity, converting back and forth
seemed like a lost cause.
However, this functionality ought to be O(n), and I thought it might be nice
to present a version of ToCycles which had O(n) complexity. Moreover, I used
an algorithm similar to the one I proposed long ago to do unsorted unions.
In the unlikely event that anyone would want to convert long permutations
into cycles, the following tocycles function would be appealing:
tocycles[p_]:=Block[{f},
f[i_]:=NestWhileList[p[[f[#]=Sequence[];#]]&,p[[i]],#=!=i&];
f/@p]
For example, let's create some permutations:
In[1]:=
<<DiscreteMath`Combinatorica`
In[15]:=
p500=RandomPermutation[500];
p1000=RandomPermutation[1000];
p2000=RandomPermutation[2000];
p10000=RandomPermutation[10000];
p100000=RandomPermutation[100000];
p1000000=RandomPermutation[1000000];
Now, notice that ToCycles seems to be O(n^2)
In[21]:=
{Timing[ToCycles[p500]],Timing[ToCycles[p1000]],Timing[ToCycles[p2000]]}[[Al
l,1]]
Out[21]=
{0.172 Second, 8. Second, 34.25 Second}
while tocycles seems to be O(n)
In[22]:=
{Timing[tocycles[p1000]],Timing[tocycles[p10000]],
Timing[tocycles[p100000]],Timing[tocycles[p1000000]]}[[All,1]]
Out[22]=
{0.031 Second, 0.313 Second, 3.859 Second, 44.828 Second}
Now, the question is whether anyone can come up with a fast way of
multiplying the cyclic form of permutations, or whether one should just
convert to the permutation list form and multiply those. I think the latter
possibility is probably the fastest.
Carl Woll
Physics Dept
U of Washington