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

Question

我想随机播放唯一项目列表，但不会执行完全随机的随机播放。我需要确保混洗列表中没有元素与原始列表中的位置相同。 （C，D，B，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

您正在寻找您的条目derangement。

首先，你的算法的工作原理是它输出一个随机排列，即一个没有固定点的排列。然而它有一个巨大的缺陷（你可能不介意，但值得记住）：你的算法无法获得一些紊乱。换句话说，它给出了一些可能的紊乱的概率为零，所以得到的分布绝对不是一致随机的。

一个可能的解决方案，在意见提出，将使用丢弃算法：

• 挑排列均匀随机
• 如果HAX没有固定点，返回它
• 否则重试

渐近地说，获得紊乱的概率接近于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，但只有当它不产生固定点。执行的时间稍长（由于拒绝部分），并要求您能够检查一个条目是否在原来的位置，但它的优点是它可以产生一切可能的紊乱（统一，为此物）。

我猜不可拒绝算法应该存在，但我相信他们不那么直截了当。

编辑：

我的算法实际上是不好的：你仍然有最后一点unshuffled结束的机会，且分布不是随机可言，看到一个模拟的边缘分布：

一个产生均匀分布紊乱的算法可以在here找到，在问题的某些上下文中有详细的解释和分析。

第二个编辑：

其实你的算法被称为Sattolo's algorithm，并已知会产生所有周期的概率相等。所以任何不是循环而是几个不相交循环的产物的紊乱都不能通过该算法获得。例如，有四个元素，交换1和2以及3和4的排列是紊乱，但不是循环。

如果你不介意只获取周期，那么Sattolo的算法是要走的路，它实际上比任何统一的排列算法快得多，因为不需要排斥。

Answer 2

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

Answer 3

正如@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中实现了他们的算法。使用长期股票可以支撑22点左右。使用BigIntegers将算法扩展到n = 170左右。使用BigInteger和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&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); 
     } 

     } 

    }