shuffle.rb

# Fisher-Yates shuffle
# the wiki shows two examples
# https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

# pencil-and-paper method
# 1. Duplicate the array and shuffle the duplicate instead (we call the duplicate `input_array`)
# 2. Generate a random number between 0 and (length of the array - 1) (we call the number `random_position`)
# 3. Take an element at position `random_position` in the `input_array`, and put into another array
# 4. Repeat 2-3 until `input_array` has nothing left

def shuffle(input_array)
  input_array = input_array.dup # (1)
  result_array = []
  until input_array.length == 0 # (4)
    range = 0..(input_array.length - 1) 
    random_position = rand(range) # (2)
    result_array << input_array.delete_at(random_position) # (3)
  end
  
  result_array
end

shuffle_modern.rb

# its good to try out different ways to shuffle :)
# https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modern_method

# modern method
# 1. Duplicate the array and shuffle the duplicate instead (we call the duplicate `arr`)
# 2. Generate a random number between 0 and (length of the array - 1) (we call the number `random`)
# 3. If `random` is the last position of the array, take out and put right into the array, and jump to step 2
# 4. Store the element at position `random` somewhere
# 5. Take the last element and put it at position `random`
# 6. Take the stored element and put into the new array
# 7. Jump back to 2 and continue until `arr` has one element, then merge the last element and the new array


def shuffle(input_arr)
  input_arr = input_arr.dup #(1)
  result_arr = []
  
  until input_arr.length < 2
    upper_limit = input_arr.length - 1
    range = 0..upper_limit
    random_position = rand(range) #(2)
    last_number = input_arr.pop
    
    if upper_limit == random_position
      result_arr << last_number #(3)
    else
      el = input_arr[random_position] #(4)
      input_arr[random_position] = last_number #(5)
      result_arr << el #(6)
    end
  end
  
  return input_arr + result_arr
end

shuffle_shorter.rb

# shorter version
def shuffle(array)
  array = array.dup
  result_arr = []
  result_arr << array.delete_at(rand(array.length)) until array.length == 0
  result_arr
end
  
# even shorter
# Array.new uses the block for each element it generates
# Array.new(3) { "hello" } gives ["hello","hello","hello"]
def shuffle(input_arr)
  input_arr = input_arr.dup
  Array.new(input_arr.length) { input_arr.delete_at(rand(input_arr.length)) }
end