Results 1 to 1 of 1

Math Help - Shuffling algorithm proof, please help!

  1. #1
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1

    Shuffling algorithm proof, please help!

    consider these two shuffling algorithms written in pseudo code, operating on a vector v with n elements:
    Code:
    for i = 1 to n, step 1
        j = random integer in the interval [i, n]
        if i 
    
    
    
    
    \neq j, swap elements in v on place i and place j
    end
    and
    Code:
    for i = 1 to n, step 1
        j = random integer in the interval [1, n]
        if i 
    
    
    
    
    \neq j, swap elements in v on place i and place j
    end
    To me it's obvious that the first algorithm will guarantee that all the n! different permutations of shuffeled vectors will have equally big chance to take place. But what about the second algorithm? Although I suspect that the same thing applies to this, I am not sure about it. Can someone please help me to prove whether this is true or not, if all n! permutations of the shuffeled vectors have equally big chance to take place or not, using the second algorithm? The only difference between the two algorithms is that the first one uses random numbers generated in the interval [i, n], while the second one uses random numbers generated in [1, n]. Oh, and about the generated numbers, all integers in the given interval has equaly big chance to be generated each time.
    Last edited by TriKri; October 14th 2008 at 05:07 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 11th 2010, 04:16 AM
  2. Big-Oh algorithm Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 12th 2010, 11:20 PM
  3. An exponential proof and an algorithm
    Posted in the Algebra Forum
    Replies: 6
    Last Post: December 15th 2008, 07:03 AM
  4. card shuffling effectiveness?
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: January 6th 2008, 05:50 PM
  5. Number Thry Card Shuffling
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 13th 2007, 10:36 PM

Search Tags


/mathhelpforum @mathhelpforum