随机列表,确保没有项目保持在同一位置

Question

我想要洗牌一系列独特的项目,但不要做一个完全随机的洗牌.我需要确保混洗列表中的元素与原始列表中的位置不同.因此,如果原始列表是(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;
    }
}

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,但前提是它不产生固定点.执行时间稍长(由于拒绝部分),并且要求您能够检查条目是否在原始位置,但它的优点是它可以产生所有可能的紊乱(统一,为此物).

我猜测应该存在非拒绝算法,但我认为它们不那么简单.

编辑:

我的算法实际上很糟糕:你仍然有可能以最后一点未洗牌结束,并且分布根本不是随机的,请参阅模拟的边际分布:

可以在此处找到产生均匀分布的紊乱的算法,其中包含问题的一些背景,详尽的解释和分析.

第二编辑:

实际上你的算法被称为Sattolo算法,并且已知以相等的概率产生所有周期.因此,使用该算法不能获得任何不是循环而是几个不相交循环的乘积的紊乱.例如,对于四个元素,交换1和2以及3和4的排列是紊乱而不是循环.

如果你不介意只获得周期,那么Sattolo的算法是要走的路,它实际上要比任何统一的紊乱算法快得多,因为不需要拒绝.

Answer 2

正如@FelixCQ 所提到的，您正在寻找的洗牌称为derangements。构建均匀随机分布的紊乱不是一个微不足道的问题，但一些结果在文献中是已知的。构造混乱的最明显的方法是拒绝方法：使用类似 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 适用于最多 22 个左右的 n。使用 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);
        }

      }

    }