Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda dracoscrigno » 30/04/2017, 00:30

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à :)
dracoscrigno
New Member
New Member
 
Messaggio: 2 di 52
Iscritto il: 29/04/2017, 21:51

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda axpgn » 30/04/2017, 15:21

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! :lol: ), 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 ... :-D

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 ... :D

Cordialmente, Alex
axpgn
Cannot live without
Cannot live without
 
Messaggio: 8263 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda dracoscrigno » 30/04/2017, 16:52

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 :P . 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?
dracoscrigno
New Member
New Member
 
Messaggio: 5 di 52
Iscritto il: 29/04/2017, 21:51

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda axpgn » 30/04/2017, 19:38

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 ... :D
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 ...)

Codice:
'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
Cannot live without
Cannot live without
 
Messaggio: 8264 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda orsoulx » 30/04/2017, 20:04

axpgn ha scritto:...che risolvendo partendo da a1=1 dà la formula iniziale ... credo ... :-D

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
Stephen Wolfram non mi è simpatico, anche perché il malefico Wolfram|Alpha non mi permette di credere che $ e^\pi=(640320^3+744)^(1/\sqrt(163)) $.
"Sono venticinque secoli che la filosofia inquadra i problemi, ma non scatta mai la foto.” - Edoardo Boncinelli, L'infinito in breve.
orsoulx
Cannot live without
Cannot live without
 
Messaggio: 1110 di 3906
Iscritto il: 30/12/2014, 11:13

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda dracoscrigno » 30/04/2017, 22:20

@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():
Codice:
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 :? :| :(
dracoscrigno
New Member
New Member
 
Messaggio: 6 di 52
Iscritto il: 29/04/2017, 21:51

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda axpgn » 01/05/2017, 00:31

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 ... :D
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 ... :wink:
axpgn
Cannot live without
Cannot live without
 
Messaggio: 8265 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda dracoscrigno » 01/05/2017, 05:25

axpgn ha scritto: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 ha scritto: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 ... :D
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 ... :wink:


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 :lol:

Nella speranza di esser stato abbastanza chiaro nell' esposizione porgo sinceri saluti e ringrazio ancora per la cortese attenzione.
dracoscrigno
New Member
New Member
 
Messaggio: 7 di 52
Iscritto il: 29/04/2017, 21:51

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda dracoscrigno » 01/05/2017, 11:54

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 :lol:
dracoscrigno
New Member
New Member
 
Messaggio: 9 di 52
Iscritto il: 29/04/2017, 21:51

Re: Permutare una matrice quadrata di valori e numero di permutazioni possibili

Messaggioda orsoulx » 01/05/2017, 12:10

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.
@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
Stephen Wolfram non mi è simpatico, anche perché il malefico Wolfram|Alpha non mi permette di credere che $ e^\pi=(640320^3+744)^(1/\sqrt(163)) $.
"Sono venticinque secoli che la filosofia inquadra i problemi, ma non scatta mai la foto.” - Edoardo Boncinelli, L'infinito in breve.
orsoulx
Cannot live without
Cannot live without
 
Messaggio: 1112 di 3906
Iscritto il: 30/12/2014, 11:13

Prossimo

Torna a Giochi matematici

Chi c’è in linea

Visitano il forum: Google Adsense [Bot] e 1 ospite