Skip to content

Counting Cycles of a Permutation in Parallel

September 4, 2009


How to count the number of cycles modulo 2 in parallel

images

Gian-Carlo Rota was one the world experts on combinatorics, and helped move the field from a corner of mathematics to become one of its central areas. Rota is famous for many other things, but his book Indiscrete Thoughts is a classic—it is a great read. Even more famous, is his list of Ten Lessons I Wish I Had Been Taught.

Today I plan to follow one of Rota’s lessons and highlight a result that I have already presented. I have not done this before, but I think the result is sufficiently interesting to warrant this. Somehow it got lost before, since the post on it contained several other ideas and results. This time it will be alone. I hope you agree that it is worth repeating; I think it is an interesting “trick” that you might be able to use.

Rota’s ten lessons created a bit of “push-back” as people say. The lesson that got the most push-back was titled:

Publish the Same Result Several Times,

which caused many to get quite upset—perhaps more than a bit. This is, of course, the lesson that I am following today.

Here is the exact quote from his paper:

After getting my degree I worked for a few years in functional analysis. I bought a copy of Frederick Riesz’s Collected Papers as soon as the big, thick, heavy, oversize volume was published. However, as I began to leaf through, I could not help but notice that the pages were extra thick, almost like cardboard. Strangely, each of Riesz’s publications had been reset in exceptionally large type. I was fond of Riesz’s papers, which were invariably beautifully written and gave the reader a feeling of definitiveness.

As I looked through his Collected Papers, however, another picture emerged. The editors had gone out of their way to publish every little scrap Riesz had ever published. It was clear that Riesz’s publications were few. What is more surprising is that the papers had been published several times. Riesz would publish the first rough version of an idea in some obscure Hungarian journal. A few years later he would send a series of notes to the French Academy’s Comptes Rendus in which the same material was further elaborated. A few more years would pass, and he would publish the definitive paper, either in French or in English.

Adam Koranyi, who took courses with Frederick Riesz, told me that Riesz would lecture on the same subject year after year while meditating on the definitive version to be written. No wonder the final version was perfect.

Riesz’s example is worth following. The mathematical community is split into small groups, each one with its own customs, notation, and terminology. It may soon be indispensable to present the same result in several versions, each one accessible to a specific group; the price one might have to pay otherwise is to have our work rediscovered by someone who uses a different language and notation and who will rightly claim it as his own.

Let’s now turn to the result that I want to highlight, which was originally presented here.

Number of Cycles of a Permutation

The result concerns permutations. Of course a permutation is nothing more than a mapping {\pi} from a finite set {S} to itself that is one-to-one. The set is usually taken to be {1,2,\dots,n} for some {n}, but we will allow any set {S}.

The problem that I want to discuss is: does {\pi} have an even or an odd number of cycles? Every permutation can be uniquely written, up to order, as a collection of cycles. The number of cycles of a permutation {\pi} will be denoted by {\mathsf{cycle}(\pi)}.

Computing the number of cycles of a permutation seems to a sequential property. I am not exactly sure how to state this precisely, but the obvious algorithm requires that you pick a point {x \in S}, and then trace out its cycle:

\displaystyle x, \pi(x), \pi(\pi(x)), \dots, x

Then, move on to the next cycle, and eventually discover the cyclic structure of {\pi}. This yields, of course, the exact number of cycles of the permutation.

There is another way to compute the number of cycles of a permutation modulo {2} that is more indirect. This is the trick that I want to highlight:

Theorem: For any permutation {\pi},

\displaystyle  \mathsf{cycle}(\pi) \equiv |S| + \mathsf{inv}(\pi) \bmod 2

Here { \mathsf{inv}(\pi)} is the number of inversions of the permutation {\pi}: an inversion is a pair of {x} and {y} in {S} so that {x<y} and yet {\pi(x) > \pi(y)}. Here is an example: Consider the permutation that maps,

\displaystyle  1 \rightarrow 2 \text{ and } 2 \rightarrow 3 \text{ and } 3 \rightarrow 1.

The number of cycles is {1}, the cardinality of the set is {3}, and there are {2} inversions. The inversions are {1,3} and {2,3}. The theorem works, since { 1 \equiv 3 + 2 \bmod 2}.

If we think of the cardinality of {S} as known, then the theorem really says:

\displaystyle  \ulcorner \mathsf{inv}(\pi) \bmod 2 \urcorner \text{ determines the value of } \ulcorner \mathsf{cycle}(\pi) \bmod 2 \urcorner.

The reason I am excited by the theorem is that computing { \mathsf{inv}(\pi) \bmod 2 } seems, to me, to be a much less sequential task, than the usual method of determining the cyclic structure of a permutation:

{\bullet} The usual method is sequential. It follows a point to another point and eventually determines its cyclic structure. Of course this method determines more than just the number of cycles modulo {2}: it gets the exact number of cycles. This method clearly is a sequential method, which does not seem to be parallelizable in any obvious manner.

{\bullet} The inversion method is easily made parallel. Have each “processor” take a pair of {x,y} from {S}, and then check whether they form an inversion: that is {x<y} and {\pi(x) > \pi(y)}. This all can be done in one parallel step. Then, the processors each report back to a central processor, who computes the total number of inversions modulo {2}.

Open Problems

Can we generalize the inversion method to count cycles modulo something other than {2}? Put another way: is there a parallel method for computing the number of cycles of a permutation modulo say {3}? Note, simply computing the number of inversions modulo {3} will not allow the determination of the number of cycles modulo {3} of a permutation. That was one of the results of the earlier post.

Finally, can we use the inversion method to solve an open problem?

About these ads
18 Comments leave one →
  1. September 4, 2009 11:39 am

    My brain hurts. I’m just going to lie down for a while while I think about this one.

  2. rjlipton permalink*
    September 4, 2009 12:02 pm

    Was the post unclear? Am sorry if that happen.

  3. September 4, 2009 12:47 pm

    Just to clarify, it seems like you are asking for something like a ‘nice formula’ for such modular counting, right? Because it looks clear that counting the number of cycles can be done in parallel. (or are you wondering more about the precise parallel complexity?)

    (Each cycle is a strongly connected component, which can in parallel be identified with its minimal-index element; then we count the number of distinct elements via, say, parallel sorting.)

    Nice post, and thanks for sharing the great Lessons from Rota.

    • rjlipton permalink*
      September 4, 2009 12:50 pm

      Yes all can be done in parallel. The issue is can it be done with little work by each processor. So it is an efficiency issue.

      Thanks for Rota comment. His list is quite neat. The book is a lot of fun to read too.

      • September 4, 2009 9:56 pm

        Pardon me if I don’t quite understand, but it seems like the original method is O(n) and the parallel method O(n^2/p). Isn’t that less efficient?

  4. rjlipton permalink*
    September 5, 2009 8:34 am

    It is not the total number of operations that is key. It is the parallel time. Thus, the new method takes two steps, while the usual takes n steps. This is a huge difference in some complexity applications. This also means that we understand the structure of the problem more if we can see how to do the problem in few parallel steps. But, you are right about total cost.

  5. Thinh Nguyen permalink
    September 6, 2009 11:21 pm

    It seems that the “central processor” should be a tree-adder. It takes log(n^2) = O(log n) more steps. So, time complexity is O(n^2 / p + log n), as in the case, p = n^2, it is O(log n).

  6. Anon permalink
    September 18, 2009 9:13 am

    Suppose we define a directed graph on [n] where (i,j) is an edge iff (i,j) is an inversion. Then, this is a transitive acyclic graph, and so every cycle is actually a clique. So the number of edges (=inversions) in each clique is even since it is of the form k(k-1)/2. Therefore, the parity is determined by the number of cliques or equivalently the number of cycles. So the “reason” why parity seems to work (and mod3 does not) is because inversion is a binary relation.

  7. Anon permalink
    September 18, 2009 9:25 am

    Stupid mistake in my previous comment, but this seems to be fixable (one way or another :-)).

  8. Warren permalink
    November 30, 2009 7:27 pm

    Create an _undirected_ graph G with an edge from u to v whenever pi(u) = v or pi(v) = u. The connected components of G are the cycles of pi. Connected components can be computed in O(log n) time using O(m / log n) processors (see Gazit, FOCS ’86, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4568240). Counting the components created can be done fairly easily in time O(log n) time using O(n / log n) processors. So the problem of counting the number of cycles in a permutation can be solved in time O(log n) using O(n / log n) processors. With the number of cycles in hand, the number of cycles modulo any desired base can be computed in constant time on one processor. Of course there’s probably a much simpler direct algorithm, but this reduction is sufficient to show the asymptotic complexity.

    RJLipton wrote:
    Thus, the new method takes two steps.
    What model of parallelism do you have in mind? In classic models such as the PRAM the step of counting how many processors say “I have an inversion” takes Theta(log n) time.

Trackbacks

  1. Counting Cycles of a Permutation in Parallel · ldfdc
  2. Math World | Counting Cycles of a Permutation in Parallel « Gödel's Lost Letter …
  3. The Curious History of the Schwartz-Zippel Lemma « Gödel’s Lost Letter and P=NP
  4. Promise Problems And TWOPATHS « Gödel’s Lost Letter and P=NP
  5. generated discreteness | Peter's ruminations

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,229 other followers