Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this problem:

Imagine you have a vector V, integers from 0 to 70000 -- sorted in ascending order Now you have a permutation P of that vector. Then you do V[P] "shuffling" the vector. If you keep doing V[P] (P never changes), V will eventually be sorted again in ascending order?

Is there a way you may know, a priori, how may shuffles you need?

share|improve this question

migrated from Jun 25 '11 at 11:15

This question came from our site for professional and enthusiast programmers.

I use Bogosort in all of my applications, because using anything else would be premature optimization. O(∞) is good enough for my users. – Carson Myers Jun 25 '11 at 14:23

Since "shuffling" is (by definition) random and has no memory of earlier runs (to always produce new permutations), you cannot be certain to ever reach the sorted state. Much less know how many repeats you might need.

share|improve this answer
well, but you can tell with a certain probability and deviation how long it will probably take – Falcon Jun 25 '11 at 13:00
-1: wrong (very forgivable: the question uses mathematical terminology that looks like ordinary words but isn't. The "shuffling" isn't random in the way you mean random) – naiad Nov 30 '11 at 3:34

Since the system has finitely many possible states (70000!), successive applications of the operation P must eventually revisit some state. And since P is reversible, the sequence cannot enter a cycle that doesn't include the starting state.

Just that's enough to prove that the vector will be sorted again within 70000! steps.

Now look at P. (I wish I knew if there were some standard mathematical terminology and/or symbols for this, but just bear with me.) P will carry an element through a circuit and back to its starting point with a certain period. All of the elements on the circuit have the same period. For instance, if P is [2 3 1 4] then the sequence looks like


The elements {1,2,3} have period 3, and {4} has period 1.

Now look at P = [2 3 1 5 4]:


The elements {1,2,3} have period 3, {4,5} have period 2, and the period of the whole permutation is the least common multiple of those periods, namely 6.

That tells us how long a given P will take to return the vector to its original state. So what's the longest period a permutation of N elements can have? We have to break N up into a1, a2, a3,... such that Σak=N, and LCD(ak) is maximized. This is an interesting problem and it's not immediately obvious to me what the answer is...

share|improve this answer
Cycle notation is the standard you're looking for. – Peter Taylor Jun 25 '11 at 15:26
@Peter Taylor: Cool, thanks! – Beta Jun 26 '11 at 19:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.