Random ный список чисел.

← →
ЕщеОдинКакжеНадоели (2012-11-16 21:21) [0]

Есть числа в массиве (списке), не повторяются. (Хотя неважно)
Нужно их перемешать в случайном порядке, т.е.
есть некая функция, которая возвращает random"ое число из этого списка, потом возвращает другое, но не то, что выпадало раньше.

Как это сделать?
Похоже на лототрон в Золотом Ключе. :)

← →
RWolf © (2012-11-16 21:29) [1]

ну так и сделать — перемешать в случайном порядке.
а возвращать уже перемешанные, по очереди.

← →
ЕщеОдинКакжеНадоели (2012-11-16 21:30) [2]

> RWolf © (16.11.12 21:29) [1]

А как перемешивать, я не знаю?

← →
Dimka Maslov © (2012-11-16 21:34) [3]

делаем Swap для двух случайно взятых индексов. n² раз.

← →
Sha © (2012-11-16 21:54) [4]

> Dimka Maslov © (16.11.12 21:34) [3]
> делаем Swap для двух случайно взятых индексов. n² раз.

как это работает для n=2?

← →
Sha © (2012-11-16 21:56) [5]

> ЕщеОдинКакжеНадоели (16.11.12 21:21)

1. выбираем случайный из n
2. выбираем случайный из оставшихся n-1
дальше сам

← →
AV © (2012-11-16 21:58) [6]

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

← →
TUser © (2012-11-16 21:59) [7]

for i := 0 to n-1 do
swap(i,random(n));

← →
Dimka Maslov © (2012-11-16 22:27) [8]

> как это работает для n=2?

никак. и для n=1 тоже никак.

← →
Sha © (2012-11-16 22:36) [9]

> Dimka Maslov © (16.11.12 22:27) [8]

a для n=3?

← →
Sha © (2012-11-16 22:36) [10]

> TUser © (16.11.12 21:59) [7]

а доказать?

← →
Inovet © (2012-11-16 22:39) [11]

> [6] AV © (16.11.12 21:58)
> берем случайное из из всего интервала, показываем, меняем с последним

А так не получится, что одни сильнее перемешаются, чем другие? Тогда уж вытаскивать/помечать случайное.

← →
AV © (2012-11-16 22:50) [12]

> Inovet © (16.11.12 22:39) [11]
А так не получится, что одни сильнее перемешаются, чем другие?

случайно выбрать из упорядоченного vs случайно выбрать из все более перемешанного с каждой итерацией
на вскидку, это не должно иметь значения.

← →
MBo © (2012-11-16 22:50) [13]

http://en.wikipedia.org/wiki/Fisher–Yates_shuffle

← →
MBo © (2012-11-16 22:56) [14]

по-русски:
http://qps.ru/RYDwI

← →
Sha © (2012-11-16 22:56) [15]

> Inovet © (16.11.12 22:39) [11]
> AV © (16.11.12 22:50) [12]

эти варианты равносильны

← →
Sha © (2012-11-16 23:08) [16]

> MBo © (16.11.12 22:56) [14]
> по-русски:

че-то намудрили там по-русски не по-русски,
по-мне так гораздо очевиднее цикл крутить наоборот

← →
Inovet © (2012-11-16 23:20) [17]

> [15] Sha © (16.11.12 22:56)
> эти варианты равносильны

При разном результате. Ну рандом. После первого раза, последующие не влияют на случайность.

> [18] Sha © (16.11.12 23:32)
> абсолютно равносильны

Я ыот об этом: при swap i-тый оказывается в случайной позиции (0..i-1), при сдвиге в i-1.

> Inovet © (16.11.12 23:58) [19]

это понятно,
однако для каждого кортежа одного алгоритма можно указать,
при каком условии второй алгоритм получит тот же кортеж

> Нужно их перемешать в случайном порядке, т.е.
> есть некая функция, которая возвращает random"ое число из
> этого списка,

На фига таблицу-то перемешивать??????????????????

> a для n=3?

Прекрасно будет работать. Девять случайных перестановок всяко перемешают список из трёх элементов

>Девять случайных перестановок всяко перемешают список из трёх элементов
Вот только перестановки будут неравновероятными

> Вот только перестановки будут неравновероятными

А и пёс бы с ими. Мне лично хватает.

>А и пёс бы с ими. Мне лично хватает.
Но ведь можно сделать равномерно за n перестановок

Random ный список чисел. Найти похожие ветки