Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg41903] Re: O(n^2) complexity of ToCycles in Combinatorica
- From: "Dr. Wolfgang Hintze" <weh at snafu.de>
- Date: Mon, 9 Jun 2003 05:20:49 -0400 (EDT)
- References: <bbt1gd$nf0$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Carl,
I have no solution to your interesting question but I'd like to add
just two comments
(1) it would be nice if we could handle permutations directly in cycle
representation, especially multiplying. The problem in treating it could
be a definition of a canonical form of the representation.
(2) experimenting with your defintion of tocycles I came upon the
question of the structure of cycles lengths in general and began a
little study. Interesting quantities are
(a) number of cycles and
(b) lenght structure
The first results for (a) are these
In[248]:=
ClearAll["Global`*"]
In[249]:=
<< "DiscreteMath`Combinatorica`"
Definition of Carl
In[250]:=
tocycles[p_] := Block[{f},
f[i_] := NestWhileList[
p[[f[#1] = Sequence[]; #1]] & , p[[i]],
#1 =!= i & ]; f /@ p]
Let's look at the cycle structure of random permutations running the
next cell several times playing with the order n of the permutation.
In[284]:=
n = 100;
p = ToCycles[RandomPermutation[n]];
lp = Length[p];
Print["Number of cycles ", lp];
For[i = 1, i <= lp, Print["#", i, ", length = ",
Length[p[[i]]], " \n", p[[i]]]; i++]
Statistics of lengths of cycles
In[330]:=
n = 10;
w = Table[0, {n}];
lng = {};
noOfRuns = 1000;
For[i = 1, i <= noOfRuns,
p = tocycles[RandomPermutation[n]]; cn = Length[p];
w[[cn]] = w[[cn]] + 1; lng = Append[lng, cn];
i++; ];
Output of statistical parameters
In[335]:=
cl = Table[i, {i, 1, n}];
w = w/noOfRuns;
mean = N[w . cl];
sigma2 = N[w . cl^2 - mean^2];
sigma = Sqrt[sigma2];
Print["Statistics of cycle numbers\nOrder of \
permutation = ", n, "\nMean = ", mean,
"\nDispersion = ", sigma2,
", Standard deviation = ", Sqrt[sigma2],
"\nmean/stddv = ", mean/sigma];
From In[367]:=
"Statistics of cycle numbers\nOrder of permutation = "10\
"\nMean = "2.874"\nDispersion = "1.222123999999999", \
Standard deviation = "1.1054971732211707"\nmean/stddv = \
"2.599735277138529
Plot the distribution
In[340]:=
ListPlot[w, PlotJoined -> True, PlotRange ->
{{0, 10}, {0, 0.5}}];
I compared the experimental length distribution with Poisson and
Binomial but none would fit well.
Wolfgang
Carl K. Woll wrote:
> 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
>
>
>