Lista shuffle, assicurandosi che nessun articolo rimanga nella stessa posizione

Question

Voglio mescolare un elenco di elementi unici, ma non fare un casuale casuale shuffle. Devo essere sicuro che nessun elemento nell'elenco mescolato si trova nella stessa posizione dell'elenco originale. Quindi, se la lista originale è (A, B, C, D, E), questo risultato sarebbe OK: (C, D, B, E, A), ma questo non sarebbe: (C, E, A, D, B) perché "D" è ancora il quarto oggetto. L'elenco avrà al massimo sette elementi. L'estrema efficienza non è una considerazione. Credo che questa modifica al Fisher/Yates fa il trucco, ma non posso dimostrarlo matematicamente:

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

Siete alla ricerca di un derangement delle voci.

Prima di tutto, l'algoritmo funziona nel senso che emette un errore casuale, ovvero una permutazione senza punto fisso. Tuttavia ha un enorme difetto (che non ti dispiacerebbe, ma vale la pena tenere a mente): alcuni disallineamenti non possono essere ottenuti con il tuo algoritmo. In altre parole, dà una probabilità pari a zero di alcuni possibili sconvolgimenti, quindi la distribuzione risultante non è sicuramente uniformemente casuale.

Una possibile soluzione, come suggerito nei commenti, sarebbe quella di utilizzare un algoritmo di rifiuto:

• raccogliere una permutazione uniformemente a caso
• se Hax senza punti fissi, restituirlo
• altrimenti riprova

In modo asintotico, la probabilità di ottenere uno squilibrio è vicino a 1/e = 0,3679 (come si vede nell'articolo di Wikipedia). Ciò significa che per ottenere un disallineamento è necessario generare una media di e = 2.718 permutazioni, che è piuttosto costoso.

Un modo migliore per farlo sarebbe quello di rifiutare ad ogni passo dell'algoritmo. In pseudocodice, qualcosa di simile (supponendo che l'array originale contiene i alla posizione i, cioè 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] 
} 

La differenza principale dal vostro algoritmo è che ci permettono j di essere pari a i, ma solo se lo fa non produrre un punto fisso. È leggermente più lungo da eseguire (a causa della parte di rifiuto) e richiede di essere in grado di verificare se una voce si trova nella sua posizione originale o meno, ma ha il vantaggio di poter produrre ogni possibile squilibrio (uniformemente, per quello importa).

Immagino che gli algoritmi di non rifiuto dovrebbero esistere, ma credo che siano meno diretti.

Edit:

mio algoritmo è in realtà male: si ha ancora una possibilità di finire con l'ultimo punto unshuffled, e la distribuzione non è casuale a tutti, vedere le distribuzioni marginali di una simulazione:

Un algoritmo che produce diramazioni distribuite uniformemente può essere trovato here, con qualche contesto sul problema, spiegazioni approfondite e analisi.

Secondo Edit:

In realtà l'algoritmo è noto come Sattolo's algorithm, ed è noto per la produzione di tutti i cicli con uguale probabilità. Quindi qualsiasi derangement che non sia un ciclo ma un prodotto di diversi cicli disgiunti non può essere ottenuto con l'algoritmo. Per esempio, con quattro elementi, la permutazione che scambia 1 e 2, e 3 e 4 è un disordine ma non un ciclo.

Se non ti dispiace ottenere solo cicli, l'algoritmo di Sattolo è la strada da seguire, è in realtà molto più veloce di qualsiasi algoritmo di derangement uniforme, poiché non è necessario alcun rifiuto.

Answer 2

In 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

Come ha accennato @FelixCQ, le mescola che state cercando sono chiamati disordini. La costruzione di squilibri distribuiti casualmente in modo uniforme non è un problema banale, ma alcuni risultati sono noti in letteratura. Il modo più ovvio per costruire gli squilibri è il metodo di rifiuto: si generano permutazioni distribuite uniformemente in modo uniforme usando un algoritmo come Fisher-Yates e poi si rifiutano le permutazioni con punti fissi. Il tempo medio di esecuzione di tale procedura è e * n + o (n) dove e è costante di Euler 2.71828 ... Questo probabilmente funzionerebbe nel tuo caso.

L'altro approccio principale per la generazione di derangements consiste nell'utilizzare un algoritmo ricorsivo. Tuttavia, a differenza di Fisher-Yates, abbiamo due rami all'algoritmo: l'ultimo elemento nell'elenco può essere scambiato con un altro elemento (ad esempio, parte di un a due cicli) o può far parte di un ciclo più ampio. Quindi ad ogni passo, l'algoritmo ricorsivo deve ramificarsi per generare tutti i possibili squilibri. Inoltre, la decisione di prendere una branca o l'altra deve essere presa con le corrette probabilità.

Sia D (n) il numero di squilibri di n elementi. In ogni fase, il numero di rami che portano l'ultimo oggetto a due cicli è (n-1) D (n-2), e il numero di rami che portano l'ultimo oggetto a cicli più grandi è (n-1) D (n -1). Questo ci dà un modo ricorsivo per calcolare il numero di derangements, vale a dire D (n) = (n-1) (D (n-2) + D (n-1)), e ci dà la probabilità di diramazione a due -ciclo in qualsiasi momento, ovvero (n-1) D (n-2)/D (n-1).

Ora possiamo costruire i derangements decidendo a quale tipo di ciclo appartiene l'ultimo elemento, scambiando l'ultimo elemento con una delle altre posizioni n-1 e ripetendo. Può essere complicato tenere traccia di tutte le ramificazioni, tuttavia, così nel 2008 alcuni ricercatori hanno sviluppato un algoritmo semplificato usando queste idee. Puoi vedere una procedura dettagliata allo http://www.cs.upc.edu/~conrado/research/talks/analco08.pdf. Il tempo di esecuzione dell'algoritmo è proporzionale a 2n + O (log^2 n), un miglioramento della velocità del 36% rispetto al metodo di rifiuto.

Ho implementato il loro algoritmo in Java. L'uso di long funziona per n fino a 22 circa. L'uso di BigIntegers estende l'algoritmo a n = 170 o giù di lì. L'uso di BigIntegers e BigDecimals estende l'algoritmo a n = 40000 circa (il limite dipende dall'utilizzo della memoria nel resto del programma).

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

     } 

    }