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
Premesso che hai sbagliato sezione (avevi tre possibilità: o la sezione di Algebra per le permutazioni, o la sezione di Algebra Lineare per le matrici oppure la sezione Giochi ... hai preso la quarta! 
), io butterei lì un paio di idee ...
Penso che il numero di permutazioni totali per un quadrato di lato $n$ sia $P_n=1!*2!*...*n!$ (che non è il quadrato di $n$) ... questo perché se $a_n$ è il numero delle permutazioni di un quadrato di lato $n$ se aggiungiamo un numero (e una colonna e una riga), per ciascuna di esse il nuovo numero può essere posizionato in $n+1$ posti sull prima riga, in $n$ posti sulla seconda e così via e quindi $a_(n+1)=a_n*(n+1)!$ che risolvendo partendo da $a_1=1$ dà la formula iniziale ... credo ...
Per la costruzione, penso che per $n$ piccoli si possa fare così ...
Crei una tabella con tutte le permutazioni (p.es. $120=5!$), a ciascuna associ il numero di "grattacieli" visibili da sx e da dx ... poi costruisci il quadrato scorrendo la tabella con cinque "for" nidificati (non sono un programmatore, è solo per dare un'idea) aiutandoti a scartare le permutazioni non idonee con i numeri associati ... spero di aver reso l'idea ...
Cordialmente, Alex
), io butterei lì un paio di idee ...Penso che il numero di permutazioni totali per un quadrato di lato $n$ sia $P_n=1!*2!*...*n!$ (che non è il quadrato di $n$) ... questo perché se $a_n$ è il numero delle permutazioni di un quadrato di lato $n$ se aggiungiamo un numero (e una colonna e una riga), per ciascuna di esse il nuovo numero può essere posizionato in $n+1$ posti sull prima riga, in $n$ posti sulla seconda e così via e quindi $a_(n+1)=a_n*(n+1)!$ che risolvendo partendo da $a_1=1$ dà la formula iniziale ... credo ...
Per la costruzione, penso che per $n$ piccoli si possa fare così ...
Crei una tabella con tutte le permutazioni (p.es. $120=5!$), a ciascuna associ il numero di "grattacieli" visibili da sx e da dx ... poi costruisci il quadrato scorrendo la tabella con cinque "for" nidificati (non sono un programmatore, è solo per dare un'idea) aiutandoti a scartare le permutazioni non idonee con i numeri associati ... spero di aver reso l'idea ...
Cordialmente, Alex
GRazie Axpgn per l' intervento. se la formula è corretta ed io la do come corretta perchè il tuo ragionamento non mi pare faccia acqua da qualche parte. A prima svista 
. Se non altro, ora, ho un termine di paragone.
Tra le varie mi chiedevo se, esiste un algoritmo, una tecnica, che, attraverso l' uso di una o più proprietà, possa far passare da una data matrice definita come iniziale possa far passare alla successiva e così via fino all' ultima.
In altri termini, prendendo sempre come esempio tre elementi per lato ed avendo quindi le possibili permutazioni di riga e di colnna, esiste un processo per cui si possa passare, per esempio, da
$((1,2,3),(2,3,1),(3,1,2))$
a
$((1,3,2),(2,1,3),(3,2,1))$
e così via di modo che sia possibile passare da una paermutazione all' altra in una successione che le spazzoli tutte?
P.s.
Rieditando... Dimenicavo...
Perchè hai proprio detto 5 reiterazioni annidate? potresti raccontarmi, se l' hai avuta, la tua possibile idea dell' algoritmo?
. Se non altro, ora, ho un termine di paragone.Tra le varie mi chiedevo se, esiste un algoritmo, una tecnica, che, attraverso l' uso di una o più proprietà, possa far passare da una data matrice definita come iniziale possa far passare alla successiva e così via fino all' ultima.
In altri termini, prendendo sempre come esempio tre elementi per lato ed avendo quindi le possibili permutazioni di riga e di colnna, esiste un processo per cui si possa passare, per esempio, da
$((1,2,3),(2,3,1),(3,1,2))$
a
$((1,3,2),(2,1,3),(3,2,1))$
e così via di modo che sia possibile passare da una paermutazione all' altra in una successione che le spazzoli tutte?
P.s.
Rieditando... Dimenicavo...
Perchè hai proprio detto 5 reiterazioni annidate? potresti raccontarmi, se l' hai avuta, la tua possibile idea dell' algoritmo?
Ho visto che hanno spostato il thread nella sezione "Giochi" il che è giusto anche se per la questione riguardante le matrici sarebbe stato meglio la sezione di "Algebra Lineare" ... aspettiamo interventi esperti ...
A riguardo del "cinque" era solo in riferimento al link che avevi messo, dove il quadrato è di lato "5" ...
Aggiungo uno pseudo-codice, sperando che si capisca la mia idea (anche se ritengo che non sia efficiente ...)
Cordialmente, Alex
A riguardo del "cinque" era solo in riferimento al link che avevi messo, dove il quadrato è di lato "5" ...
Aggiungo uno pseudo-codice, sperando che si capisca la mia idea (anche se ritengo che non sia efficiente ...)
'Questa è la tabella con le 24 permutazioni di 4 numeri;
'La 2^ colonna rappresenta quanti grattacieli si vedono da sx e da dx
'Ovviamente andrebbe costruita automaticamente e non inserita a mano come fatto dame ... :)
dim T(24,2)
T(0,0)=1234
T(1,0)=1243
T(2,0)=1324
T(3,0)=1423
T(4,0)=1342
T(5,0)=1432
T(6,0)=2134
T(7,0)=2143
T(8,0)=3124
T(9,0)=4123
T(10,0)=3142
T(11,0)=4132
T(12,0)=2314
T(13,0)=2413
T(14,0)=3214
T(15,0)=4213
T(16,0)=3412
T(17,0)=4312
T(18,0)=2341
T(19,0)=2431
T(20,0)=3241
T(21,0)=4231
T(22,0)=3421
T(23,0)=4321
T(0,1)=41
T(1,1)=32
T(2,1)=31
T(3,1)=22
T(4,1)=32
T(5,1)=23
T(6,1)=31
T(7,1)=22
T(8,1)=21
T(9,1)=12
T(10,1)=22
T(11,1)=13
T(12,1)=31
T(13,1)=22
T(14,1)=21
T(15,1)=12
T(16,1)=22
T(17,1)=13
T(18,1)=32
T(19,1)=23
T(20,1)=22
T(21,1)=13
T(22,1)=23
T(23,1)=14
'Questa è la tabella che rappresenta il quadrato da trovare
'La prima colonna inizialmente è vuota, nella seconda ci sono i grattacieli
dim Q(4,2)
Q(0,0)=0
Q(1,0)=0
Q(2,0)=0
Q(3,0)=0
Q(0,1)=31
Q(1,1)=22
Q(2,1)=32
Q(3,1)=14
for a = 0 to 20
if T(a,1)=Q(0,1) then
Q(0,0)=T(a,0)
else
goto [nexta]
end if
for b = a+1 to 21
if T(b,1)=Q(1,1) then
Q(1,0)=T(b,0)
else
goto [nextb]
end if
for c = b+1 to 22
if T(c,1)=Q(2,1) then
Q(2,0)=T(c,0)
else
goto [nextc]
end if
for d = c+1 to 23
if T(d,1)=Q(3,1) then
Q(3,0)=T(c,0)
else
goto [nextd]
end if
' Qui va inserita la procedura per il controllo verticale
[nextd]
next d
[nextc]
next c
[nextb]
next b
[nexta]
next a
print T(0,0)
print T(1,0)
print T(2,0)
print T(3,0)
Cordialmente, Alex
"axpgn":
...che risolvendo partendo da a1=1 dà la formula iniziale ... credo ...
Sono di più, ma non so quante: per $ n=4 $ ne trovo il doppio 572; per $ n=5 $ almeno il quadruplo, ma ne ho sicuramente perse per strada.
Ciao
@axpgn
Ti sei fatto capire benissimo ed ho già costruito tutto l' impalco di funzioni per generare le matrici anche se devo rivederne alcune. a dire il vero ne ho implementate varie versioni (con l' uso degli array, con le Collection e le stringhe, etc) ma ora credo che SOLO DOPO aver capito come calcolare, matematicamente parlando, il numero effettivo delle permutazioni possibili andrò a rivedere come modificare l' implementazione.
Comunque, se ti può interessare, ma non vorrei essere proprio io che ho creato il topic, a spingerlo OFF e non trovare rispota, eccoti un esempio per la generazione delle varie permutazioni possibili:
E' una macro Excel da inserire in un modulo qualsiasi. L' ingresso è la Sub Prova():
é solo un esempio.
il processo completo lo trovi in questo intervento di ForumExcel.
Ma, anche se apparentemente funziona. Se ci vuoi giocare funziona. Non crea TUTTE le permutazioni.
il concetto funzionale è:
crea una matrice di un determinato lato.
trova tutte le permutazioni attraverso al permutazione di colonne e righe.
Ero convinto che applicando tutte le matrici di permutazione alle colonne ed alle righe, avrei ottenuto tutte le possibili permutazioni.
Continuando nel thread, mi è stato fatto notare che alcune soluzioni valide non vengono generate e quindi trovate.
Per il numero dei grattacieli visti, i numeri esterni, è una proprietà secondaria e viene generata da una propria funzione dedicata al momento del bisogno.
Io l' ho utilizzata come firma per cercare la matrice di grattacieli.
Genero una firma attraverso i numeri esterni e, ad ogni permutazione trovata. Confronto le due firme e se sono identiche; Bingo! ho trovato la soluzione.
Purtroppo l' algoritmo principale, quello che genera le permutazioni non è corretto e non genera tutte le permutazioni. Purtroppo sono partito con un assunto sbagliato ed ho ottenuto un risultato sbagliato
Ti sei fatto capire benissimo ed ho già costruito tutto l' impalco di funzioni per generare le matrici anche se devo rivederne alcune. a dire il vero ne ho implementate varie versioni (con l' uso degli array, con le Collection e le stringhe, etc) ma ora credo che SOLO DOPO aver capito come calcolare, matematicamente parlando, il numero effettivo delle permutazioni possibili andrò a rivedere come modificare l' implementazione.
Comunque, se ti può interessare, ma non vorrei essere proprio io che ho creato il topic, a spingerlo OFF e non trovare rispota, eccoti un esempio per la generazione delle varie permutazioni possibili:
E' una macro Excel da inserire in un modulo qualsiasi. L' ingresso è la Sub Prova():
Option Explicit
Sub prova()
Dim Parola As String
Dim Parole As New Collection
Dim u As Long
Parola = "abc"
Set Parole = PermutaParola(Parola)
For u = 1 To Parole.Count
Debug.Print u; " "; Parole(u)
Next
End Sub
Function PermutaParola(Parola As String) As Collection
Dim p As Long
Dim sp As Long
Dim Valore As String
Dim Uscita As New Collection
Dim SubPermuta As New Collection
Dim SubParola As String
Dim SubUscita As String
If Len(Parola) > 1 Then
For p = 1 To Len(Parola)
Valore = Mid(Parola, p, 1)
SubParola = Replace(Parola, Valore, "")
Set SubPermuta = PermutaParola(SubParola)
For sp = 1 To SubPermuta.Count
Uscita.Add Valore & SubPermuta(sp)
Next
Next
Else
Uscita.Add Parola
End If
Set PermutaParola = Uscita
End Functioné solo un esempio.
il processo completo lo trovi in questo intervento di ForumExcel.
Ma, anche se apparentemente funziona. Se ci vuoi giocare funziona. Non crea TUTTE le permutazioni.
il concetto funzionale è:
crea una matrice di un determinato lato.
trova tutte le permutazioni attraverso al permutazione di colonne e righe.
Ero convinto che applicando tutte le matrici di permutazione alle colonne ed alle righe, avrei ottenuto tutte le possibili permutazioni.
Continuando nel thread, mi è stato fatto notare che alcune soluzioni valide non vengono generate e quindi trovate.
Per il numero dei grattacieli visti, i numeri esterni, è una proprietà secondaria e viene generata da una propria funzione dedicata al momento del bisogno.
Io l' ho utilizzata come firma per cercare la matrice di grattacieli.
Genero una firma attraverso i numeri esterni e, ad ogni permutazione trovata. Confronto le due firme e se sono identiche; Bingo! ho trovato la soluzione.
Purtroppo l' algoritmo principale, quello che genera le permutazioni non è corretto e non genera tutte le permutazioni. Purtroppo sono partito con un assunto sbagliato ed ho ottenuto un risultato sbagliato
Un paio di considerazioni ...
Come fatto notare giustamente da orsoulx, il numero di "quadrati" diversi è maggiore (li chiamo "quadrati" perché lascerei la parola "permutazioni" alle singole righe); il mio errore è stato quello di supporre che l'inserimento di un numero in più nella riga lasciasse immutato il resto (della riga), invece questo "inserimento" rimette in gioco permutazioni prima escluse ...
Giocando un po' con permutazioni e dismutazioni credo che il numero di quadrati diversi di lato $4$ sia $24*9*4*1=864$, mentre quelli di lato $5$ dovrebbero essere $120*44*12*3*1=190.080$.
Però ... questo non ti interessa più di tanto (se non come ordine di grandezza) perché il tuo obiettivo è quello di trovare un metodo per "scrivere" le soluzioni, dati i "grattacieli", non quello di calcolare quanti "quadrati" esistono ...
Ora, sono abbastanza sicuro che "l'algoritmo" che ho descritto funzioni per quello scopo, se non fosse che è poco efficiente velocemente ...
Io ti consiglierei di aprire un thread in Informatica riguardante la ricerca di un metodo efficiente per la creazione delle permutazioni (non dei quadrati) ed un altro in Algebra Lineare per la "manipolazione" delle matrici.
Cordialmente, Alex
P.S.: proverò a dare un'occhiata al tuo codice ma ... non è roba mia ...
Come fatto notare giustamente da orsoulx, il numero di "quadrati" diversi è maggiore (li chiamo "quadrati" perché lascerei la parola "permutazioni" alle singole righe); il mio errore è stato quello di supporre che l'inserimento di un numero in più nella riga lasciasse immutato il resto (della riga), invece questo "inserimento" rimette in gioco permutazioni prima escluse ...
Giocando un po' con permutazioni e dismutazioni credo che il numero di quadrati diversi di lato $4$ sia $24*9*4*1=864$, mentre quelli di lato $5$ dovrebbero essere $120*44*12*3*1=190.080$.
Però ... questo non ti interessa più di tanto (se non come ordine di grandezza) perché il tuo obiettivo è quello di trovare un metodo per "scrivere" le soluzioni, dati i "grattacieli", non quello di calcolare quanti "quadrati" esistono ...
Ora, sono abbastanza sicuro che "l'algoritmo" che ho descritto funzioni per quello scopo, se non fosse che è poco efficiente velocemente ...
Io ti consiglierei di aprire un thread in Informatica riguardante la ricerca di un metodo efficiente per la creazione delle permutazioni (non dei quadrati) ed un altro in Algebra Lineare per la "manipolazione" delle matrici.
Cordialmente, Alex
P.S.: proverò a dare un'occhiata al tuo codice ma ... non è roba mia ...
"axpgn":
Un paio di considerazioni ...
Come fatto notare giustamente da orsoulx, il numero di "quadrati" diversi è maggiore (li chiamo "quadrati" perché lascerei la parola "permutazioni" alle singole righe); il mio errore è stato quello di supporre che l'inserimento di un numero in più nella riga lasciasse immutato il resto (della riga), invece questo "inserimento" rimette in gioco permutazioni prima escluse ...
Giocando un po' con permutazioni e dismutazioni credo che il numero di quadrati diversi di lato $4$ sia $24*9*4*1=864$, mentre quelli di lato $5$ dovrebbero essere $120*44*12*3*1=190.080$.
Se mi spiegassi come sei arrivato ad avere questi valori, il ragionamento sotteso, eventuali considerazioni relative a proprietà che non conosco... Te ne sareei grato.
"axpgn":
Però ... questo non ti interessa più di tanto (se non come ordine di grandezza) perché il tuo obiettivo è quello di trovare un metodo per "scrivere" le soluzioni, dati i "grattacieli", non quello di calcolare quanti "quadrati" esistono ...
Ora, sono abbastanza sicuro che "l'algoritmo" che ho descritto funzioni per quello scopo, se non fosse che è poco efficiente velocemente ...
Io ti consiglierei di aprire un thread in Informatica riguardante la ricerca di un metodo efficiente per la creazione delle permutazioni (non dei quadrati) ed un altro in Algebra Lineare per la "manipolazione" delle matrici.
Cordialmente, Alex
P.S.: proverò a dare un'occhiata al tuo codice ma ... non è roba mia ...
Alex. Non vorrei mancarti di rispetto ma... Si... insomma... non sono qui a cercare un algoritmo per risolvere il gioco dei grattacieli ne ti ho passato il codice perché tu lo valutassi e mi dessi un riscontro a riguardo.
La risposta che cerco è quella dettata in topic ed ho narrato tutto il resto perchè ho pensato che potesse esser d' aiuto a capire quello che, magari, in topic, non era stato spiegato in modo esaustivo.
Quello che vorrei conoscere è:
la formula per conoscere il numero di possibili permutazioni, di un gruppo di dati, matrice, quadrato, (non so quale sia il termine giusto per nominarlo) con il vincolo che, lungo le righe e lungo le colonne, gli elementi non siano ripetuti.
un esempio di questa matrice è:
$((1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3))$
alcune sue possibili permutazioni potrebbero essere:
$((1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3))$ $((2,3,4,1),(3,4,1,2),(1,2,3,4),(4,1,2,3))$$((3,4,1,2),(2,3,4,1),(1,2,3,4),(4,1,2,3))$
A me servirebbe conoscere la formula che determina quante siano le permutazioni possibili perchè utilizzerei quel dato come limite nell algoritmo.
e vorrei poter capire e magari conoscere, un metodo, se esiste per poter permutare da uno stato ad un successivo oppure un precedente. nella permutazione di righe e colonne questo è possibile (dato uno stato iniziale ed un ordine alle matrici di permutazione e definito chi viene prima tra colonne e righe)
Se non esiste un concetto matematico, mi faccio bastare una spiegazione a parole, come, per esempio, sapere come hai ottenuto i numeri di cui sopra per affermare che le permutazioni siano quelle che hai detto.
il processo di conteggio delle possibilità può diventare algoritmo di risoluzione... vabbè... Buona notte... No... vista l' ora... buon giorno
Nella speranza di esser stato abbastanza chiaro nell' esposizione porgo sinceri saluti e ringrazio ancora per la cortese attenzione.
Credo d' aver trovato, finalmente, la risposta ad uno dei due quesiti. Certo, solo a ragionamento, non una vera e propria prava matematica.
Prendima una matrice di 4 righe e 4 colonne formata da righe e colonne di 4 elementi non ripetuti.
le possibili combinazioni di ogni riga sono: $4! = 24$
$(1,2,3,4,)$ $(1,2,4,3,)$ $(1,3,2,4,)$ $(1,3,4,2,)$ $(1,4,2,3,)$ $(1,4,3,2,)$ $(2,1,3,4,)$ $(2,1,4,3,)$ $(2,3,1,4,)$ $(2,3,4,1,)$ $(2,4,1,3,)$ $(2,4,3,1,)$ $(3,1,2,4,)$ $(3,1,4,2,)$ $(3,2,1,4,)$ $(3,2,4,1,)$ $(3,4,1,2,)$ $(3,4,2,1,)$ $(4,1,2,3,)$ $(4,1,3,2,)$ $(4,2,1,3,)$ $(4,2,3,1,)$ $(4,3,1,2,)$ $(4,3,2,1,)$
Prendiamo una di queste permutazioni e poniamola come prima riga della nostra matrice:
$((1,2,3,4),(?,?,?,?),(?,?,?,?),(?,?,?,?))$
Ne avremo $24 = 4!$
ora aggiungiamo una seconda riga tra quelle rimaste:
$((1,2,3,4),(1,2,4,3),(?,?,?,?),(?,?,?,?))$
di queste avremo la possibilità di posizionarne $23 = 4!-1$ (quella gia utilizzata sopra)
Procediamo anche con la successiva riga
$((1,2,3,4),(1,2,4,3),(1,3,2,4),(?,?,?,?))$
Con lo stesso ragionamento di prima possiamo dire che ho $22$ possibili combinazioni. pari a: $4!-2$
ed infine;
$((1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2))$
... $4!-3$
l epossibili permutazioni sono quindi:
$4! * (4!-1) * (4!-2)*(4!-3)$
Non saprei come scriverlo in modo generale se non :
$n!* (n!-1) * (n!-2)*...*(n!-n+1)$
a questo numero di permutazioni, ora, vanno defalcate le permutazioni che non soddisfano il vincolo di non avere lo stesso valore ripetuto lungo la colonna... Questo non riesco ad immaginarlo senza perdermici dentro
Prendima una matrice di 4 righe e 4 colonne formata da righe e colonne di 4 elementi non ripetuti.
le possibili combinazioni di ogni riga sono: $4! = 24$
$(1,2,3,4,)$ $(1,2,4,3,)$ $(1,3,2,4,)$ $(1,3,4,2,)$ $(1,4,2,3,)$ $(1,4,3,2,)$ $(2,1,3,4,)$ $(2,1,4,3,)$ $(2,3,1,4,)$ $(2,3,4,1,)$ $(2,4,1,3,)$ $(2,4,3,1,)$ $(3,1,2,4,)$ $(3,1,4,2,)$ $(3,2,1,4,)$ $(3,2,4,1,)$ $(3,4,1,2,)$ $(3,4,2,1,)$ $(4,1,2,3,)$ $(4,1,3,2,)$ $(4,2,1,3,)$ $(4,2,3,1,)$ $(4,3,1,2,)$ $(4,3,2,1,)$
Prendiamo una di queste permutazioni e poniamola come prima riga della nostra matrice:
$((1,2,3,4),(?,?,?,?),(?,?,?,?),(?,?,?,?))$
Ne avremo $24 = 4!$
ora aggiungiamo una seconda riga tra quelle rimaste:
$((1,2,3,4),(1,2,4,3),(?,?,?,?),(?,?,?,?))$
di queste avremo la possibilità di posizionarne $23 = 4!-1$ (quella gia utilizzata sopra)
Procediamo anche con la successiva riga
$((1,2,3,4),(1,2,4,3),(1,3,2,4),(?,?,?,?))$
Con lo stesso ragionamento di prima possiamo dire che ho $22$ possibili combinazioni. pari a: $4!-2$
ed infine;
$((1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2))$
... $4!-3$
l epossibili permutazioni sono quindi:
$4! * (4!-1) * (4!-2)*(4!-3)$
Non saprei come scriverlo in modo generale se non :
$n!* (n!-1) * (n!-2)*...*(n!-n+1)$
a questo numero di permutazioni, ora, vanno defalcate le permutazioni che non soddisfano il vincolo di non avere lo stesso valore ripetuto lungo la colonna... Questo non riesco ad immaginarlo senza perdermici dentro
"axpgn":
Giocando un po' con permutazioni e dismutazioni credo che il numero di quadrati diversi di lato $ 4 $ sia $ 24⋅9⋅4⋅1=864$
Se prima eran poche, adesso direi che sian troppe; per $ n=4 $ sono ragionevolmente certo del risultato $ 576 $. Preso un quadrato qualsiasi si possono permutare le colonne per ordinare la prima riga e poi permutare le righe (esclusa la prima) per ordinare anche la prima colonna. Il procedimento è invertibile e quindi per calcolare quanti quadrati diversi di lato $ n $ esistono avremo $ q_n= n!(n-1)!*r_n $, dove $ r_n $ è il numero di 'quadrati ridotti': quelli che hanno la prima riga e la prima colonna ordinate. Ora, $ r_4=4 $ e visto le poche possibilità non credo di averne saltata qualcuna, quindi $ q_n=576 $. Per $ r_5 $, invece, qualche dubbio mi resta.
@dracoscrigno:
ho dato un'occhiata alla discussione che hai linkato e mi pare non vi siate accorti che la corrispondenza fra quadrati e 'firme' non è biunivoca: ogni quadrato ha una e una sola firma, ma più quadrati possono avere la medesima firma. Ad esempio:
$ ((1,2,3,4),(2,4,1,3),(3,1,4,2),(4,3,2,1)) $ ha una firma che non cambia se si scambiano gli $ 1 $ ed i $ 4 $ delle posizioni centrali.
Per quanto riguarda la generazione di tutti i quadrati possibili un'idea potrebbe essere quella di partire dai quadrati ridotti e utilizzare l'algoritmo per le permutazioni che consiste nel fare sempre e solo uno swap ad ogni passo. In questo modo si avrebbe la certezza di non generare alcun doppione.
Ciao
"orsoulx":
[quote="axpgn"]Giocando un po' con permutazioni e dismutazioni credo che il numero di quadrati diversi di lato $ 4 $ sia $ 24⋅9⋅4⋅1=864$
Se prima eran poche, adesso direi che sian troppe; per $ n=4 $ sono ragionevolmente certo del risultato $ 576 $. Preso un quadrato qualsiasi si possono permutare le colonne per ordinare la prima riga e poi permutare le righe (esclusa la prima) per ordinare anche la prima colonna. Il procedimento è invertibile e quindi per calcolare quanti quadrati diversi di lato $ n $ esistono avremo $ q_n= n!(n-1)!*r_n $, dove $ r_n $ è il numero di 'quadrati ridotti': quelli che hanno la prima riga e la prima colonna ordinate. Ora, $ r_4=4 $ e visto le poche possibilità non credo di averne saltata qualcuna, quindi $ q_n=576 $. Per $ r_5 $, invece, qualche dubbio mi resta.[/quote]
Mi auguro possiate portare tanta pazienza perchè faccio veramente una fatica bestia a comprendervi
Questi pochi interventi hanno portato la mia autostima a $Capra^\infty$[size=150]Orsoulx[/size]. il numero che hai dichiarto; è un caso? oppure è anche il quadrato del fattoriale di n?
per n=4 -> $N!_2=576$
Quando parli di permutare le righe, o le colonne, intendi, immagino, quello di applicare una matrice di permutazione alla matrice quadrata... provo a spiegarlo in altro modo perché non sono certo di averlo detto nel modo giusto:
io parto, per esempio, con questo schema:
$((1,2,3,4),(2,4,1,3),(3,1,4,2),(4,3,2,1))$
che, decido avere questa matrice di permutazione:
$(1,2,3,4)$
applicandogli una tra le possibili matrici di permutazione (data dalle possibili permutazione dei valori della matrice stessa)
Arbitrariamente, per l' esempio, sclgo questa:
$(4,2,3,1)$ Dove, di fatto , ho scambiato il primo elemento con l' ultimo.
la matrice quadrata risultante sarebbe, quindi:
$((1,2,3,4),(2,4,1,3),(3,1,4,2),(4,3,2,1)) rArr (4,2,3,1) rArr ((4,2,3,1),(3,4,1,2),(2,1,4,3),(1,3,2,4))$
Lo chiedo perchè è una strada che ho percorso ma non mi pare che faccia uscire tutti i risultati possibili.
Il mio processo era quello di partire da una matrice preimpostata che ho denomintato PermutazioneUno e parte con la prima riga e prima colonna ordinata (1,2,3,4)
$ ((1,2,3,4),(2,4,1,3),(3,1,4,2),(4,3,2,1)) $
A questa applicavo tutte le matrici di permutazione sulle colonne ed alle risultanti applicavo il processo alle righe.
il lavoro geneava N!^2 risultati dei quali solo le prime due file, solo $N!*(N-1)$, erano matrici valide, le altre erano tutte copie di queste.
(Però, mi hai fatto venire un idea... le matriciquadrate, fammele chiamare, principali, le PermutazioniUno, non sono una sola ma sono più di una.
Trovate queste, ad esse si applica la permutazione delle righe e delle colonne... Mi sono gia perso
Scusatemi
"orsoulx":
@dracoscrigno:
ho dato un'occhiata alla discussione che hai linkato e mi pare non vi siate accorti che la corrispondenza fra quadrati e 'firme' non è biunivoca: ogni quadrato ha una e una sola firma, ma più quadrati possono avere la medesima firma. Ad esempio:
$ ((1,2,3,4),(2,4,1,3),(3,1,4,2),(4,3,2,1)) $ ha una firma che non cambia se si scambiano gli $ 1 $ ed i $ 4 $ delle posizioni centrali.
Non ce ne siamo accorti... A dire il vero, in fase di implementazione ci avevo pensato e pensavo che la "firma" fosse univoca. Tant' è che lo dichiaro più volte nel discorso intrapreso. l' ho azzardata e poi non indagata, perché, ai fini del gioco, non è importante.
Se la matrice trovata si "incastra", va bene. Il dato disponibile è la firma (il numero di grattacieli visti) Non si hanno altri dati a disposizione se non i valori esterni, come, per esempio, il grattacielo più alto in prossimità di un $1$.
Quindi, si, ci ho pensato. Ho tirato ad indovinare dicendo che erano biunivoche ma ho anche pensato che se mi sbagliavo non era importante... Spero
... Magari mi salti fuori con un altra verità ... Speriamo di no "orsoulx":
Per quanto riguarda la generazione di tutti i quadrati possibili un'idea potrebbe essere quella di partire dai quadrati ridotti e utilizzare l'algoritmo per le permutazioni che consiste nel fare sempre e solo uno swap ad ogni passo. In questo modo si avrebbe la certezza di non generare alcun doppione.
Ciao
Questa dei quadrati ridotti non l' ho ancora ben capita... sarebbe il quadrato dato dal defalcamento di una riga ed una colonna?
"dracoscrigno":
il numero che hai dichiarto; è un caso? oppure è anche il quadrato del fattoriale di n?
Pura coincidenza, ad esempio $ q_3=3!*2!*r_3 = 12 ne (3!)^2=36 $, perché $ r_3=1 $ (se la prima riga e la prima colonna sono $ 1,2,3 $ esiste un solo modo per completare il quadrato).
"dracoscrigno":
Però, mi hai fatto venire un idea... le matriciquadrate, fammele chiamare, principali, le PermutazioniUno, non sono una sola ma sono più di una.
Trovate queste, ad esse si applica la permutazione delle righe e delle colonne... Mi sono gia perso
Credo stiamo dicendo la medesima cosa: quelle che tu chiami 'matrici principali' sono le stesse che io chiamo 'quadrati ridotti'.
"dracoscrigno":
ma ho anche pensato che se mi sbagliavo non era importante...
Dipende. Ad esempio nel sudoku non sono considerati leciti schemi che portino a più di una soluzione.
"dracoscrigno":
Questa dei quadrati ridotti non l' ho ancora ben capita... sarebbe il quadrato dato dal defalcamento di una riga ed una colonna?
Vedi sopra: è un quadrato con prima riga e prima colonna ordinate in ordine crescente.
Ciao
grande Orsoulx.
ho capito!
non so valutare se quanto detto è, matematicamente provato ma lo trovo elegante e quanto mi basta per credere che sia così.
ho cominciato a leggere alcune cose trovate in rete (ho veramente molte lacune, troppe per poter comprendere una spiegazione più rigorosa di quanto affrontato fin ora)
vi ringrazio entrambi.
... ora che, credo d aver la risposta al primo quesito;
quante sono le permutazioni possibili?
passerei al secondo quesito.
Ho però l impressione che sarebbe meglio affrontarlo in un nuovo topic.
Sto maturando l idea di affrontarlo in un modo differente da quello che pensavo quando ho aperto questo topic e mi sembra che i due argomenti debbano esser separati.
dite che infrango il regolamento? non vorrei peccare di crossposting.
ho capito!
non so valutare se quanto detto è, matematicamente provato ma lo trovo elegante e quanto mi basta per credere che sia così.
ho cominciato a leggere alcune cose trovate in rete (ho veramente molte lacune, troppe per poter comprendere una spiegazione più rigorosa di quanto affrontato fin ora)
vi ringrazio entrambi.
... ora che, credo d aver la risposta al primo quesito;
quante sono le permutazioni possibili?
passerei al secondo quesito.
Ho però l impressione che sarebbe meglio affrontarlo in un nuovo topic.
Sto maturando l idea di affrontarlo in un modo differente da quello che pensavo quando ho aperto questo topic e mi sembra che i due argomenti debbano esser separati.
dite che infrango il regolamento? non vorrei peccare di crossposting.
ho detto una stupidaggine...
devo legare il valore di $r$ alla variabile $n$
... quanto vale $r$ ?
.... aspetta che rileggo tutto il thread... mi devo esser perso qualcosa
devo legare il valore di $r$ alla variabile $n$
... quanto vale $r$ ?
.... aspetta che rileggo tutto il thread... mi devo esser perso qualcosa
"orsoulx":
[quote="axpgn"]Giocando un po' con permutazioni e dismutazioni credo che il numero di quadrati diversi di lato $ 4 $ sia $ 24⋅9⋅4⋅1=864$
Se prima eran poche, adesso direi che sian troppe; per $ n=4 $ sono ragionevolmente certo del risultato $ 576 $. ...[/quote]
Spiego come ci sono arrivato ...
La prima riga può essere scritta in $24=4!$ modi diversi ...
Le altre tre sono dismutazioni della prima, che nel nostro caso sono $!4=9$, quindi la seconda riga può essere scritta in $9$ modi diversi ...
Purtroppo non è possibile limitarsi a prenderne tre su nove perché queste nove non sono dismutazioni tra loro ... a mano però è facile ricavare che solo $4$ rimangono disponibili dopo aver fissato la seconda riga e ovviamente l'ultima è obbligata dopo aver fissato la terza, quindi in totale $24*9*4*1=864$ ...
Lo stesso ragionamento per $n=5$ ...
Dov'è l'errore?
Cordialmente, Alex
"dracoscrigno":
... quanto vale r ?
A saperlo, saperlo! Non ho trovato di meglio che provare. Per $ n=4 $ è facile $ r_4=4 $; ma già per $ r_5 $ son dolori: per tentativi a mano sicuramente almeno 54.
"axpgn":
Dov'è l'errore?
Nel $ 4 $. Delle $ 9 $ dismutazioni $ 3 $, quelle costituite da due cicli di ordine $ 2 $ (due scambi fra coppie diverse) lasciano ancora $ 4 $ possibilità per la terza. Epperò le altre $ 6 $ formate da un unico ciclo di ordine $ 4 $ ne permettono solo $ 2 $ successive. Esempio $ ((1,2,3,4),(2,3,4,1)) $, se la terza riga inizia con $ 3 $ può essere solo $ 3,4,1,2 $ e se inizia con $ 4 $ solo $ 4,2,1,3 $. $ 3*4+6*2=24 $ che conferma quanto ho trovato per altra via.
Ciao
Trovato! ... nel senso che ho trovato su Internet ...
Ho scoperto i "Latin Squares" ed il loro numero per quadrati di ordine $n$ è $L_n=n!*(n-1)!*R_n$ (come detto da orsoulx) dove i primi valori di $R_n$ sono $R_1=1, R_2=1, R_3=1, R_4=4, R_5=56, R_6=9408$.
Per maggiori informazioni qui
Cordialmente, Alex
Ho scoperto i "Latin Squares" ed il loro numero per quadrati di ordine $n$ è $L_n=n!*(n-1)!*R_n$ (come detto da orsoulx) dove i primi valori di $R_n$ sono $R_1=1, R_2=1, R_3=1, R_4=4, R_5=56, R_6=9408$.
Per maggiori informazioni qui
Cordialmente, Alex
GRazie Axpgn.
Ho cercato di seguire i vari link nella pagina che hai proposto.
immagino che quel $r_n$ postato da Orsoulx sia questo:
$((1,1),(2,1),(3,1),(4,4),(5,56),(6,9408),(7,16942080),(8,535281401856),(9,377597570964258816),(10,7580721483160132811489280),(11,5363937773277371298119673540771840))$
immagino che partano da $1$, uno.
e sto notando che dalla matrice di grado $7$ in poi, mi sa che serve un bel calcolatore
bè... direi che ora ho un bel pò di materiale su cui studiare. Grazie all' ultimo post qui sopra sono riuscito anche ad arrivare a:
wikipedya -> quadrati latini
Grazie mille ancora
Ho cercato di seguire i vari link nella pagina che hai proposto.
immagino che quel $r_n$ postato da Orsoulx sia questo:
$((1,1),(2,1),(3,1),(4,4),(5,56),(6,9408),(7,16942080),(8,535281401856),(9,377597570964258816),(10,7580721483160132811489280),(11,5363937773277371298119673540771840))$
immagino che partano da $1$, uno.
e sto notando che dalla matrice di grado $7$ in poi, mi sa che serve un bel calcolatore
bè... direi che ora ho un bel pò di materiale su cui studiare. Grazie all' ultimo post qui sopra sono riuscito anche ad arrivare a:
wikipedya -> quadrati latini
Grazie mille ancora
"dracoscrigno":
... immagino che quel $r_n$ postato da Orsoulx sia questo: ...
Yes
"axpgn":
Trovato! ... nel senso che ho trovato su Internet ...
Sono soddisfatto: per $ n=5 $ ne ho perse solo due!
Da quel che ho capito, per $ n>11 $ non se ne conosce esattamente il numero.
"dracoscrigno":
e sto notando che dalla matrice di grado 7 in poi, mi sa che serve un bel calcolatore
Già con $ n=6 $ si macina abbastanza. Tenendo conto che per generare una permutazione e ricavarne la firma occorrono più di 100 operazioni elementari e che le permutazioni da esaminare sono più di 800 milioni, mi aspetterei un tempo di esecuzione nell'ordine dei minuti.
Ciao
se ho ben capito gia con una matrice di grado 6 siamo al limite. da grado 7 in poi, un risolutore diventa improponibile.
Lo affermo pensando ad un algoritmo che macina dalla prima all ultima mayrice ed il caso vuole che il risultato sia tra le ultime.
ma.
quello che non mi è chiaro è la formula per determinare $r_n$
seguendo i link a fondo pagina, alla voce formula, non arrivo mai ad una formula definitiva ma in un circolo vizioso che ritorna alla stessa pagina dove, per conoscere $r_n$ devo conoscere tutte le permutazioni possibili e, per conoscere tutte le permutazioni possibili, devo conoscere $r_n$.
... cosa mi sfugge?
Lo affermo pensando ad un algoritmo che macina dalla prima all ultima mayrice ed il caso vuole che il risultato sia tra le ultime.
ma.
quello che non mi è chiaro è la formula per determinare $r_n$
seguendo i link a fondo pagina, alla voce formula, non arrivo mai ad una formula definitiva ma in un circolo vizioso che ritorna alla stessa pagina dove, per conoscere $r_n$ devo conoscere tutte le permutazioni possibili e, per conoscere tutte le permutazioni possibili, devo conoscere $r_n$.
... cosa mi sfugge?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo