Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Tue, 10 Jun 2003 04:46:49 -0400 (EDT)
- References: <bbt1gd$nf0$1@smc.vnet.net> <001c01c32da0$e9497ab0$b4ab76d5@home>
- Sender: owner-wri-mathgroup at wolfram.com
Wouter,
Thanks, I didn't think to check out the new Combinatorica package. I do have
a few comments, though.
1. The RotateRight will make my output identical to Sriram's, but that's
really unnecessary. After all, for example, the cycle {1,2,3} is completely
equivalent to the cycle {3,1,2}.
2. On my machine, tocycles does release its memory afterwards. On the other
hand, it does take quite a bit more memory than Sriram's version, as
evidenced by MaxMemoryUsed[].
3. At least on my version of Mathematica (4.1), Sriram's version is still
O(n^2) if the permutation is not in a packed array, while my tocycles is
O(n) with or without packed arrays.
4. The basic algorithm used by both Sriram and myself are essentially the
same. I don't understand why Sriram's ToCycles has O(n^2) algorithmic
complexity when working with non packed array permutations.
5. Finally, inspired by the challenge, I present another tocycles which
seems to be more than twice as fast as Sriram's:
tocycles[p_] := Block[{np = p},
If[np[[#]] =!= 0,
tmp = fc[p, #];
np[[tmp]] = 0;
tmp,
Unevaluated[Sequence[]]] & /@ p]
fc = Compile[{{p, _Integer, 1}, {i, _Integer}},
NestWhileList[p[[#]] &, p[[i]], # =!= i &]];
Carl Woll
Physics Dept
U of Washington
----- Original Message -----
From: "wouter meeussen" <wouter.meeussen at pandora.be>
To: mathgroup at smc.vnet.net
Subject: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica
> dear Carl,
>
> looked it up, the link is
> www.cs.uiowa.edu/~sriram/Combinatorica/newFeatures.nb.pdf
> tested your 'tocycles' against Sriram's for a RandomPermutation[10^6]
> yours=48.8 s, his=31.8s
> BUT : yours hogs 339 Mb memory and doesn't release it!
>
> btw, a RotateRight is needed to make your cycles equivalent to Sriram's
> as in :
>
> tocycles[p_] := Block[{f},
> f[i_] := NestWhileList[p[[f[#1] = Sequence[]; #1]] & ,
> p[[i]], #1 =!= i & ];RotateRight/@ (f /@ p)]
>
>
> but it's still a remarkable one-liner,
> a programmer's Haiku,
> a pleasure to work through
>
> Wouter.
>
>
>