Należy przetasować listę, upewniając się, że żaden przedmiot nie został w tej samej pozycji.

Question

Chcę przetasować listę unikatowych przedmiotów, ale nie losować losowo. Muszę mieć pewność, że żaden element na przetasowanej liście nie znajduje się na tej samej pozycji co na oryginalnej liście. Tak więc, jeśli oryginalna lista jest (A, B, C, D, E), wynik ten byłby OK: (C, D, B, E, A), ale ten nie byłby: (C, E, A, D, B), ponieważ "D" jest nadal czwartym elementem. Lista będzie zawierać maksymalnie siedem pozycji. Ekstremalna wydajność nie jest brana pod uwagę. Myślę, że ta modyfikacja Fisher/Yates załatwia sprawę, ale nie mogę tego udowodnić matematycznie:

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

Ty szukasz derangement swoich wpisów.

Po pierwsze, twój algorytm działa w tym sensie, że wysyła losowe zakłócenie, tj. Permutację bez stałego punktu. Jednak ma on ogromną wadę (której możesz nie mieć nic przeciwko, ale warto o tym pamiętać): niektórych zakłóceń nie można uzyskać za pomocą algorytmu. Innymi słowy, daje prawdopodobieństwo zerowe niektórym możliwym zakłóceniom, więc wynikowy rozkład nie jest zdecydowanie losowy.

Jednym z możliwych rozwiązań, jak zasugerowano w komentarzach, byłoby użycie algorytmu odrzucenia:

• wybrać permutacji równomiernie losowo
• jeśli hax ma stałych punktów, zwrócić go
• inaczej Ponów próbę:

Asymptotycznie prawdopodobieństwo uzyskania zmiany jest bliskie 1/e = 0,3767 (zgodnie z artykułem wikipedii). Co oznacza, że ​​aby uzyskać zmianę, trzeba wygenerować średnią permutacji e = 2,718, co jest dość kosztowne.

Lepszym sposobem na to byłoby odrzucenie na każdym etapie algorytmu. W Pseudokod, coś jak to (zakładając, że tablica oryginalna zawiera i w pozycji i, tj 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] 
} 

Główną różnicą od algorytmu jest to, że pozwalają j być równa i, ale tylko wtedy, gdy to robi nie wytwarzają stałego punktu. Jest nieco dłuższy do wykonania (ze względu na odrzucenie) i wymaga, abyś mógł sprawdzić, czy wpis jest na swoim oryginalnym miejscu, czy nie, ale ma tę zaletę, że może wytworzyć każde możliwe zakłócenie (jednolicie, dla tego materia).

Zgaduję, że algorytmy odrzucania nie powinny istnieć, ale uważam, że są mniej proste.

Edit:

Mój algorytm jest rzeczywiście zły: wciąż masz szansę kończąc na ostatnim punkcie unshuffled i dystrybucja nie jest przypadkowa w ogóle, zobacz marginalne rozkładów symulacji:

Algorytm generujący równomiernie rozłożone zakłócenia można znaleźć pod here, z pewnym kontekstem problemu, dokładnymi objaśnieniami i analizami.

Druga Edycja:

Właściwie Twój algorytm jest znany jako Sattolo's algorithm, i wiadomo, że produkują wszystkie cykle z jednakowym prawdopodobieństwem. Tak więc żadne zakłócenie, które nie jest cyklem, lecz produktem kilku rozłącznych cykli, nie może być uzyskane za pomocą algorytmu. Na przykład, w przypadku czterech elementów, permutacja, która wymienia 1 i 2 oraz 3 i 4, jest zaburzeniem, ale nie cyklem.

Jeśli nie masz nic przeciwko uzyskiwaniu tylko cykli, to algorytm Sattolo jest do zrobienia, w rzeczywistości jest znacznie szybszy niż jakikolwiek jednolity algorytm zakłóceń, ponieważ nie jest konieczne odrzucanie.

Answer 2

W 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

Jak @FelixCQ wspomniał, że tasuje szukasz nazywa zaburzeniami. Konstruowanie równomiernie rozłożonych losowo zakłóceń nie jest banalnym problemem, ale niektóre wyniki są znane w literaturze. Najbardziej oczywistym sposobem konstruowania zakłóceń jest metoda odrzucania: generujesz równomiernie losowo rozdzielone permutacje za pomocą algorytmu takiego jak Fisher-Yates, a następnie odrzucasz permutacje z ustalonymi punktami. Średni czas działania tej procedury to e * n + o (n), gdzie e jest stałą Eulera 2,71828 ... To prawdopodobnie zadziała w twoim przypadku.

Innym ważnym podejściem do generowania zakłóceń jest użycie algorytmu rekursywnego. Jednak w przeciwieństwie do Fishera-Yatesa mamy do algorytmu dwie gałęzie: ostatnią pozycję na liście można zamienić na inną pozycję (tj. Część z dwustopniowa) lub może być częścią większego cyklu. Tak więc na każdym etapie algorytm rekursywny musi rozgałęziać się, aby wygenerować wszystkie możliwe zakłócenia. Ponadto decyzja o przyjęciu jednego lub drugiego oddziału musi zostać podjęta z prawymi prawdopodobieństwami.

Niech D (n) będzie liczbą zakłóceń n pozycji. Na każdym etapie liczba odgałęzień przyjmujących ostatnią pozycję do dwóch cykli wynosi (n-1) D (n-2), a liczba odgałęzień przyjmujących ostatni element do większych cykli to (n-1) D (n -1). To daje nam rekursywny sposób obliczania liczby zakłóceń, mianowicie D (n) = (n-1) (D (n-2) + D (n-1)) i daje nam prawdopodobieństwo rozgałęzienia do dwóch -kolekcja na dowolnym etapie, a mianowicie (n-1) D (n-2)/D (n-1).

Teraz możemy konstruować zniekształcenia, decydując, do jakiego typu cyklu należy ostatni element, zamieniając ostatni element na jedną z pozostałych pozycji n-1 i powtarzając. Może być jednak skomplikowane śledzenie całego rozgałęzienia, więc w 2008 r. Niektórzy badacze opracowali uproszczony algorytm wykorzystujący te pomysły. Opis przejścia znajduje się pod adresem http://www.cs.upc.edu/~conrado/research/talks/analco08.pdf. Czas działania algorytmu jest proporcjonalny do 2n + O (log^2 n), co daje poprawę o 36% w stosunku do metody odrzucania.

Wdrożyłem ich algorytm w Javie. Używanie longów działa na n do 22. Używanie BigIntegers rozszerza algorytm do n = 170 lub tak. Używanie BigIntegers i BigDecimals rozszerza algorytm do n = 40000 (limit zależy od wykorzystania pamięci w pozostałej części programu).

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

     } 

    }