0
$\begingroup$

I've read this similar question How to prove correctness of a shuffle algorithm? and I understand the answer. However I still couldn't figure out how to apply that inductive proof to a similar shuffle algorithm --- inside-out shuffling algorithm, which is as follows:

  for i from 0 to n − 1 do
      j ← random integer such that 0 ≤ j ≤ i
      if j ≠ i
          a[i] ← a[j]
      a[j] ← source[i]

source is the input array and a is the output array.

Another question I have is: would it be the same if I changed the code to the following:

  for i from 0 to n − 1 do
      j ← random integer such that 0 ≤ j ≤ i
      swap(a[j], a[i])

This is similar to the knuth algorithm except that it chooses a random element in the first i elements instead of last n-i elements. I have the feeling that they shouldn't both work, but I'm not sure.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Well, you'll need a different proof for a different algorithm. Can I suggest that you read about proof by induction, then try to formulate an induction predicate (an invariant) that holds at each iteration of the loop? It probably makes the most sense for you to spend some time trying to think through it, then show us what progress you've made and where you got stuck (e.g., what candidates for the loop invariant you've considered). Also, please ask about only one algorithm per post. If you want to two questions, or ask about two algorithms, you can post them in separate questions. $\endgroup$
    – D.W. ♦
    Sep 27, 2017 at 1:34
  • $\begingroup$ The second algorithm assumes that a is initialized with the numbers to be shuffled. The first one doesn't - it copies them from the array source. Otherwise they are identical. $\endgroup$
    – Yuval Filmus
    Sep 27, 2017 at 7:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.