Trộn danh sách, đảm bảo rằng không có mục nào ở cùng một vị trí

Question

Tôi muốn trộn một danh sách các mục duy nhất, nhưng không thực hiện ngẫu nhiên ngẫu nhiên. Tôi cần phải chắc chắn rằng không có yếu tố nào trong danh sách xáo trộn ở cùng vị trí như trong danh sách gốc. Vì vậy, nếu danh sách ban đầu là (A, B, C, D, E), kết quả này sẽ là OK: (C, D, B, E, A), nhưng điều này sẽ không: (C, E, A, D, B) vì "D" vẫn là mục thứ tư. Danh sách sẽ có tối đa bảy mục. Hiệu quả cực đoan không phải là một sự cân nhắc. Tôi nghĩ rằng thay đổi này để Fisher/Yates hiện các trick, nhưng tôi không thể chứng minh điều đó về mặt toán học:

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

Bạn đang tìm kiếm một derangement các mục của bạn.

Trước hết, thuật toán của bạn hoạt động theo nghĩa là nó tạo ra một sự xáo trộn ngẫu nhiên, nghĩa là một hoán vị không có điểm cố định. Tuy nhiên nó có một lỗ hổng rất lớn (mà bạn có thể không nhớ, nhưng đáng lưu ý): một số chuyển động không thể có được với thuật toán của bạn. Nói cách khác, nó đưa ra xác suất bằng không cho một số sai lệch có thể xảy ra, do đó phân phối kết quả chắc chắn không phải ngẫu nhiên thống nhất.

Một giải pháp khả thi, như đề xuất trong các ý kiến, sẽ được sử dụng một thuật toán từ chối:

• chọn một hoán vị đồng đều một cách ngẫu nhiên
• nếu nó HAX không có điểm cố định, trả lại
• khác thử lại

Có nghĩa là xác suất có được sự xáo trộn gần 1/e = 0.3679 (như đã thấy trong bài viết wikipedia). Điều đó có nghĩa là để có được sự xáo trộn, bạn sẽ cần tạo ra mức trung bình là e = 2.718 hoán vị, điều này khá tốn kém.

Cách tốt hơn để làm điều đó là từ chối ở mỗi bước của thuật toán. Trong giả, một cái gì đó như thế này (giả sử mảng ban đầu chứa i ở vị trí i, tức là 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] 
} 

Sự khác biệt chính từ thuật toán của bạn là chúng ta cho phép j được bằng i, nhưng chỉ khi nó không tạo ra một điểm cố định. Nó hơi dài hơn để thực thi (do phần từ chối) và yêu cầu bạn có thể kiểm tra xem mục nhập có ở vị trí ban đầu hay không, nhưng có lợi thế là nó có thể tạo ra mọi sự xáo trộn có thể (thống nhất, cho rằng vấn đề).

Tôi đoán các thuật toán không từ chối nên tồn tại, nhưng tôi tin rằng chúng sẽ kém thẳng về phía trước.

Edit:

thuật toán của tôi là thực sự xấu: bạn vẫn có cơ hội kết thúc với điểm cuối cùng unshuffled, và sự phân bố không phải là ngẫu nhiên ở tất cả, nhìn thấy sự phân bố biên của một mô phỏng:

Thuật toán tạo ra các biến dạng phân bố thống nhất có thể được tìm thấy here, với một số ngữ cảnh về vấn đề, giải thích và phân tích kỹ lưỡng.

Sửa Thứ hai:

Thực ra thuật toán của bạn được gọi là Sattolo's algorithm, và được biết đến để sản xuất tất cả các chu kỳ với xác suất bằng nhau. Vì vậy, bất kỳ derangement mà không phải là một chu kỳ nhưng một sản phẩm của một số chu kỳ disjoint không thể thu được với các thuật toán. Ví dụ, với bốn yếu tố, hoán vị trao đổi 1 và 2, và 3 và 4 là một sự xáo trộn nhưng không phải là một chu kỳ.

Nếu bạn không nhớ chỉ có chu kỳ, thuật toán của Sattolo là con đường để đi, nó thực sự nhanh hơn nhiều so với thuật toán derangement thống nhất, vì không cần từ chối.

Answer 2

Trong 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

Như @FelixCQ đã đề cập, các shuffles bạn đang tìm kiếm được gọi là Loạn. Việc xây dựng những chuyển động phân bố ngẫu nhiên thống nhất không phải là một vấn đề tầm thường, nhưng một số kết quả được biết đến trong văn học. Cách rõ ràng nhất để xây dựng các quấy rối là bằng phương pháp từ chối: bạn tạo các hoán vị được phân phối ngẫu nhiên một cách thống nhất bằng cách sử dụng một thuật toán như Fisher-Yates và sau đó loại bỏ các hoán vị với các điểm cố định. Thời gian chạy trung bình của quy trình đó là e * n + o (n) trong đó e là hằng số của Euler 2.71828 ... Điều đó có thể hoạt động trong trường hợp của bạn.

Cách tiếp cận lớn khác để tạo Loạn là sử dụng một thuật toán đệ quy. Tuy nhiên, không giống như Fisher-Yates, chúng tôi có hai chi nhánh để các thuật toán: mục cuối cùng trong danh sách có thể được hoán đổi với một mục (ví dụ, một phần của một hai chu kỳ), hoặc có thể là một phần của một chu kỳ lớn hơn. Vì vậy, ở mỗi bước, thuật toán đệ quy phải nhánh để tạo ra tất cả các biến dạng có thể xảy ra. Hơn nữa, quyết định có nên lấy một nhánh hay nhánh kia phải được thực hiện với xác suất chính xác hay không.

Hãy D (n) là số Loạn các mặt hàng n. Ở mỗi giai đoạn, số lượng các chi nhánh lấy vật phẩm cuối cùng đến hai chu kỳ là (n-1) D (n-2), và số lượng nhánh lấy vật phẩm cuối cùng đến chu kỳ lớn hơn là (n-1) D (n -1). Điều này cho chúng ta một cách đệ quy để tính toán số lần chuyển động, cụ thể là D (n) = (n-1) (D (n-2) + D (n-1)), và cho chúng ta khả năng phân nhánh thành hai -máy ở bất kỳ giai đoạn nào, cụ thể là (n-1) D (n-2)/D (n-1).

Bây giờ chúng ta có thể xây dựng Loạn bằng cách quyết định mà loại chu kỳ yếu tố cuối cùng thuộc về, trao đổi các yếu tố cuối cùng để một trong những n-1 vị trí khác, và lặp lại. Nó có thể phức tạp để theo dõi tất cả các nhánh, tuy nhiên, vì vậy trong năm 2008 một số nhà nghiên cứu đã phát triển một thuật toán sắp xếp hợp lý bằng cách sử dụng những ý tưởng đó. Bạn có thể xem hướng dẫn tại http://www.cs.upc.edu/~conrado/research/talks/analco08.pdf. Thời gian chạy của thuật toán tỷ lệ với 2n + O (log^2 n), cải thiện 36% tốc độ trên phương pháp loại bỏ.

tôi đã thực hiện thuật toán của họ trong Java. Sử dụng longs làm việc cho n lên đến 22 hoặc lâu hơn. Sử dụng BigIntegers mở rộng thuật toán thành n = 170 hoặc hơn. Sử dụng BigIntegers và BigDecimals mở rộng thuật toán thành n = 40000 hoặc hơn (giới hạn phụ thuộc vào việc sử dụng bộ nhớ trong phần còn lại của chương trình).

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

     } 

    }