RE: Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg42001] RE: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Mon, 16 Jun 2003 03:57:13 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Carl, thank you for that remark. This is was due to a last minute try to squeeze out the last drop. (Alas! by principle, never do so!) I even had a bad feeling about doing so anyhow, i.e. had I left off the necessary checks, hurry and greed! My prior version copied the input p to a local pa and worked with that. It's only minute slower: In[3]:= tc1x0c = Compile[{{p, _Integer, 1}}, Module[{ca = p, pa = p, ppa = p, xp = 0, xc = 0, xxp = 0, xppa = 0, xlp = 0, len = Length[p]}, While[While[++xp <= len && pa[[xp]] === 0,]; xp <= len, ca[[++xc]] = xp; ppa[[++xppa]] = xc; xxp = xp; While[(xxp = pa[[xlp = xxp]]) =!= xp, ca[[++xc]] = xxp; pa[[xlp]] = 0]; pa[[xlp]] = 0 ]; n = xppa; {ca, ppa}]]; The idea is: not to use any List constructions. The cycles are returned in an array, ca, however as a flat structure (of same length as the permutation p). Therefore the beginning indices for each cycle are also returned, again in an array of that length (needed for the identity permutation). The valid length of that is returned via a global variable. pa is a copy of the permutation, where all used values are being marked off in the course of the calculation. In[4]:= tc1x0[p_] := Block[{n, ca, ppa, res}, res = tc1x0c[p]; ppa = Take[res[[2]], n]; Block[{Take}, Thread[Take[res[[1]], #], List, -1]] &@ Transpose[{ppa, (Drop[ppa, 1] - 1)~Join~{Length[p]}}] ] In[47]:= p0 = p1000000; Scan[Print[Timing[#[p0]][[1]], ": ", ToString[#]] &, {tc1x0, tc1x}] >From In[47]:= 5.268 Second": "tc1x0" >From In[47]:= 5.207 Second": "tc1x" In[51]:= p0 = Range[100000]; Scan[Print[Timing[#[p0]][[1]], ": ", ToString[#]] &, {tc1x0, tc1x}] >From In[51]:= 2.584 Second": "tc1x0" >From In[51]:= 2.763 Second": "tc1x" -- Hartmut >-----Original Message----- >From: Carl K. Woll [mailto:carlw at u.washington.edu] To: mathgroup at smc.vnet.net >Sent: Thursday, June 12, 2003 4:25 PM >To: Wolf, Hartmut >Subject: [mg42001] Re: [mg41915] Re: O(n^2) complexity of ToCycles in >Combinatorica > > >Hartmut, > >Only a comment. Your tc1x overwrites its input so that it >can't be run twice >in a row. For example, > >perm=Range[10]; >tc1x[perm] >tc1x[perm] > >produces a bunch of error messages. > >Carl Woll >Physics Dept >U of Washington > [...]