алгоритм перемешивания только со случайными 0, 1

Я только что прочитал какой-то вопрос интервью в Интернете, и мне стало любопытно решение.

Проблема такая.

Дан список чисел и функция rand(0,1), которая возвращает случайное целое число от 0 до 1. Предоставьте алгоритм для случайной сортировки заданного списка на основе вывода функции rand(), которую следует вызвать. один раз для каждого числа в списке.

Кажется, просят сгенерировать случайное число только с 0 и 1 для перемешивания. И я придумал это решение.

int random(int array_index, int array size)
{
    return (array_index * 41 * (array_size + rand(0,1)) % array_size;
}

Но я чувствую, что этого недостаточно, так как это зависит от array_index.

У кого-нибудь есть лучший ответ на это?


random shuffle
person code animal    schedule 27.03.2012    source источник
comment
@sarnold 41 — просто случайное простое число. Я также рассматривал эту проблему как генерацию хэш-числа с меньшим коллизией, потому что мы не хотим генерировать повторяющиеся случайные числа. поэтому я использовал тактику из хеш-функции.   -  person code animal    schedule 27.03.2012
comment
Ах, достаточно справедливо. Обратите внимание, что если бы я был интервьюером, мне было бы так же любопытно узнать число ... веская причина приветствуется, но, возможно, должна была быть в комментарии или чем-то подобном.   -  person sarnold    schedule 27.03.2012
comment
@sarnold ну вот. хаха.   -  person code animal    schedule 27.03.2012
comment
Вы уверены, что это случайное целое число от 0 до 1?   -  person Lasse V. Karlsen    schedule 28.03.2012

Ответы (4)


arrow_upward
2
arrow_downward

Вам следует использовать алгоритм перемешивания Фишера-Йейтса, действительно случайное перемешивание за время O (n) (т. Е. «Вызывается один раз для каждого числа в списке»).

To shuffle an array a of n elements (indices 0..n-1):
    for i from n − 1 downto 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]
person Gareth Bowen    schedule 27.03.2012
comment
Не подходит для этой проблемы. случайный j не равен 0 ≤ j ≤ i. это 0 или 1. - person code animal; 27.03.2012
comment
Извините, я прочитал значение как случайное число от 0 до 1, которое можно легко преобразовать в 0 ≤ j ≤ i. - person Gareth Bowen; 27.03.2012

arrow_upward
0
arrow_downward

Я просто напишу свой на Ruby, так как я использую его больше.

def random_sort(numbers)
  sorted = Array.new
  index = 0
  numbers.each do |number|
    while rand(1)
      index += 1
    end

    index = index % numbers.length
    while numbers[index] != nil
      if index > numbers.length - 1
        index = 0
        continue
      end
      index += 1
    end

    sorted[index] = number
  end

  return sorted
end
person Mizuho    schedule 27.03.2012
comment
Вы выделяете sorted из блока numbers.each do |number|, что дает вам новый sorted[] для каждого отдельного номера. - person sarnold; 27.03.2012
comment
Я не знаком с Руби. Но вывод while rand(1) выглядит как index == 1. Я этого не понимаю. - person code animal; 27.03.2012
comment
@sarnold: Да, я действительно не заметил этого, пока печатал (так как я сделал это здесь). Собираюсь исправить это... не хочу выглядеть ПОЛНОСТЬЮ идиотским. Хотя выглядеть несколько идиотски для меня нормально. - person Mizuho; 27.03.2012

arrow_upward
0
arrow_downward

Пусть размер массива будет N

Чтобы случайным образом перетасовать список чисел, мы используем следующую стратегию.

For the first element we find a position out of the all available N choices.
Then, the second element has N-1 choices and so on. 
We generate the N! possible outcomes which ensures all are equi-probable.

Теперь, чтобы сгенерировать позицию случайным образом из (скажем, N) вариантов, мы делаем следующее; (Проделываем то же самое для N-1, N-2...)

Use Divide - And - Conquer.
First modify N to (Least Power of 2 >= N) Example: For N=5, modified_N=8 
Run rand(0,1) - 
If 0 - we the position is from 1 to modified_N/2
Else - the position is in modified_N/2+1 to modified_N

We do this recursively till we find the final position. 
If the final position is between N+1 and modified_N we run this procedure again.

Таким образом, мы можем найти 1 позицию за раз случайным образом, используя rand(0,1)

person Sajal Jain    schedule 13.09.2012
comment
Это похоже на генерацию битов целого числа с помощью rand(0,1) - person Sajal Jain; 13.09.2012

arrow_upward
0
arrow_downward

Предположим, у меня есть список из 10 элементов. Тогда их 10! = 3628800 различных способов его заказа.

Если я могу вызвать rand(0,1) только 10 раз, я могу сгенерировать только 2^10 = 1024 различных двоичных последовательностей.

Невозможно однозначно идентифицировать один из 10! упорядочивания с числом от 0 до 1024. То есть мы не можем выполнить беспристрастную перетасовку. (за исключением списков, содержащих более 3 элементов). Итак, теперь мы можем сосредоточиться на выборе простой в реализации необъективной перетасовки.

Например:

result = new List<int>();

foreach( int i in list )
{
  int r = rand(0,1);

  if( r == 0 )
    result.Prepend(i);
  else
    result.Append(i);
}
return result;

Это очень предвзято к размещению элементов дальше в списке от середины списка.

person Xantix    schedule 15.03.2013