隨機播放列表，確保沒有項目保持在同一位置

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

     } 

    }