Generare più sequenze di numeri con valori univoci in ciascun indice

Question

Ho una riga con i numeri 1:n. Sto cercando di aggiungere una seconda fila anche con i numeri 1:n ma questi dovrebbero essere in un ordine casuale, pur rispettando il seguente:

1. Nessun posizioni hanno lo stesso numero in entrambe le righe
2. Nessuna combinazione di numeri si verifica due volte

ad esempio, nel seguente

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

il numero 7 avviene nella stessa posizione in entrambe le righe 1 e 2 (vale a dire posizione 7; in tal modo non soddisfano regola 1)

mentre nella seguente

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

la combinazione di 2 + 7 appare due volte (nelle posizioni 2 e 7, in tal modo non rispondenti regola 2).

Sarebbe forse possibile, ma inutilmente dispendioso in termini di tempo, eseguire questa operazione manualmente (almeno fino a un numero ragionevole), ma in MATLAB deve esserci una soluzione piuttosto elegante.

Answer 1

Questo è abbastanza semplice.Crea una permutazione casuale dei nodi, ma interpreta l'elenco come segue: Interpretalo come una passeggiata casuale attorno ai nodi, e se il nodo 'b' appare dopo il nodo 'a', significa che il nodo 'b' appare sotto il nodo 'a 'nelle liste:

Così, se il permutazione casuale iniziale è

3 2 5 1 4 

Poi la passeggiata in questo caso è 3 -> 2 -> 5 -> 1 -> 4 e si crea le righe come segue:

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

questa passeggiata casuale soddisfare entrambe le condizioni.

Ma si desidera consentire più di un ciclo nella rete? So che non vuoi che due persone abbiano il cappello a vicenda. Ma che dire di 7 persone, dove di loro hanno i cappelli l'uno dell'altro e l'altro hanno i cappelli l'uno dell'altro? Questo è accettabile e/o desiderabile?

Answer 2

Questo problema è chiamato un errore di una permutazione.
Utilizzare la funzione randperm, per trovare una permutazione casuale dei dati.

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

Quindi, è possibile verificare che la sequenza sia legale. In caso contrario, fallo ancora e ancora ..
Hai uno probability di circa 0.3 ogni volta per avere successo, il che significa che hai bisogno di circa 10/3 volte di provare finché non lo trovi. Quindi troverai la risposta molto velocemente.

In alternativa, è possibile utilizzare this algorithm per creare uno squilibrio casuale.

Modifica

Se si vuole avere solo cicli di dimensioni> 2, questa è una generalizzazione del problema. In esso è scritto che la probabilità in that case è più piccola, ma abbastanza grande da trovarla in una quantità fissa di passaggi. Quindi lo stesso approccio è ancora valido.

Answer 3

Andrey ti ha già indirizzato allo randperm e all'approccio del tipo "reiezione-campionamento". Dopo aver generato una permutazione p, un modo semplice per verificare se ha un punto fisso è any(p==1:n). Un modo semplice per verificare se contiene cicli di lunghezza 2 è any(p(p)==1:n).

Così questo diventa permutazioni p di 1:n esecuzione della prestazione richiesta:

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

Attorno a questo con un ciclo for e per ogni conteggio delle iterazioni del ciclo while, sembra che uno ha bisogno per generare in media 4.5 permutazioni per ogni "valido" (e 6.2 se non sono ammessi neanche i cicli di lunghezza tre). Molto interessante.