Randomize matrice Perl, mantenendo riga e colonna ammonta stesso

Question

Ho una matrice che voglio randomizzare un paio di mille volte, mantenendo la riga e colonna Totali stesso:

 1 2 3 
    A 0 0 1 
    B 1 1 0 
    C 1 0 0  

Un esempio di una matrice casuale valida sarebbe:

 1 2 3 
    A 1 0 0 
    B 1 1 0 
    C 0 0 1 

la mia matrice reale è molto più grande (circa 600x600 articoli), quindi ho davvero bisogno di un approccio che è computazionalmente efficiente.

Il mio approccio iniziale (inefficiente) consisteva di array mischiare con il Perl Cookbookshuffle

Ho incollato il mio codice corrente al di sotto. Ho un codice in più per iniziare con una nuova lista mescolata di numeri, se non viene trovata alcuna soluzione nel ciclo while. L'algoritmo funziona bene per una matrice di piccole dimensioni, ma non appena avrò iniziato a scalare ci vorrà un'eternità per trovare una matrice casuale che soddisfi i requisiti.

Esiste un modo più efficiente per eseguire ciò che sto cercando? Grazie mille!

#!/usr/bin/perl -w 
use strict; 

my %matrix = ('A' => {'3' => 1 }, 
      'B' => {'1' => 1, 
       '2' => 1 }, 
      'C' => {'1' => 1 } 
    ); 

my @letters =(); 
my @numbers =(); 

foreach my $letter (keys %matrix){ 
    foreach my $number (keys %{$matrix{$letter}}){ 
    push (@letters, $letter); 
    push (@numbers, $number); 
    } 
} 

my %random_matrix =(); 

&shuffle(\@numbers); 
foreach my $letter (@letters){ 
    while (exists($random_matrix{$letter}{$numbers[0]})){ 
    &shuffle (\@numbers); 
    } 
    my $chosen_number = shift (@numbers); 
    $random_matrix{$letter}{$chosen_number} = 1; 
} 

sub shuffle { 
    my $array = shift; 
    my $i = scalar(@$array); 
    my $j; 
    foreach my $item (@$array) 
    { 
     --$i; 
     $j = int rand ($i+1); 
     next if $i == $j; 
     @$array [$i,$j] = @$array[$j,$i]; 
    } 
    return @$array; 
} 

Answer 1

Il problema con l'algoritmo attuale è che si sta cercando di mischiare il tuo modo di vicoli ciechi - in particolare, quando i vostri @letters e @numbers array (dopo il riordino iniziale di @numbers) producono la stessa cella più di una volta. Questo approccio funziona quando la matrice è piccola, perché non ci vogliono troppi tentativi per trovare un re-shuffle fattibile. Tuttavia, è un killer quando le liste sono grandi. Anche se potresti cercare le alternative in modo più efficiente, ad esempio provando permutazioni piuttosto che mischiare casualmente, l'approccio è probabilmente destinato a fallire.

Invece di mischiare interi elenchi, è possibile affrontare il problema apportando piccole modifiche a una matrice esistente.

Ad esempio, iniziamo con la matrice di esempio (chiamiamola M1). Seleziona casualmente una cella per cambiare (ad esempio, A1). A questo punto la matrice si trova in uno stato illegale. Il nostro obiettivo sarà quello di risolverlo nel numero minimo di modifiche, in particolare 3 ulteriori modifiche. Implementa queste 3 modifiche aggiuntive "camminando" intorno alla matrice, con ogni riparazione di una riga o colonna che produce un altro problema da risolvere, fino a quando non hai percorso il cerchio completo (err ... rettangolo completo).

Ad esempio, dopo aver modificato A1 da 0 a 1, ci sono 3 modi di camminare per la riparazione successiva: A3, B1 e C1. Decidiamo che la prima modifica debba correggere le righe. Quindi selezioniamo A3. Nella seconda modifica, correggeremo la colonna, quindi abbiamo le scelte: B3 o C3 (per esempio, C3). La riparazione finale offre solo una scelta (C1), perché dobbiamo tornare alla colonna della nostra modifica originale.Il risultato finale è una nuova matrice valida.

Orig   Change A1  Change A3  Change C3  Change C1 
    M1              M2 

    1 2 3  1 2 3   1 2 3   1 2 3   1 2 3 
    -----  -----   -----   -----   ----- 
A | 0 0 1  1 0 1   1 0 0   1 0 0   1 0 0 
B | 1 1 0  1 1 0   1 1 0   1 1 0   1 1 0 
C | 1 0 0  1 0 0   1 0 0   1 0 1   0 0 1 

Se un percorso di modifica porta ad un vicolo cieco, si marcia indietro. Se tutti i percorsi di riparazione falliscono, la modifica iniziale può essere rifiutata.

Questo approccio genererà rapidamente nuove matrici valide. Non produrrà necessariamente risultati casuali: M1 e M2 saranno ancora altamente correlati l'uno con l'altro, un punto che diventerà più direttamente evidente man mano che la dimensione della matrice cresce.

Come si aumenta la casualità? Hai detto che la maggior parte delle celle (99% o più) sono zero. Un'idea sarebbe quella di procedere in questo modo: per ogni 1 nella matrice, impostare il suo valore su 0 e quindi riparare la matrice usando il metodo di modifica a 4 delineato sopra. In effetti, dovresti spostare tutti quelli in posizioni nuove e casuali.

Ecco un'illustrazione. Ci sono probabilmente ulteriori ottimizzazioni della velocità qui, ma questo approccio ha prodotto 10 nuove matrici 600x600, con una densità dello 0,5%, in 30 secondi circa sulla mia scatola di Windows. Non so se è abbastanza veloce.

use strict; 
use warnings; 

# Args: N rows, N columns, density, N iterations. 
main(@ARGV); 

sub main { 
    my $n_iter = pop; 
    my $matrix = init_matrix(@_); 
    print_matrix($matrix); 
    for my $n (1 .. $n_iter){ 
     warn $n, "\n"; # Show progress. 
     edit_matrix($matrix); 
     print_matrix($matrix); 
    } 
} 

sub init_matrix { 
    # Generate initial matrix, given N of rows, N of cols, and density. 
    my ($rows, $cols, $density) = @_; 
    my @matrix; 
    for my $r (1 .. $rows){ 
     push @matrix, [ map { rand() < $density ? 1 : 0 } 1 .. $cols ]; 
    } 
    return \@matrix; 
} 

sub print_matrix { 
    # Dump out a matrix for checking. 
    my $matrix = shift; 
    print "\n"; 
    for my $row (@$matrix){ 
     my @vals = map { $_ ? 1 : ''} @$row; 
     print join("\t", @vals), "\n"; 
    } 
} 

sub edit_matrix { 
    # Takes a matrix and moves all of the non-empty cells somewhere else. 
    my $matrix = shift; 
    my $move_these = cells_to_move($matrix); 
    for my $cell (@$move_these){ 
     my ($i, $j) = @$cell; 
     # Move the cell, provided that the cell hasn't been moved 
     # already and the subsequent edits don't lead to a dead end. 
     $matrix->[$i][$j] = 0 
      if $matrix->[$i][$j] 
      and other_edits($matrix, $cell, 0, $j); 
    } 
} 

sub cells_to_move { 
    # Returns a list of non-empty cells. 
    my $matrix = shift; 
    my $i = -1; 
    my @cells =(); 
    for my $row (@$matrix){ 
     $i ++; 
     for my $j (0 .. @$row - 1){ 
      push @cells, [$i, $j] if $matrix->[$i][$j]; 
     } 
    } 
    return \@cells; 
} 

sub other_edits { 
    my ($matrix, $cell, $step, $last_j) = @_; 

    # We have succeeded if we've already made 3 edits. 
    $step ++; 
    return 1 if $step > 3; 

    # Determine the roster of next edits to fix the row or 
    # column total upset by our prior edit. 
    my ($i, $j) = @$cell; 
    my @fixes; 
    if ($step == 1){ 
     @fixes = 
      map { [$i, $_] } 
      grep { $_ != $j and not $matrix->[$i][$_] } 
      0 .. @{$matrix->[0]} - 1 
     ; 
     shuffle(\@fixes); 
    } 
    elsif ($step == 2) { 
     @fixes = 
      map { [$_, $j] } 
      grep { $_ != $i and $matrix->[$_][$j] } 
      0 .. @$matrix - 1 
     ; 
     shuffle(\@fixes); 
    } 
    else { 
     # On the last edit, the column of the fix must be 
     # the same as the column of the initial edit. 
     @fixes = ([$i, $last_j]) unless $matrix->[$i][$last_j]; 
    } 

    for my $f (@fixes){ 
     # If all subsequent fixes succeed, we are golden: make 
     # the current fix and return true. 
     if (other_edits($matrix, [@$f], $step, $last_j)){ 
      $matrix->[$f->[0]][$f->[1]] = $step == 2 ? 0 : 1; 
      return 1; 
     } 
    } 

    # Failure if we get here. 
    return; 
} 

sub shuffle { 
    my $array = shift; 
    my $i = scalar(@$array); 
    my $j; 
    for (@$array){ 
     $i --; 
     $j = int rand($i + 1); 
     @$array[$i, $j] = @$array[$j, $i] unless $i == $j; 
    } 
} 

Answer 2

Non sono sicuro se vi aiuterà, ma si può provare ad andare da un angolo e per ogni colonna e riga si dovrebbe monitorare la somma totale ed effettivo. Invece di cercare di colpire una buona matrice, prova a vedere il totale come importo e dividerlo. Per ogni elemento, trova il numero più piccolo di totale di righe - totale della riga effettiva e totale della colonna - totale della colonna effettiva. Ora hai il limite superiore per il tuo numero casuale. È chiaro? Spiacente, non conosco Perl, quindi non posso mostrare alcun codice.

Answer 3

Passo 1: Innanzitutto vorrei inizializzare la matrice su zeri e calcolare i totali richiesti di righe e colonne.

Passo 2: Ora scegli una riga casuale, ponderata per il conteggio di 1s che deve essere in quella riga (quindi una riga con il conteggio 300 ha più probabilità di essere prelevata rispetto a una riga con peso 5).

Passaggio 3: per questa riga, selezionare una colonna casuale, ponderata in base al conteggio di 1 in quella colonna (tranne ignorare eventuali celle che potrebbero già contenere un 1 - ulteriori informazioni in seguito).

Passaggio 4: posizionare uno in questa cella e ridurre il conteggio di righe e colonne per la riga e la colonna appropriate.

Passaggio 5: tornare al passaggio 2 finché nessuna riga ha un conteggio diverso da zero.

Il problema però è che questo algoritmo può non riuscire a terminare perché potresti avere una riga dove devi metterne una, e una colonna che ha bisogno di una, ma hai già inserito una in quella cella, quindi tieni 'bloccato'. Non sono sicuro di quanto questo possa accadere, ma non sarei sorpreso se accadesse molto frequentemente, abbastanza da rendere l'algoritmo inutilizzabile. Se questo è un problema, posso pensare a due modi per risolverlo:

a) Costruire l'algoritmo sopra in modo ricorsivo e consentire il backtracking in caso di errore.

b) Consentire a una cella di contenere un valore maggiore di 1 se non ci sono altre opzioni e continuare. Quindi alla fine hai un numero corretto di righe e colonne ma alcune celle potrebbero contenere numeri maggiori di 1.È possibile risolvere questo trovando un raggruppamento che assomiglia a questo:

2 . . . . 0 
. . . . . . 
. . . . . . 
0 . . . . 1 

e cambiando a:

1 . . . . 1 
. . . . . . 
. . . . . . 
1 . . . . 0 

dovrebbe essere facile trovare un tale raggruppamento, se si dispone di molti zeri. Penso che b) rischia di essere più veloce.

Non sono sicuro che sia il modo migliore, ma è probabilmente più veloce di mischiare gli array. Tracciamo questa domanda per vedere cosa escono gli altri.

Answer 4

Come @Gabriel io non sono un programmatore Perl in modo che sia possibile che questo è ciò che il codice fa già ...

Hai postato solo un esempio. Non è chiaro se si desidera una matrice casuale che abbia lo stesso numero di 1 in ogni riga e colonna come matrice iniziale, o una che abbia le stesse righe e colonne ma mescolata. Se quest'ultimo è abbastanza buono, puoi creare un array di indici di riga (o di colonna, non importa) e permutarlo a caso. È quindi possibile leggere la matrice originale nell'ordine specificato dall'indice casuale. Non c'è bisogno di modificare la matrice originale o creare una copia.

Naturalmente, questo potrebbe non soddisfare aspetti delle vostre esigenze che non sono espliciti.

Answer 5

Non sono un matematico, ma immagino che se è necessario mantenere la stessa colonna e i totali delle righe, le versioni casuali della matrice avranno la stessa quantità di uni e zeri.

Correggetemi se ho torto, ma ciò significherebbe che rendere successive le versioni della matrice richiederebbe solo di mescolare le righe e le colonne.

Le colonne mescolate in modo casuale non modificheranno i totali per righe e colonne e nemmeno le righe casualmente mescolate. Quindi, quello che farei, è il primo shuffle row, e poi mescolare le colonne.

Questo dovrebbe essere abbastanza veloce.