Newsgroup: it.scienza.informatica
Titolo: Permutazioni - Matrici

Ciao a tutti,
sto cercando un algoritmo semplice per trovare tutte le permutazioni 
possibili di una matrice quadrata.
Vorrei cioè permutare le righe (e rispettive colonne):
es. 3X3 (A,B,C rappresentano le etichette di riga
ABC; ACB; BCA; BAC; CAB; CBA
Qualcuno ha qualche suggerimento?
grazie a tutti
ste

 ha scritto nel messaggio
news:3E83180A...@inwind.it...

Ecco tre metodi per generare tutte le permutazioni di un insieme:
sono tre metodi che ho scritto in java...il principio è applicabile
anche alle righe di una mtrice e qualsiasi altra cosa...
Si tratta di algoritmi per la risoluzione di problemi algebrici.
Ciao!
// genera permutazioni 1 versione
   public static void Permutazioni(ListaSI a){
      if(a.EstVuota())
         return;
      int[] vett = new int[a.Lunghezza()];
      int i,j,h,k,maxi,maxj,appoggio,conta;
      for(i=0;i<a.Lunghezza();i++)
         vett[i] = i;
      TextIO.putln();
      for(i=0;i<a.Lunghezza();i++)
         TextIO.put(" "+a.Car(vett[i]));
      conta=0;
      do{
         conta++;
         maxi = -1;
         for(i=0;i<(vett.length-1);i++)
            if(vett[i]<vett[i+1])
               maxi = i;
         if(maxi==-1)
            break;
         maxj = 0;
         for(j=(maxi+1);j<vett.length;j++)
            if(vett[j]>vett[maxi])
                maxj = j;
         for(j=(maxi+1);j<vett.length;j++)
            if((vett[j]>vett[maxi])&&(vett[j]<vett[maxj]))
                maxj = j;
         appoggio = vett[maxi];
         vett[maxi] = vett[maxj];
         vett[maxj] = appoggio;
         h = (vett.length - (maxi+1))/2;
         for(k=0;k<h;k++){
            appoggio = vett[maxi+k+1];
            vett[maxi+k+1] = vett[vett.length-k-1];
            vett[vett.length-k-1] = appoggio;
         }
         TextIO.putln();
         for(i=0;i<a.Lunghezza();i++)
             TextIO.put(" "+a.Car(vett[i]));
      }while(maxi!=-1);
   }
   // genera permutazioni 2 versione
   public static void Permutazioni2(ListaSI a,ListaSI b,int[] stato){
      if(a.EstVuota())
         return;
      int i,j,h,k,maxi,maxj,appoggio,conta;
      if(stato[a.Lunghezza()]==0){
         for(i=0;i<a.Lunghezza();i++)
            stato[i] = i;
         stato[a.Lunghezza()]=-1;
      }
      if(stato[a.Lunghezza()]==-1){
         while(!b.EstVuota())
            b.Cdr(0);
         for(i=0;i<a.Lunghezza();i++)
            b.Cons(a.Car(stato[i]),i);
         maxi = -1;
         for(i=0;i<(stato.length-2);i++)
            if(stato[i]<stato[i+1])
               maxi = i;
         if(maxi==-1){
            stato[a.Lunghezza()]=1;
            return;
         }
         maxj = 0;
         for(j=(maxi+1);j<(stato.length-1);j++)
            if(stato[j]>stato[maxi])
                maxj = j;
         for(j=(maxi+1);j<(stato.length-1);j++)
            if((stato[j]>stato[maxi])&&(stato[j]<stato[maxj]))
                maxj = j;
         appoggio = stato[maxi];
         stato[maxi] = stato[maxj];
         stato[maxj] = appoggio;
         h = ((stato.length - 1) - (maxi+1))/2;
         for(k=0;k<h;k++){
            appoggio = stato[maxi+k+1];
            stato[maxi+k+1] = stato[(stato.length-1)-k-1];
            stato[(stato.length-1)-k-1] = appoggio;
         }
      }
   }
   // genera permutazioni 3 versione
   public static void Permutazioni3(int[] l,int[] r,int ind){
      if(ind==l.length){
         TextIO.putln();
         for(int i=0;i<ind;i++)
            TextIO.put(" "+r[i]);
         return;
      }
      boolean trovato;
      for(int i=0;i<l.length;i++){
      trovato=false;
         for(int j=0;j<ind;j++)
            if(l[i]==r[j])
               trovato=true;
         if(!trovato){
            r[ind]=l[i];
            Permutazioni3(l,r,ind+1);
         }
      }
      return;
   }

 ha scritto nel messaggio
news:3E83180A...@inwind.it...

Sarebbe meglio tu indicassi in che linguaggio lavori...
Comunque, direttamente dal modulo List del linguaggio Haskell, ecco il
metodo per effettuare le permutazioni:
permutations            :: [a] -> [[a]]
permutations []         =  [[]]
permutations (x:xs)     =  [zs | ys <- permutations xs, zs <- interleave x
ys ]
  where interleave          :: a -> [a] -> [[a]]
        interleave x []     =  [[x]]
        interleave x (y:ys) =  [x:y:ys] ++ map (y:) (interleave x ys)

PrimoPrincipio wrote:
[CUT]
Grazie 1000!
ste

 Sarebbe meglio tu indicassi in che linguaggio lavori...
Mi piacerebbe lavorare in ambiente R (
www.r-project.org
), dato che poi 
devo fare delle operazioni un po' complicate su queste matrici.
Ciao
Ste


Hmmm non conosco R, però conosco J, ed è molto potente:
www.jsoftware.com
\begin{quote}
The J language is based on a small set of simple and consistent rules with
powerful
facilities for defining new operations. The basic datatype is a
multi-dimensional array,
and the built-in functions are highly optimized for operating on whole
arrays at a time,
allowing you to manipulate data far more easily than with conventional
software. The
concise syntax and interactive environment make J ideal for applications
such as
statistics, financial and actuarial analysis, modeling, simulation and
educational use.
\end{quote}
Vedi la brochure 
http://www.jsoftware.com/Jbro.pdf
 per + info.