Permutazioni matrice vincolata in java

[tidus1717]

Salve a tutti..ho un problema con tutte le possibili permutazioni di una matrice vincolata..
se ad esempio ho una matrice A:
3 6 7
4 8 9
1 2 5
e voglio generare tutte le possibili permutazioni di A senza mai muovere ad esempio i numeri 7 e 5 dalla loro posizione iniziale..come posso fare in java?Grazie mille in anticipo a chi mi aiuterà con questo problema!!!

[VincenzoTheBest]

Originariamente inviato da tidus1717
Salve a tutti..ho un problema con tutte le possibili permutazioni di una matrice vincolata..
se ad esempio ho una matrice A:
3 6 7
4 8 9
1 2 5
e voglio generare tutte le possibili permutazioni di A senza mai muovere ad esempio i numeri 7 e 5 dalla loro posizione iniziale..come posso fare in java?Grazie mille in anticipo a chi mi aiuterà con questo problema!!!

Ti interessa "solo" calcolare il numero di permutazioni oppure vuoi anche rappresentare le matrici con gli elementi permutati?

[tidus1717]

Mi servono le rappresentazioni delle permutazioni della matrice...

[VincenzoTheBest]

Originariamente inviato da tidus1717
Mi servono le rappresentazioni delle permutazioni della matrice...

Ok! Devi prima trovare un concetto/algoritmo per produrre le matrici permutate e successivamente magari possiamo provare a discutere riguardo la sua implementazione.

[tidus1717]

un ragazzo mi ha dato una idea per l'implementazione ma non so se sia giusta:
Credo che potresti semplificare l'approccio al problema convertendo la matrice MxN in un vettore di lunghezza M*N, ovvero con l'elemento [1,1] nella posizione 1, e l'elemento [3,3] nella posizione 9.

Detto questo, potresti usare un altro vettore che definisce l'ordine di lettura dei numeri presenti nel vettore, sapendo che NON devi toccare le posizioni 3 e 9 (che sono i numeri 7 e 5 di cui hai parlato)

Viene naturale pensare al seguente pseudo codice:

Finché (non si è raggiunta l'ultima permutazione)
.....Prossima_permutazione(vettore);
.....SE (gli elementi da tenere fermi si sono mossi) continue;
.....Scrivi_in_colonna(vettore);
Fine

Dove "continue" è la codifica in C (e credo anche in Java sia uguale) per passare alla prossima iterazione del ciclo, senza eseguire le istruzioni rimanenti,

Questo algoritmo va a generare tutte le permutazioni del vettore e scarta quelle che hanno gli elementi da tenere fermi spostati.

A occhio l'efficienza non è il massimo... verranno generate tantissime permutazioni che tanto dovranno essere scartate! Possiamo fare di meglio:

Il vettore non sarà più di lunghezza M*M, bensì di lunghezza (M*N-K) dove K è il numero di "eccezioni" che non vuoi muovere.

Adesso lo pseudocodice diventa:

Finché (non si è raggiunta l'ultima permutazione)
.....Prossima_permutazione(vettore);
.....vettore2 = Ripristina_elementi(vettore)
.....Scrivi_in_colonna(vettore2);
Fine

Questo algoritmo genera solo le permutazioni essenziali e aggiunge gli elementi (ripristinandoli) e scrive il nuovo vettore (vettore2) che contiene la permutazione.

N.B. La funzione Scrivi_in_colonna() simulerà una visualizzazione di matrice, se tu vuoi tornare i dati in una vera matrice basta usare un'altra funzione..

[VincenzoTheBest]

Tutto quello di cui hai bisogno è:
- Una classe Matrice
- Una classe che fornisca in output una lista/array di oggetti Matrice, nella quale vai ad implementare un algoritmo per calcolare le permutazioni sul vettore che rappresenta, in forma lineare, la matrice vincolata presa in input.

[tidus1717]

ma non so come implementare la permutazione..mi potresti fare almeno uno pseudocodice per favore...

[VincenzoTheBest]

Originariamente inviato da tidus1717
ma non so come implementare la permutazione..mi potresti fare almeno uno pseudocodice per favore...

Consideriamo la seconda classe che ti ho consigliato di costituire e la chiamiamo PmutMatriceVincolata (ipotizzando che le matrici contengano interi)

public class PmutMatriceVincolata{

  private Matrice mv;
  private int vincoli[];
  ...altri campi
  
  /*
   * @param mv matrice di cui creare le permutazioni
   * @param vincoli array di elementi che all'interno della matrice non cambiano la propria pos.
   */
  public PmutMatriceVincolata(Matrice mv, int vincoli[]){
       this.mv = mv;
       this.vincoli = vincoli;
  }

  private LinkedList linearizzaMatrice(){
    ...
  }

  public Matrice[] getMatriciPmut(){
     //qui implementi l'algoritmo per calcolare le permutazioni
     //puoi rappresentarle tramite array, liste o stringhe come meglio credi..

    //il totale delle permutazioni dunque è fattoriale( linearizzaMatrice().size() - vincoli.length )
  }

  ...
}

[tidus1717]

Grazie per l'aiuto...il mio problema è che non riesco a capire come scrivere in java il fatto che degli elementi devono rimanere fermi durante la permutazione..

[VincenzoTheBest]

Originariamente inviato da tidus1717
Grazie per l'aiuto...il mio problema è che non riesco a capire come scrivere in java il fatto che degli elementi devono rimanere fermi durante la permutazione..

Alternativamente potresti generare la permutazione senza gli elementi fissi ed inserirli solo quando vai a comporre la matrice.
Per fare ciò ti salvi le loro posizioni all'interno della rappresentazione lineare della matrice!

Riferendomi al tuo esempio:
una possibile rappresentazione lineare della matrice è:
3, 6, 7, 4, 8, 9, 1, 2, 5