orsoulx ha scritto:axpgn ha scritto: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.
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$Orsoulx. 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 ha scritto:@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 ha scritto: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?
