MathGroup Archive 2003

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

Search the Archive

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.
>
>
>



  • Prev by Date: Re: Taking a function as a parameter of a function
  • Next by Date: Re: Mathlink performance and task switches
  • Previous by thread: Re: O(n^2) complexity of ToCycles in Combinatorica
  • Next by thread: RE: Re: O(n^2) complexity of ToCycles in Combinatorica