Permutare una matrice quadrata di valori e numero di permutazioni possibili
Augurandomi che il titolo del topic sia abbastanza vicino ad anticipare il problema del quale sono a chiedervi lumi, mi accingo a snocciolarvelo il meglio possibile.
Tutto nasce da un gioco, il gioco dei grattacieli (spiegato a questo link). Essendo appassionato di programmazione ho cercato di implementare un solutore ma dopo un primo inizio in cui pensavo d' aver raggiunto l' obbiettivo, mi sono accorto di aver sbaglaito tutto.
il mio problema è che credevo di poter trovare tutte le possibili permutazioni di una matrice attraverso la permutazione delle sue righe e delle sue colonne, generando un numero di permutazioni pari al quadrato del fattoriale del lato del quadrato:
Numero di permutazioni = N!^2 dove N è il numero delle celle per lato.
Il mio dilemma, anzi, i miei due dilemmi, sono:
1 - Qual' è la formula per determinare quante sono le permutazioni possibili di una griglia di valori di questo genere?
2 - Come posso fare per permutare la griglia, la matrice, in modo che da poter avere tutte le sue possibili permutazioni?
L' unico vincolo è che, nelle righe e nelle colonne, non ci devono essere ripetizioni.
Anticipo che non so niente di matrici e l' unic acosa che ho saputo fare è stato quello di generare una matrice di partenza:
123
231
312
ed applicare, alle sue righe e colonne, le matrici di permutazione (123, 132, 213, 231, 312, 321)
di modo da avere un quadrante di 36 matrici dove solo le prime due file sono risultate essere differenti
N! * (N-1)!
Sperando di essermi spiegato abbastanza da farmi capire ed augurandomi di avervi incuriosito abbastanza da portarvi a darmi qualche consiglio.
GRazie ancora della gentile disponibilità
Tutto nasce da un gioco, il gioco dei grattacieli (spiegato a questo link). Essendo appassionato di programmazione ho cercato di implementare un solutore ma dopo un primo inizio in cui pensavo d' aver raggiunto l' obbiettivo, mi sono accorto di aver sbaglaito tutto.
il mio problema è che credevo di poter trovare tutte le possibili permutazioni di una matrice attraverso la permutazione delle sue righe e delle sue colonne, generando un numero di permutazioni pari al quadrato del fattoriale del lato del quadrato:
Numero di permutazioni = N!^2 dove N è il numero delle celle per lato.
Il mio dilemma, anzi, i miei due dilemmi, sono:
1 - Qual' è la formula per determinare quante sono le permutazioni possibili di una griglia di valori di questo genere?
2 - Come posso fare per permutare la griglia, la matrice, in modo che da poter avere tutte le sue possibili permutazioni?
L' unico vincolo è che, nelle righe e nelle colonne, non ci devono essere ripetizioni.
Anticipo che non so niente di matrici e l' unic acosa che ho saputo fare è stato quello di generare una matrice di partenza:
123
231
312
ed applicare, alle sue righe e colonne, le matrici di permutazione (123, 132, 213, 231, 312, 321)
di modo da avere un quadrante di 36 matrici dove solo le prime due file sono risultate essere differenti
N! * (N-1)!
Sperando di essermi spiegato abbastanza da farmi capire ed augurandomi di avervi incuriosito abbastanza da portarvi a darmi qualche consiglio.
GRazie ancora della gentile disponibilità
Risposte
Niente ... non esiste la formula per determinare $R_n$, si deve contare ... è per quel motivo che sono fermi a $R_11$ ... (io non sono ancora riuscito a contare quante sono le sue cifre ... 
)
)
si guadagna qualcosa se mi metto di buona lena per $r_11$? 
a questo punto direi che posso procedere ad un algoritmo che, sistematicamente, le passi tutte.
a "carta e penna" mi par d aver trovato un sistema interessante per trovare i quadrati principali.
quelli che, se ho ben capito, danno tutte le combinazioni attraverso la permutazione delle righe e delle colonne.
sempre se ho capito:
$r_n$ sono i quadrati principali
$n!$ sono la loro permutazione sulle colonne (o le righe)
$(n-1)!$ sono le matrici qui sopra permutate per le righe (o le colonne)
a questo punto direi che posso procedere ad un algoritmo che, sistematicamente, le passi tutte.
a "carta e penna" mi par d aver trovato un sistema interessante per trovare i quadrati principali.
quelli che, se ho ben capito, danno tutte le combinazioni attraverso la permutazione delle righe e delle colonne.
sempre se ho capito:
$r_n$ sono i quadrati principali
$n!$ sono la loro permutazione sulle colonne (o le righe)
$(n-1)!$ sono le matrici qui sopra permutate per le righe (o le colonne)
"dracoscrigno":
si guadagna qualcosa se mi metto di buona lena per $r_11$?
La fama! (o la fame?)
"dracoscrigno":
sempre se ho capito:
$ r_n $ sono i quadrati principali
$ n! $ sono la loro permutazione sulle colonne (o le righe)
$ (n-1)! $ sono le matrici qui sopra permutate per le righe (o le colonne)
Sostanzialmente sì, però si tratta di capire cosa intendi per "quadrati principali" ... quello che ha le idee chiare però è orsoulx
Cordialmente, Alex
Devo dire che mi sono un po' perso.
Ma per un quadrato 4x4 quante sono le possibilità? $576$?
In un altro post io avevo trovato il risultato di $384$.
Vero che si parlava di sudoku, ma mi sembra sia la stessa cosa......
Ma per un quadrato 4x4 quante sono le possibilità? $576$?
In un altro post io avevo trovato il risultato di $384$.
Vero che si parlava di sudoku, ma mi sembra sia la stessa cosa......
@superpippone:
le regole del sudoku prevedono un'ulteriore condizione; per il 4 per 4 credo sia: in ogni quadrato 2 per 2 d'angolo devono comparire tutti i quattro numeri. Condizione che riduce il numero di possibilità. Per il 4 per 4 il conto mi torna. Da una configurazione valida se ne può ottenere un'altra permutando i quattro numeri. Sarà allora $ s_4=4! * r_n $, dove $ r_n $ è il numero dei sudoku ridotti, cioè quelli che hanno, nell'angolo in alto a sinistra i numeri $ ((1,2),(3,4)) $. Allora quello in alto a destra dovrà avere $ 3 $ e $ 4 $ nella prima riga e $ 1 $ e $ 2 $ nella seconda: quattro modi diversi possibili. Analogamente quello in basso a sinistra dovrà avere $ 2 $ e $ 4 $ nella prima colonna e $ 1 $ e $ 3 $ nella seconda: altri quattro modi diversi possibili. Il quadrato in basso a destrà risulta allora determinato. Quindi $ s_4=4! * 4 * 4 =384 $.
Ciao
le regole del sudoku prevedono un'ulteriore condizione; per il 4 per 4 credo sia: in ogni quadrato 2 per 2 d'angolo devono comparire tutti i quattro numeri. Condizione che riduce il numero di possibilità. Per il 4 per 4 il conto mi torna. Da una configurazione valida se ne può ottenere un'altra permutando i quattro numeri. Sarà allora $ s_4=4! * r_n $, dove $ r_n $ è il numero dei sudoku ridotti, cioè quelli che hanno, nell'angolo in alto a sinistra i numeri $ ((1,2),(3,4)) $. Allora quello in alto a destra dovrà avere $ 3 $ e $ 4 $ nella prima riga e $ 1 $ e $ 2 $ nella seconda: quattro modi diversi possibili. Analogamente quello in basso a sinistra dovrà avere $ 2 $ e $ 4 $ nella prima colonna e $ 1 $ e $ 3 $ nella seconda: altri quattro modi diversi possibili. Il quadrato in basso a destrà risulta allora determinato. Quindi $ s_4=4! * 4 * 4 =384 $.
Ciao
Ehhhhhh....
Mi sono reso conto in seguito di avere scritto una baggianata!
In effetti nel sudoku 4x4, bisogna tenere conto della "costruibilità" dei 4 quadratini 2x2.
Mi scuso.
Mi sono reso conto in seguito di avere scritto una baggianata!
In effetti nel sudoku 4x4, bisogna tenere conto della "costruibilità" dei 4 quadratini 2x2.
Mi scuso.
"superpippone":
Mi scuso.
Ti pare il caso?
Ciao
io mi son messo di buona lena ed ho scritto la colonna delle 24 permutazioni di $(1,2,3,4)$
poi ho preso una delle 6 permutazioni che comincian con $1$ ed ho vercato tutte quelle che comincian con $2$ che soddisfacessero il vincolo dell essere differenti per colonna.
ho reiterato il processo, quindi, per sei volte.
alla fine ho trovato 18 quadrati.
secondo me, $r_n$ dovrebbe essere questo numero di quadrati trovati.
... perchè non ne trovo 24, ma 18?
poi ho preso una delle 6 permutazioni che comincian con $1$ ed ho vercato tutte quelle che comincian con $2$ che soddisfacessero il vincolo dell essere differenti per colonna.
ho reiterato il processo, quindi, per sei volte.
alla fine ho trovato 18 quadrati.
secondo me, $r_n$ dovrebbe essere questo numero di quadrati trovati.
... perchè non ne trovo 24, ma 18?
A quale quadrato ti riferisci? $n=4$ o $n=5$ ?
Comunque se $n=4$ allora $R_4=4$ e i quattro quadrati "principali" (o meglio "ridotti") da permutare $4!*3!$ volte ($4!$ le colonne e $3!$ le restanti tre righe) sono quelli nella forma $((1,2,3,4),(2,*,*,*),(3,*,*,*),(4,*,*,*))$ e cioè $((1,2,3,4),(2,1,4,3),(3,4,1,2),(4,3,2,1))$, $((1,2,3,4),(2,1,4,3),(3,4,2,1),(4,3,1,2))$, $((1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3))$, $((1,2,3,4),(2,4,1,3),(3,1,4,2),(4,3,2,1))$.
Se $n=5$ allora $R_5=56$ però te li costruisci tu ... ... (oppure li chiedi gentilmente a orsoulx che li ha trovati tutti ... 
)
Comunque se $n=4$ allora $R_4=4$ e i quattro quadrati "principali" (o meglio "ridotti") da permutare $4!*3!$ volte ($4!$ le colonne e $3!$ le restanti tre righe) sono quelli nella forma $((1,2,3,4),(2,*,*,*),(3,*,*,*),(4,*,*,*))$ e cioè $((1,2,3,4),(2,1,4,3),(3,4,1,2),(4,3,2,1))$, $((1,2,3,4),(2,1,4,3),(3,4,2,1),(4,3,1,2))$, $((1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3))$, $((1,2,3,4),(2,4,1,3),(3,1,4,2),(4,3,2,1))$.
Se $n=5$ allora $R_5=56$ però te li costruisci tu ...
... (oppure li chiedi gentilmente a orsoulx che li ha trovati tutti ... )
grazie . ora credo d aver capito.
con quadrati principali intendevo i 4 quadrati che mi hai indicato.
ho detto primcipali e non ridotti perche la parola "ridotti", nel momento in cui ho postato non mi veniva anche se l avevo gia letta piu sopra in un vostro intervento.
il 24 di cui parlavo, non so dove l ho tirato fuori. probabilmente mi son confuso (con tutte ste paginate di roba scritta in inglese fose mi.son perso più di una volta)
di quei quattro quadrati che mi hai indicato io ne trovavo 18 perchè cercavo tutti i quadrati possibili con le $4!$ permutazioni di $4$ elementi.
mi ero perso il particolare di cercare solo quelle con la prima riga ferma ad $(1,2,3,4)$
quindi me ne uscivano, non 4 ma 18. tanto meglio. sono gia un botto così
adesso credo d aver l algoritmo fatto e finito in testa:
primo passo:
creare i quadrati ridotto.
di ogni quadrato trovato permutare le colonne.
di quadrato nato dalla permutazione di colonna, permutarne le righe.
... acquisterò in muovo pc più performante
con quadrati principali intendevo i 4 quadrati che mi hai indicato.
ho detto primcipali e non ridotti perche la parola "ridotti", nel momento in cui ho postato non mi veniva anche se l avevo gia letta piu sopra in un vostro intervento.
il 24 di cui parlavo, non so dove l ho tirato fuori. probabilmente mi son confuso (con tutte ste paginate di roba scritta in inglese fose mi.son perso più di una volta)
di quei quattro quadrati che mi hai indicato io ne trovavo 18 perchè cercavo tutti i quadrati possibili con le $4!$ permutazioni di $4$ elementi.
mi ero perso il particolare di cercare solo quelle con la prima riga ferma ad $(1,2,3,4)$
quindi me ne uscivano, non 4 ma 18. tanto meglio. sono gia un botto così
adesso credo d aver l algoritmo fatto e finito in testa:
primo passo:
creare i quadrati ridotto.
di ogni quadrato trovato permutare le colonne.
di quadrato nato dalla permutazione di colonna, permutarne le righe.
... acquisterò in muovo pc più performante
"dracoscrigno":
... acquisterò in muovo pc più performante
Perché uno solo? Con una camionata, lavorando in parallelo, finisci prima.
Questi sono gli $ r_5 $. Senza la prima riga e la prima colonna, rdinati secondo le posizioni del '2' nel riquadro 3 per 3 in basso a destra e poi secondo le posizioni del 5 nel 3 per 3 in alto a sinistra, tranne l'ultimo della quarta fila che dovrebbe essere l'ultimo della quinta e le ultime due della seconda che dovrebbero essere le ultime della settima.
Ciao e buon lavoro
Ciao.
Ma utilizzando questo genere di formule, si è in grado di trovare quanti sono i sudoku possibili nella forma classica (un quadrato 9x9, suddiviso in 9 quadratini 3x3)?????
Se sì, quanti sono??
E' una curiosità che mi angustia da oltre un decennio.....
Grazie
Ma utilizzando questo genere di formule, si è in grado di trovare quanti sono i sudoku possibili nella forma classica (un quadrato 9x9, suddiviso in 9 quadratini 3x3)?????
Se sì, quanti sono??
E' una curiosità che mi angustia da oltre un decennio.....
Grazie
Meno di $5.524.751.496.156.892.842.531.225.600$ ...
EDIT: Ho trovato questo ...
"Bertram Felgenhauer, Frazer Jarvis e, indipendentemente da loro, Ed Russell, hanno stabilito che l'universo di tutti i possibili Sudoku avrebbe $6.670.903.752.021.072.936.960$ abitanti."
Basta chiedere ...
Cordialmente, Alex
EDIT2: Vedi qui
EDIT: Ho trovato questo ...
"Bertram Felgenhauer, Frazer Jarvis e, indipendentemente da loro, Ed Russell, hanno stabilito che l'universo di tutti i possibili Sudoku avrebbe $6.670.903.752.021.072.936.960$ abitanti."
Basta chiedere ...
Cordialmente, Alex
EDIT2: Vedi qui
Mi sento lievemente preso in giro....
Il primo numero che hai scritto, non mi è sconosciuto...
Cos'è? Il numero delle cartelle della tombola?
Ti ringrazio per l'informazione. Adesso dormirò molto più tranquillo.
Saluti.
Luciano
Il primo numero che hai scritto, non mi è sconosciuto...
Cos'è? Il numero delle cartelle della tombola?
Ti ringrazio per l'informazione. Adesso dormirò molto più tranquillo.
Saluti.
Luciano
Cioè, ti ho cercato i riferimenti che volevi e mi dici che ti prendo in giro? Cattivo! 
Per quel numero ... è quattro pagine che stiamo parlando di quei numeri ovvero in questo caso il numero di matrici quadrate di ordine $9$ riempite con 9 simboli diversi che non si ripetono in nessuna colonna e in nessuna riga ... ok?
Mi fa piacere esserti stato di aiuto per risolvere problemi del sonno ...
Ciao, Alex
Per quel numero ... è quattro pagine che stiamo parlando di quei numeri ovvero in questo caso il numero di matrici quadrate di ordine $9$ riempite con 9 simboli diversi che non si ripetono in nessuna colonna e in nessuna riga ... ok?
Mi fa piacere esserti stato di aiuto per risolvere problemi del sonno ...
Ciao, Alex
Ma come potevi pensare che collegassi "quel" numero, con l'argomento oggetto di questo post!!!
Lo sai che sono "limitato".......
Lo sai che sono "limitato".......
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo