Подтвердить что ты не робот

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

Я хочу перетасовать список уникальных предметов, но не делаю случайного случайного перетасовки. Я должен быть уверен, что ни один элемент в перетасованном списке не будет находиться в том же месте, что и в исходном списке. Таким образом, если исходный список (A, B, C, D, E), этот результат будет ОК: (C, D, B, E, A), но это не будет: (C, E, A, D, B), поскольку "D" по-прежнему остается четвертым. Список будет содержать не более семи позиций. Крайняя эффективность - это не соображение. Я думаю, что эта модификация Fisher/Yates делает трюк, но я не могу доказать это математически:

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;
    }
}
4b9b3361

ОТВЕТЫ

Ответ 1

Вы ищете derangement ваших записей.

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

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

  • выбираем перестановку равномерно случайным образом
  • если он не имеет неподвижных точек, верните его
  • иначе повторить попытку

Асимптотически вероятность получения нарушения близка к 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, но только если он не создает фиксированную точку. Это немного длиннее для выполнения (из-за части отказа) и требует, чтобы вы могли проверить, находится ли запись в ее первоначальном месте или нет, но она имеет то преимущество, что она может производить все возможные нарушения (равномерно для этого материя).

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

Edit:

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

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

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

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

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

Ответ 2

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

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

Пусть 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. Использование longs работает для n до 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 Qaru (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);
        }

      }

    }

Ответ 3

В С++:

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]);
    }
}