лучший алгоритм для перетасовки массива

Question

У меня есть массив s = {'ACA', 'BBC', 'CKA', ...};

Я хочу перетасовать. Поэтому я создаю список A = {1,2,3,4 ..} и список B = {1,2,3,4, ...}

Затем я перетасовываю два списка. random.shuffle (А) random.shuffle (Б)

, наконец, я поменять местами с [A [0]] с [ы B [0]], своп с [A [1]] с S [B [1]] .....

Является ли этот алгоритм произвольной перестановкой s? Является ли это случайным? Предполагая, что random.shuffle производит случайные достаточно перестановки A и B.

Answer 1

Для использования Фишера - Йетс (Кнут) перемешайте с массивом индекса, инициализировать один массив индексов A как

for (int i = 0; i < n; i++) A[i] = /* random integer in 0..i */; 

, а затем делать свопы как

for (int i = 0; i < n; i++) swap(&s[A[i]], &s[i]); 

Ваш алгоритм не порождают равномерные случайные подстановки. При n = 2 возможности для A и B равны

A = {0, 1}; B = {0, 1}; 
A = {0, 1}; B = {1, 0}; 
A = {1, 0}; B = {0, 1}; 
A = {1, 0}; B = {1, 0}; 

Ничего из этого не влияет на начальную перестановку; либо оба элемента меняются местами, либо один и тот же нетривиальный своп повторяется дважды, отменяя его эффект.

Answer 2

Knut's shuffle - простой и эффективный способ перетасовки массива. Вам не нужны дополнительные массивы индексов. Есть ли какая-то особая причина для их использования?