Lista aleatoria, asegurando que ningún elemento permanece en la misma posición

Question

Quiero barajar una lista de elementos únicos, pero no hacer una mezcla aleatoria al azar. Necesito estar seguro de que ningún elemento en la lista mezclada está en la misma posición que en la lista original. Por lo tanto, si la lista original es (A, B, C, D, E), este resultado estaría bien: (C, D, B, E, A), pero este no: (C, E, A, D, B) porque "D" sigue siendo el cuarto elemento. La lista tendrá como máximo siete elementos. La eficiencia extrema no es una consideración. Creo que esta modificación de Fisher/Yates hace el truco, pero no puedo demostrar matemáticamente:

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

Usted está buscando un derangement de sus entradas.

En primer lugar, su algoritmo funciona en el sentido de que emite un trastorno aleatorio, es decir, una permutación sin punto fijo. Sin embargo, tiene un defecto enorme (que puede que no te importe, pero vale la pena tener en cuenta): no se pueden obtener algunas alteraciones con tu algoritmo. En otras palabras, da probabilidad cero a algunos posibles trastornos, por lo que la distribución resultante definitivamente no es uniformemente aleatoria.

Una posible solución, como se sugiere en los comentarios, sería el uso de un algoritmo de rechazo:

• recoger una permutación de manera uniforme al azar
• si Hax no hay puntos fijos, devuélvalo
• lo contrario reintento

Asintóticamente, la probabilidad de obtener un desarreglo está cerca de 1/e = 0,3679 (como se ve en el artículo de Wikipedia). Lo que significa que para obtener un trastorno tendrá que generar un promedio de e = 2.718 permutaciones, lo cual es bastante costoso.

Una mejor forma de hacerlo sería rechazar en cada paso del algoritmo. En pseudocódigo, algo como esto (suponiendo que la matriz original contiene i en la posición i, es decir 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 principal diferencia con respecto a su algoritmo es que permitimos que j para ser igual a i, pero sólo si lo hace no produce un punto fijo Es un poco más largo de ejecutar (debido a la parte de rechazo), y exige que usted pueda verificar si una entrada está en su lugar original o no, pero tiene la ventaja de que puede producir todos los trastornos posibles (de manera uniforme, para ese importar).

Supongo que deberían existir algoritmos de no rechazo, pero creo que son menos directos.

Editar:

Mi algoritmo es realmente malo: usted todavía tiene la oportunidad de acabar con el último punto unshuffled, y la distribución no es al azar en todo, ver las distribuciones marginales de una simulación:

Se puede encontrar un algoritmo que produce desarreglos uniformemente distribuidos here, con algún contexto sobre el problema, explicaciones y análisis completos.

Segunda Edición:

realidad su algoritmo se conoce como Sattolo's algorithm, y es conocido para producir todos los ciclos con igual probabilidad. Entonces cualquier desarreglo que no sea un ciclo sino un producto de varios ciclos disjuntos no se puede obtener con el algoritmo. Por ejemplo, con cuatro elementos, la permutación que intercambia 1 y 2, y 3 y 4 es un trastorno, pero no un ciclo.

Si no te importa obtener solo ciclos, entonces el algoritmo de Sattolo es el camino a seguir, en realidad es mucho más rápido que cualquier algoritmo de desarreglo uniforme, ya que no se necesita ningún rechazo.

Answer 2

En 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

Como @FelixCQ ha mencionado, los derrapes que usted está buscando son los llamados trastornos . La construcción de trastornos uniformemente distribuidos al azar no es un problema trivial, pero algunos resultados son conocidos en la literatura. La forma más obvia de construir trastornos es mediante el método de rechazo: genera permutaciones uniformemente distribuidas aleatoriamente utilizando un algoritmo como Fisher-Yates y luego rechaza las permutaciones con puntos fijos. El tiempo promedio de ejecución de ese procedimiento es e * n + o (n) donde e es la constante de Euler 2.71828 ... Eso probablemente funcione en su caso.

El otro enfoque importante para generar trastornos es usar un algoritmo recursivo. Sin embargo, a diferencia de Fisher-Yates, tenemos dos ramas para el algoritmo: el último elemento de la lista puede intercambiarse con otro elemento (es decir, parte de un de dos ciclos) o puede formar parte de un ciclo mayor. Entonces, en cada paso, el algoritmo recursivo debe ramificarse para generar todos los posibles trastornos. Además, la decisión de tomar una rama u otra debe tomarse con las probabilidades correctas.

Deje que D (n) sea el número de trastornos de n elementos. En cada etapa, el número de ramas que toman el último elemento para dos ciclos es (n-1) D (n-2), y el número de ramas que toman el último elemento para ciclos más grandes es (n-1) D (n -1). Esto nos da una forma recursiva de calcular el número de trastornos, a saber, D (n) = (n-1) (D (n-2) + D (n-1)), y nos da la probabilidad de ramificarse en dos -ciclo en cualquier etapa, a saber (n-1) D (n-2)/D (n-1).

Ahora podemos construir los desajustes decidiendo a qué tipo de ciclo pertenece el último elemento, intercambiando el último elemento por una de las n-1 otras posiciones y repitiendo. Sin embargo, puede ser complicado hacer un seguimiento de todas las ramificaciones, por lo que en 2008 algunos investigadores desarrollaron un algoritmo simplificado utilizando esas ideas. Puede ver un tutorial en http://www.cs.upc.edu/~conrado/research/talks/analco08.pdf. El tiempo de ejecución del algoritmo es proporcional a 2n + O (log^2 n), una mejora del 36% en la velocidad sobre el método de rechazo.

He implementado su algoritmo en Java. Usar largos funciona para n hasta 22 o más. El uso de BigIntegers extiende el algoritmo a n = 170 o más. El uso de BigIntegers y BigDecimals amplía el algoritmo a n = 40000 o más (el límite depende del uso de la memoria en el resto del programa).

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

     } 

    }