Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 stackoverflow.com 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
add comment

2 Answers 2

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

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
add comment

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
1  
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) –  sparkleshy Nov 30 '11 at 3:34
add comment

Your Answer

 
discard

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