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

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

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

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

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

Асимптотически вероятность расстройства близка к 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, является расстройством, но не циклом.

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

Как уже упоминал @FelixCQ, перетасовки, которые вы ищете, называются расстройствами. Построение равномерно распределенных случайным образом расстройств — нетривиальная задача, но в литературе известны некоторые результаты. Самый очевидный способ построения расстройств — это метод отбрасывания: вы генерируете равномерно распределенные случайным образом перестановки, используя алгоритм вроде Фишера-Йейтса, а затем отбрасываете перестановки с фиксированными точками. Среднее время выполнения этой процедуры равно 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. Использование 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 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 < 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<String,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);
        }

      }

    }