# Keep permuting a vector until it is ordered

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?

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

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

``````ABCD
CABD
ABCD
``````

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

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

``````ABCDE
BCAED
CABDE
ABCED
CABED
ABCDE
``````

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

• Cycle notation is the standard you're looking for. Jun 25, 2011 at 15:26

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.

• well, but you can tell with a certain probability and deviation how long it will probably take Jun 25, 2011 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) Nov 30, 2011 at 3:34