Вариация Фишера Йейтса - PullRequest
Новая
       10

Вариация Фишера Йейтса

11 голосов
/ 14 января 2012

Классический Фишер Йейтс выглядит примерно так: 

void shuffle1(std::vector<int>& vec)
{
    int n = vec.size();
    for (int i = n - 1; i > 0; --i)
    {
        std::swap(vec[i], vec[rand() % (i + 1)]);
    }
}

Вчера я реализовал итерацию "назад" по ошибке: 

void shuffle2(std::vector<int>& vec)
{
    int n = vec.size();
    for (int i = 1; i < n; ++i)
    {
        std::swap(vec[i], vec[rand() % (i + 1)]);
    }
}

Эта версия чем-то хуже (или лучше) чем первый?Это искажает результирующие вероятности?

Ответы [ 2 ]

3 голосов
/ 14 января 2012

Да, это даже распределение при условии rand().Мы докажем это, показав, что каждый вход может генерировать каждую перестановку с равной вероятностью.

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

  0,1   //input where 0,1 represent indices
01  10  //output. Represents permutations of 01. It is clear that each one has equal probability

Для N у нас будут все перестановки для N-1,и случайным образом поменять местами последний символ для N 

    (N-1 0th permutation),N     .....          (N-1 Ith permutation),N ________________________  
      /              \                       /                   \                             \ 
0th permutation of N  1st permutation....   (I*N)th permutation   ((I*N)+1)th permutation .... (I*N)+(I-1)th permutation

Эта хреновая индукция должна привести к тому, что оно имеет равномерное распределение.

Пример:

N = 2:

  0,1
01  10 // these are the permutations. Each one has equal probability

N = 3: 

           0,1|2           // the | is used to separate characters that we will insert later
    01,2           10,2    // 01, 10 are permutations from N-1, 2 is the new value
 210 021 012   201 120 102 // these are the permutations, still equal probability

N = 4: (изогнут для удобства чтения) 

                                                           0,1|23

                                                       01,2|3  10,2|3

                                           012,3 021,3 210,3    102,3 120,3 201,3

0123 0132 0321 3230                                                                                  2013 2031 2310 3012
                    0213 0231 0312 3210                                          1203 1230 1302 3201
                                        2103 2130 2301 3102  1023 1032 1320 3021

и т. Д.

1 голос
/ 14 января 2012

Мне все в порядке (при условии, что rand ()% N беспристрастен, но это не так).Похоже, можно продемонстрировать, что каждая перестановка входных данных создается ровно 1 последовательностью случайных выборов, где каждый случайный выбор сбалансирован.

Сравните это с ошибочной реализацией, такой как 

for (int i = 0; i < v.size(); ++i) {
  swap(v[i], v[rand() % v.size()]);
}

Здесь вы можете видеть, что существует n n одинаково вероятных способов получения n!перестановок, и так как n n не делится поровну на n!где n> 2, некоторые из этих перестановок должны производиться чаще, чем другие.

...