¿Por qué esta forma de generar aleatoriamente un gráfico es injusto?

Mi objective es generar un gráfico dirigido de n vértices de modo que cada vértice tenga una arista y una arista. Pensé que una forma de hacerlo sería poner todos los vértices en una maceta y que los vértices tomaran turnos. barajando y sacando inputs, así por ejemplo si el vértice 1 saca el vértice 3, entonces eso significa que habrá un borde que irá de 1 a 3. Si un vértice se saca del bote, simplemente lo devuelve y se reorganiza. Si al final, el último vértice descubre que la olla solo se contiene a sí misma, entonces debemos comenzar de nuevo. Aquí está mi código de Kotlin:

fun generateGraph(n: Int): Map<Int, Int> { val vertices : List<Int> = (1..n).toList() while (true) { val pot = vertices.toMutableList() val result = mutableMapOf<Int, Int>() for (vertex in 1 until n) { do { java.util.Collections.shuffle(pot) } while (pot[0] == vertex) result.put(vertex, pot.removeAt(0)) } if (pot[0] != n) { result.put(n, pot.removeAt(0)) return result } else { // The last vertex left in the pot is also the last one unassigned. Try again... } } } 

Parece funcionar. Sin embargo, cuando estoy probando, descubro que sale con algunos charts más que otros. Cuando n es 3, los únicos charts válidos son los ciclos

 {1=3, 2=1, 3=2} {1=2, 2=3, 3=1} 

pero estoy descubriendo que el primero aparece el doble de veces que el segundo:

 fun main(args: Array<String>) { val n = 3 val patternCounts = mutableMapOf<Map<Int, Int>, Int>() val trials = 10000 (1..trials).forEach({ val graph = generateGraph(n) patternCounts[graph] = patternCounts.getOrDefault(graph, 0) + 1 }) println(patternCounts) } 

Una tirada de esto recién impresa

 {{1=3, 2=1, 3=2}=6669, {1=2, 2=3, 3=1}=3331} 

¿Qué me estoy perdiendo? Y, ¿hay alguna manera de hacer esto justo?

No es difícil ver por qué ocurre ese resultado. El vértice 1 se combina con el vértice 3 la mitad del time. Si eso sucede, el gráfico no se puede rechazar porque el rechazo solo ocurre cuando el último vértice restante es n (3 en este caso) y ese vértice se ha utilizado. Así que la mitad del time obtendrás {(1,3), (2,1), (3,2)}.

La otra mitad del time, el vértice 1 coincidirá con el vértice 2, pero luego la mitad de esos casos (es decir, ¼ del total) serán rechazados después de que el vértice 2 coincida con el vértice 1. Entonces {(1,2), ( 2,3), (3,1)} se elegirá una cuarta parte del time.

En el trimestre restante, se repetirá todo el procedimiento, lo que significa que {(1,3), (2,1), (3,2)} seguirán siendo elegidos el doble de frecuencia.

Una solución es rechazar todo el gráfico tan pronto como coincida un vértice consigo mismo. En este caso, no hay necesidad de reorganizar antes de seleccionar; solo reorganizas si el gráfico es rechazado.

El problema general es que el caso de emparejar un vértice consigo mismo no es independiente de todas las demás opciones. Entonces, simplemente reorganizar después de ciertos partidos y rechazar después de otros conduce a un sesgo.

Rechazar y reiniciar después de cualquier coincidencia podría no ser la solución más eficiente, pero funcionará. Una forma de hacer que el algorithm sea más eficiente sería barajar incrementalmente, en lugar de hacer todo el barajado y luego validarlo. Otra posibilidad se describe en un documento al que se hace reference a partir de esta pregunta sobre Mathematics Stack Exchange.

¿Qué me estoy perdiendo? Y, ¿hay alguna manera de hacer esto justo?

Lo que te estás perdiendo es que tu algrothim es injusto.

En primer lugar, debe saber que el generador de numbers aleatorios de software no es realmente aleatorio. Siempre hace que parezca justo, a diferencia del real aleatorio.

Entonces, considere lo siguiente

 java.util.Collections.shuffle(pot) 

darte 3 resultados

 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 

Si elimina su condición de "do-while" y su condición, todos los resultados tienen un conteo similar.

Sin embargo, usted lo hace, mientras que la condición previene la position = valor. Los posibles resultados son

 2, 1, 3 2, 3, 1 3, 1, 2 

Tenga en count que la distribución de los resultados NO es par. Considera lo siguiente:

 When vertex == 1: case pot[0] == 1: reroll case pot[0] == 2: continue // 50% case pot[0] == 3: continue // 50% If the result[0] == 2: When vertex == 2: case pot[0] == 1: continue // 25% case pot[0] == 3: continue // 25% If the result[0] == 3: When vertex == 2: case pot[0] == 1: continue // 50% case pot[0] == 2: reroll Result: 2, 1, 3 (25%) 2, 3, 1 (25%) 3, 1, 2 (50%) 

Entonces, la condición if DISCARD 2, 1, 3 (No se repite, que es diferente del ciclo while. Comenzó de nuevo desde cero. Los resultados restantes son

  2, 3, 1 (25%) 3, 1, 2 (50%) 

(3, 1, 2):(2, 3, 1) es aproximadamente 2: 1 que coincide con su resultado.

Solución

 fun generateGraph(n: Int): Map<Int, Int> { val vertices : List<Int> = (1..n).toList() loop@ while (true) { val pot = vertices.toMutableList() val result = mutableMapOf<Int, Int>() // No need to shuffle evey position java.util.Collections.shuffle(pot) for (vertex in 1..n) { val value = pot[vertex-1] // if position == value, always start from scratch if (value == vertex) continue@loop result.put(vertex, value) } return result } } 

Además, debe mejorar las matemáticas en probabilidad y estadística antes de dudar de la distribución numérica de un generador de numbers aleatorios.

  • ¿Por qué IntelliJ Idea no reconoce mis testings de Spek?
  • Ventana cornetworkingera RxJava
  • ¿Cómo puedo representar una relación de muchos a muchos con Android Room?
  • La propiedad en la interfaz no puede tener un campo de respaldo
  • Kotlin: ejecuta una testing de integración, el error `diversión principal ya está definido`
  • CountDownLatch no libera el hilo
  • Cuál es la diferencia entre la class normal y la class de datos en kotlin
  • ¿Cuál es el tipo de setContentView ()
  • ¿Cuál es el enfoque correcto para "Esta class AsyncTask debe ser estática o pueden producirse filtraciones" en Kotlin Android?
  • ¿Cómo configurar el headerView de NavigationView con Anko DSL?
  • ReferenceError: ok no está definido en QUnitAsserter.assertTrue en Kotlin Javascript