# 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?

-

## migrated from stackoverflow.comJun 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.

-
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

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