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

Question

Я хочу перетасовать список уникальных предметов, но не делать совершенно случайную перестановку.Я должен быть уверен, что ни один элемент в перетасованном списке не находится в той же позиции, что и в исходном списке.Таким образом, если исходный список (A, B, C, D, E), этот результат будет в порядке: (C, D, B, E, A), но этот не будет: (C, E, A,D, B), потому что «D» по-прежнему четвертый пункт.В списке будет не более семи предметов.Чрезвычайная эффективность не является соображением.Я думаю, что эта модификация Фишера / Йейтса добилась цели, но я не могу доказать это математически:

function shuffle(data) {
    for (var i = 0; i < data.length - 1; i++) {
        var j = i + 1 + Math.floor(Math.random() * (data.length - i - 1));

        var temp = data[j];
        data[j] = data[i];
        data[i] = temp;
    }
}

Answer 1

Вы ищете отклонение ваших записей.

Прежде всего, ваш алгоритм работает в том смысле, что он выводит случайное отклонение, то есть перестановку без фиксированной точки.Однако у него есть огромный недостаток (который вы можете не возражать, но стоит иметь в виду): некоторые нарушения не могут быть получены с помощью вашего алгоритма .Другими словами, это дает нулевую вероятность некоторых возможных отклонений, поэтому результирующее распределение определенно не является равномерно случайным.

Одним из возможных решений, как предлагается в комментариях, было бы использование алгоритма отклонения:

• выбрать случайную перестановку равномерно
• , если она не имеет фиксированных точек, вернуть ее
• в противном случае повторить попытку

Асимптотически, вероятность получениярасстройство близко к 1/e = 0,3679 (как видно из статьи в Википедии).Это означает, что для получения расстройства вам нужно будет генерировать в среднем e = 2,718 перестановок, что довольно дорого.

Лучший способ сделать это - отклонить на каждом шаге алгоритма.В псевдокоде, что-то вроде этого (если исходный массив содержит i в позиции i, то есть a[i]==i):

for (i = 1 to n-1) {
   do {
      j = rand(i, n)   // random integer from i to n inclusive
   } while a[j] != i   // rejection part
   swap a[i] a[j]
}

Основное отличие от вашего алгоритма состоит в том, что мы разрешаем jбыть равным i, но только если оно не дает фиксированной точки.Он немного дольше выполняется (из-за части отклонения) и требует, чтобы вы были в состоянии проверить, находится ли запись в ее первоначальном месте или нет, но у него есть то преимущество, что он может вызывать все возможные помехи (равномерно, для этоговопрос).

Я предполагаю, что должны существовать алгоритмы неприятия, но я бы посчитал их менее простыми.

Редактировать:

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

Алгоритм, который производитЗдесь можно найти равномерно распределенные отклонения здесь , с некоторым контекстом проблемы, подробными объяснениями и анализом.

Второе редактирование:

Собственно ваш алгоритмизвестен как алгоритм Саттоло и, как известно, производит все циклы с равной вероятностью.Таким образом, любое нарушение, которое не является циклом, но продуктом нескольких непересекающихся циклов, не может быть получено с помощью алгоритма.Например, с четырьмя элементами перестановка, которая обменивает 1 и 2, а также 3 и 4, является отклонением, а не циклом.

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

Answer 2

Как уже упоминал @FelixCQ, нужные вам случайные тасовки называются degraments . Построение равномерно случайно распределенных расстройств не является тривиальной проблемой, но некоторые результаты известны в литературе. Самым очевидным способом построения отклонений является метод отклонения: вы генерируете равномерно случайно распределенные перестановки, используя алгоритм, такой как Фишер-Йейтс, а затем отклоняете перестановки с фиксированными точками. Среднее время выполнения этой процедуры составляет e * n + o (n), где e - постоянная Эйлера 2.71828 ... Это, вероятно, сработает в вашем случае.

Другим основным подходом к генерации нарушений является использование рекурсивного алгоритма. Однако, в отличие от Фишера-Йейтса, у нас есть две ветви к алгоритму: последний элемент в списке может быть заменен другим элементом (т. Е. Частью двухтактного ) или может быть частью больший цикл. Таким образом, на каждом этапе рекурсивный алгоритм должен разветвляться, чтобы генерировать все возможные отклонения. Кроме того, решение о том, брать ли одну ветку или другую, должно приниматься с правильными вероятностями.

Пусть D (n) - количество отклонений от n предметов. На каждом этапе количество ветвей, переводящих последний элемент в два цикла, составляет (n-1) D (n-2), а количество ветвей, переводящих последний элемент в большие циклы, составляет (n-1) D (n). -1). Это дает нам рекурсивный способ вычисления количества неисправностей, а именно D (n) = (n-1) (D (n-2) + D (n-1)), и дает нам вероятность разветвления до двух цикл на любой стадии, а именно (n-1) D (n-2) / D (n-1).

Теперь мы можем построить неисправности, решив, к какому типу цикла принадлежит последний элемент, поменяв последний элемент на одну из n-1 других позиций и повторив. Однако может быть сложно отслеживать все ветвления, поэтому в 2008 году некоторые исследователи разработали оптимизированный алгоритм с использованием этих идей. Вы можете увидеть прохождение в http://www.cs.upc.edu/~conrado/research/talks/analco08.pdf. Время выполнения алгоритма пропорционально 2n + O (log ^ 2 n), что на 36% больше скорости по сравнению с методом отклонения.

Я реализовал их алгоритм на Java. Использование long работает до 22 или около того. Использование BigIntegers расширяет алгоритм до n = 170 или около того. Использование BigIntegers и BigDecimals расширяет алгоритм до n = 40000 или около того (ограничение зависит от использования памяти в остальной части программы).

    package io.github.edoolittle.combinatorics;

    import java.math.BigInteger;
    import java.math.BigDecimal;
    import java.math.MathContext;
    import java.util.Random;
    import java.util.HashMap;
    import java.util.TreeMap;

    public final class Derangements {

      // cache calculated values to speed up recursive algorithm
      private static HashMap<Integer,BigInteger> numberOfDerangementsMap 
        = new HashMap<Integer,BigInteger>();
      private static int greatestNCached = -1;

      // load numberOfDerangementsMap with initial values D(0)=1 and D(1)=0
      static {
        numberOfDerangementsMap.put(0,BigInteger.valueOf(1));
        numberOfDerangementsMap.put(1,BigInteger.valueOf(0));
        greatestNCached = 1;
      }

      private static Random rand = new Random();

      // private default constructor so class isn't accidentally instantiated
      private Derangements() { }

      public static BigInteger numberOfDerangements(int n)
        throws IllegalArgumentException {
        if (numberOfDerangementsMap.containsKey(n)) {
          return numberOfDerangementsMap.get(n);
        } else if (n>=2) {
          // pre-load the cache to avoid stack overflow (occurs near n=5000)
          for (int i=greatestNCached+1; i<n; i++) numberOfDerangements(i);
          greatestNCached = n-1;
          // recursion for derangements: D(n) = (n-1)*(D(n-1) + D(n-2))
          BigInteger Dn_1 = numberOfDerangements(n-1);
          BigInteger Dn_2 = numberOfDerangements(n-2);
          BigInteger Dn = (Dn_1.add(Dn_2)).multiply(BigInteger.valueOf(n-1));
          numberOfDerangementsMap.put(n,Dn);
          greatestNCached = n;
          return Dn;
        } else {
          throw new IllegalArgumentException("argument must be >= 0 but was " + n);
        }
      }

      public static int[] randomDerangement(int n)
        throws IllegalArgumentException {

        if (n<2)
          throw new IllegalArgumentException("argument must be >= 2 but was " + n);

        int[] result = new int[n];
        boolean[] mark = new boolean[n];

        for (int i=0; i<n; i++) {
          result[i] = i;
          mark[i] = false;
        }
        int unmarked = n;

        for (int i=n-1; i>=0; i--) {
          if (unmarked<2) break; // can't move anything else
          if (mark[i]) continue; // can't move item at i if marked

          // use the rejection method to generate random unmarked index j &lt i;
          // this could be replaced by more straightforward technique
          int j;
          while (mark[j=rand.nextInt(i)]);

          // swap two elements of the array
          int temp = result[i];
          result[i] = result[j];
          result[j] = temp;

          // mark position j as end of cycle with probability (u-1)D(u-2)/D(u)
          double probability 
        = (new BigDecimal(numberOfDerangements(unmarked-2))).
        multiply(new BigDecimal(unmarked-1)).
        divide(new BigDecimal(numberOfDerangements(unmarked)),
               MathContext.DECIMAL64).doubleValue();
          if (rand.nextDouble() < probability) {
        mark[j] = true;
        unmarked--;
          }

          // position i now becomes out of play so we could mark it
          //mark[i] = true;
          // but we don't need to because loop won't touch it from now on
          // however we do have to decrement unmarked
          unmarked--;
        }

        return result;
      }

      // unit tests
      public static void main(String[] args) {
        // test derangement numbers D(i)
        for (int i=0; i<100; i++) {
          System.out.println("D(" + i + ") = " + numberOfDerangements(i));
        }
        System.out.println();

        // test quantity (u-1)D_(u-2)/D_u for overflow, inaccuracy
        for (int u=2; u<100; u++) {
          double d = numberOfDerangements(u-2).doubleValue() * (u-1) /
        numberOfDerangements(u).doubleValue();
          System.out.println((u-1) + " * D(" + (u-2) + ") / D(" + u + ") = " + d);
        }

        System.out.println();

        // test derangements for correctness, uniform distribution
        int size = 5;
        long reps = 10000000;
        TreeMap<String,Integer> countMap = new TreeMap&ltString,Integer>();
        System.out.println("Derangement\tCount");
        System.out.println("-----------\t-----");
        for (long rep = 0; rep < reps; rep++) {
          int[] d = randomDerangement(size);
          String s = "";
          String sep = "";
          if (size > 10) sep = " ";
          for (int i=0; i<d.length; i++) {
        s += d[i] + sep;
          }

          if (countMap.containsKey(s)) {
        countMap.put(s,countMap.get(s)+1);
          } else {
        countMap.put(s,1);
          }
        }

        for (String key : countMap.keySet()) {
          System.out.println(key + "\t\t" + countMap.get(key));
        }

        System.out.println();

        // large random derangement
        int size1 = 1000;
        System.out.println("Random derangement of " + size1 + " elements:");
        int[] d1 = randomDerangement(size1);
        for (int i=0; i<d1.length; i++) {
          System.out.print(d1[i] + " ");
        }

        System.out.println();
        System.out.println();

        System.out.println("We start to run into memory issues around u=40000:");
        {
          // increase this number from 40000 to around 50000 to trigger
          // out of memory-type exceptions
          int u = 40003;
          BigDecimal d = (new BigDecimal(numberOfDerangements(u-2))).
        multiply(new BigDecimal(u-1)).
        divide(new BigDecimal(numberOfDerangements(u)),MathContext.DECIMAL64);
          System.out.println((u-1) + " * D(" + (u-2) + ") / D(" + u + ") = " + d);
        }

      }

    }

Answer 3

В C ++:

template <class T> void shuffle(std::vector<T>&arr)
{
    int size = arr.size();

    for (auto i = 1; i < size; i++)
    {
        int n = rand() % (size - i) + i;
        std::swap(arr[i-1], arr[n]);
    }
}