помогите пожалуйста с моим кодом "shuffle" в ruby

Question

это вопрос

В случайном порядке. Теперь, когда вы закончили новый алгоритм сортировки, как насчет напротив? Напишите метод случайного принимает массив и возвращает полностью перемешанная версия. Как всегда, вы хочу проверить это, но тестирование это хитрее: как вы можете проверить, чтобы сделать уверен, что вы получаете идеальный перетасовать? Что бы вы даже сказали идеальным было бы перемешать? Теперь тест для это.

Это мой код ответа:

def shuffle arr
    x = arr.length
while x != 0
        new_arr = []
    rand_arr = (rand(x))
    x--
    new_arr.push rand_arr
    arr.pop rand_arr
end

new_arr

end

puts (shuffle ([1,2,3]))

Какие у меня ошибки? Почему этот код не работает?

Answer 1

Вот более краткий способ написать:

def shuffle(arr)
  new_arr = []

  while (arr.any?) do 
    new_arr << arr.delete_at(rand(arr.length))
  end

  new_arr
end

И некоторые тесты:

5.times do
  puts shuffle((1..5).to_a).join(',')
end

>> 4,2,1,3,5
>> 3,2,1,4,5
>> 4,2,5,1,3
>> 5,2,1,4,3
>> 4,3,1,5,2

Answer 2

Вот гораздо более рубиновая версия:

class Array
  def shuffle!
    size.downto(1) { |n| push delete_at(rand(n)) }
    self
  end
end

puts [1,2,3].shuffle!

Answer 3

Помимо незначительных других ошибок, вы, похоже, не понимаете, что делают pop и push (взятие или добавление некоторых элементов из конца массива).

Вы, вероятно, пытаетесь написать что-то вроде ниже.

def shuffle arr
    x = arr.length
    new_arr = []
    while x != 0
        randpos = rand(x)
        x = x-1
        item = arr[randpos]
        new_arr.push item
        arr[randpos] = arr[x]
        arr.pop
    end

    new_arr

end

puts (shuffle ([1,2,3]))

Answer 4

Ваши индексы перепутаны с вашими значениями. Когда вы делаете new_arr.push rand_arr, вы помещаете любой случайный индекс в качестве значения в конце new_arr. То, что вы хотели сделать, это new_arr.push arr[rand_arr], где arr[rand_arr] - это значение индекса rand_arr в arr.

Answer 5

Вариант ответа Марка Томаса. Его алгоритм может быть довольно медленным с большим массивом из-за производительности операций удаления.

class Array
  def shuffle!
    size.downto(1) do |n|
       index=rand(n)
       # swap elements at index and the end
       self[index], self[size-1] = self[size-1],self[index]
    end
    self
  end
end

puts [1,2,3].shuffle!

Этот алгоритм O (размер), а алгоритм Марка O (размер ^ 2). На моем компьютере ответ Марка занимает 400 секунд, чтобы перетасовать массив из 1 000 000 элементов на моем компьютере, по сравнению с 0,5 секунды для моего метода.

Answer 6

В Ruby 1.8.7 и 1.9.2 есть встроенный метод Array # shuffle.