Generar secuencias múltiples de números con valores únicos en cada índice

Question

Tengo una fila con los números 1:n. Estoy mirando para agregar una segunda fila también con los números 1:n pero éstos deben estar en un orden aleatorio, mientras que satisface la siguiente:

1. No hay posiciones tienen el mismo número en ambas filas
2. Ninguna combinación de números ocurre dos veces

Por ejemplo, en el siguiente

Row 1: 1 2 3 4 5 6 7 ... 
Row 2: 3 6 15 8 13 12 7 ... 

el número 7 se produce en la misma posición en ambas filas 1 y 2 (es decir, posición 7; de este modo que no satisfagan la regla 1)

mientras que en el siguiente

Row 1: 1 2 3 4 5 6 7 ... 
Row 2: 3 7 15 8 13 12 2 ... 

la combinación de 2 + 7 aparece dos veces (en las posiciones 2 y 7; de este modo que no satisfagan la regla 2).

Quizás sea posible, pero innecesariamente lento, hacerlo a mano (al menos hasta un número razonable), pero debe haber una solución bastante elegante para esto en MATLAB.

Answer 1

Esto es bastante sencillo.Cree una permutación aleatoria de los nodos, pero interprete la lista de la siguiente manera: inténtelo como una caminata aleatoria alrededor de los nodos, y si el nodo 'b' aparece después del nodo 'a', significa que el nodo 'b' aparece debajo del nodo 'a 'en las listas:

Así que si su permutación aleatoria inicial es

3 2 5 1 4 

a continuación, el paseo en este caso es 3 -> 2 -> 5 -> 1 -> 4 y crea las filas de la siguiente manera:

Row 1: 1 2 3 4 5 
Row 2: 4 5 2 3 1 

este paseo aleatorio se satisfacer ambas condiciones

¿Pero desea permitir más de un ciclo en su red? Sé que no quieres que dos personas se tomen el sombrero. Pero ¿qué pasa con 7 personas, donde tienen sombreros el uno al otro y el otro tienen los sombreros del otro? ¿Es esto aceptable y/o deseable?

Answer 2

Este problema se llama derangment de una permutación.
Utilice la función randperm, para encontrar una permutación aleatoria de sus datos.

x = [1 2 3 4 5 6 7]; 
y = randperm(x); 

Luego, puede verificar que la secuencia sea legal. Si no, hágalo una y otra vez.
Usted tiene probability de aproximadamente 0,3 cada vez para tener éxito, lo que significa que necesita aproximadamente 10/3 veces para intentarlo hasta que lo encuentre. Por lo tanto, encontrará la respuesta realmente rápido.

Como alternativa, puede usar this algorithm para crear un desorden aleatorio.

Editar

Si usted quiere tener sólo ciclos de tamaño> 2, esto es una generalización del problema. En él está escrito que la probabilidad en that case es más pequeña, pero lo suficientemente grande como para encontrarla en una cantidad fija de pasos. Entonces, el mismo enfoque sigue siendo válido.

Answer 3

Andrey ya ha señalado randperm y el enfoque de rechazo-muestreo-como. Después de generar una permutación p, una manera fácil de verificar si tiene un punto fijo es any(p==1:n). Una manera fácil de verificar si contiene ciclos de longitud 2 es any(p(p)==1:n).

Así que ahora se pone permutaciones p de 1:n que cumplen sus requisitos:

p=[]; 
while (isempty(p)) 
    p=randperm(n); 
    if any(p==1:n), p=[]; 
    elseif any(p(p)==1:n), p=[]; 
    end 
end 

rodeando a éste con un bucle for y para cada conteo de las iteraciones del bucle while, parece que se necesita para generar un promedio de 4.5 permutaciones para cada uno "válido" (y 6.2 si los ciclos de longitud tres no están permitidos, tampoco). Muy interesante.