Permutazioni e Assembler

[janjan]

Non sono riuscito a creare un programma in assembler in grado di scrivere su vettore le permutazioni dei primi "n" num. naturali, n<6.
Qualcuno può essermi d'aiuto??? Ho in mente solo versioni ricorsive ma in assembler la ricorsione non è facilissima... va bene anke solo l'algoritmo in C, grazie in anticipo a tutti coloro che collaboreranno!!!!!

Jan

[a2000]

io c'avrei questo algoritmino cosiddetto di g: :

 v(1, 1) = 1: iMax = 1
 For n = 2 To NN
  For i = 1 To iMax
   v(i, n) = n
  Next i
  For k = n - 1 To 1 Step -1
   For i = 1 To iMax
    ix = i + (n - k) * iMax
    For j = 1 To k - 1
     v(ix, j) = v(i, j)
    Next j
    v(ix, k) = n
    For j = k To n - 1
     v(ix, j + 1) = v(i, j)
    Next j
   Next i
  Next k
  iMax = iMax * n
 Next n

molto semplice, anzi molto semplificabile con i potenti shortcut dell'assembler.

interessa ?

[a2000]

sono 19 righe ma per amore di sintesi (ma anche per semplificare la trasposizione tal quale in assembler) si possono ridurre a ... 8-9

[lombardp]

Il problema mi ha interessato, ed ho buttato giù dal nulla questo algoritmino, che sembra funzionare... credo.

#define N 4     // Numero di numeri
#define M 24    // Numero permutazioni

int main(int argc, char* argv[])
{
   int mm,nn,pp;

   int num[N];  // Array dei numeri
   int appo;

   // Inizializzazione array
   for (nn=0;nn<N;nn++) num[nn] = nn;
   // Scrittura della prima permutazione
   for (nn=0;nn<N;nn++) printf("%d",num[nn]);
   printf("\n");

   // Ciclo sulle altre permutazioni
   for (mm=1;mm<M;mm++)
   {
      pp = M;
      for (nn=N;nn>0;nn--)
      {
         pp = pp / nn;
         if ((mm%pp)==0)
         {
            appo = num[nn-2];
            num[nn-2] = num[nn-1];
            num[nn-1] = appo;
            nn = 0;
         }
      }
      // Scrittura permutazione risultante
      for (nn=0;nn<N;nn++) printf("%d",num[nn]);
      printf("\n");
   }

   getch();

	return 0;
}

Ricordavo di aver letto da qualche parte che si potevano enumerare tutte le permutazioni ogni volta scambiando tra di loro due elementi. Senza ripetizioni.

Dovevo solo trovare la legge che definiva la sequenza degli scambi. Con un modo spudoratamente empirico (osservando un paio di casi), ho buttato giù l'accozzaglia di codice sopra riportata.

[verloc]

Hai verificato che il numero di permutazioni sia esatto?

N!


L'algoritmo è quello del contachilometri.

Cerca con il motore,mi pare abbiamo trattato già l'argomento.

[janjan]

Grazie mille per le risposte!!!!

Adesso ci ragiono un po' sopra e spero di riuscire a capirle...
Ciao!!! Jan

[verloc]

Originally posted by "a2000"

io c'avrei questo algoritmino cosiddetto di g: :

 v(1, 1) = 1: iMax = 1
 For n = 2 To NN
  For i = 1 To iMax
   v(i, n) = n
  Next i
  For k = n - 1 To 1 Step -1
   For i = 1 To iMax
    ix = i + (n - k) * iMax
    For j = 1 To k - 1
     v(ix, j) = v(i, j)
    Next j
    v(ix, k) = n
    For j = k To n - 1
     v(ix, j + 1) = v(i, j)
    Next j
   Next i
  Next k
  iMax = iMax * n
 Next n

molto semplice, anzi molto semplificabile con i potenti shortcut dell'assembler.

interessa ?

Capisco la fretta e il poco tempo a disposizione,ma dovresti scrivere gli snippets con una maggiore leggibilità.
Ne converrai che adoperare una quindicina di lettere dell'alfabeto per identificare indici e vettori non aiuta molto se ci devi mettere 2 ore per capire il senso delle istruzioni.
Tieni inoltre conto che non tutti capiscono la sintassi del basic.
Noi tutti ti ringraziamo per quello che dai al forum (sono serio) ma ti prego,scrivi meglio (il naming delle variabili per esempio) e commenta.


Cmq si,a me imteressa ! (magari con qualche link ai migliori algoritmi per il calcolo combinatorio).

per Lombard: credo che quello di a2000 sia il tipo di alg. giusto
perchè non contiene neanche un IF.
Mi sto convincendo che l'algoritmo che preveda solo istruzioni di swapping
sia una leggenda(anch'io pensavo esistesse...ma chissà...)


PS Mi pare proprio che si chiami di Penetrazione giusto?

[lombardp]

Originally posted by "verloc"


per Lombard: credo che quello di a2000 sia il tipo di alg. giusto
perchè non contiene neanche un IF.
Mi sto convincendo che l'algoritmo che preveda solo istruzioni di swapping
sia una leggenda(anch'io pensavo esistesse...ma chissà...)

Il codice che ho buttato giù contiene un'IF e due divisioni, ma per il resto fa solamente swap tra due numeri, uno ed un solo swap ad ogni permutazione (l'IF e le divisioni servono per capire qualìè lo swap giusto).

[verloc]

Originally posted by "lombardp"



Il codice che ho buttato giù contiene un'IF e due divisioni, ma per il resto fa solamente swap tra due numeri, uno ed un solo swap ad ogni permutazione (l'IF e le divisioni servono per capire qualìè lo swap giusto).

cmq non sono stato chiaro
non intendevo assolutamente criticare il tuo codice...(me ne guardo bene )
anzi ritengo sia eccellente(non l'ho detto).

[a2000]

Originally posted by "lombardp"

Il problema mi ha interessato, ed ho buttato giù dal nulla questo algoritmino, che sembra funzionare... credo.
....

ci siamo "annusati" e riconosciuti ... credo ig:
(anche se non ti sei ancora iscritto alla setta dei testimoni di nabla)
e per questo ti dico che è bellino però ...
... però, se non ho tradotto male dall'ostroCoto, ci deve essere un errore che porta alla ripetizione di alcune permutazioni (e all'assenza di altre) già con 4 elementi.

appena mi è passata l'inca++atura e le code polemiche della riunione di stamattina ti mando il file.

[a2000]

Originally posted by "verloc"



Capisco la fretta e il poco tempo a disposizione,ma dovresti scrivere gli snippets con una maggiore leggibiltà.
Ne converrai che adoperare una quindicina di lettere dell'alfabeto per identificare indici e vettori non aiuta molto se ci devi mettere 2 ore per capire il senso delle istruzioni.
Tieni inoltre conto che non tutti capiscono la sintassi del basic.
Noi tutti ti ringraziamo per quello che dai al forum (sono serio) ma ti prego,scrivi meglio (il naming delle variabili per esempio) e commenta.


Cmq si,a me imteressa ! (magari con qualche link ai migliori algoritmi per il calcolo combinatorio).

per Lombard: credo che quello di a2000 sia il tipo di alg. giusto
perchè non contiene neanche un IF.
Mi sto convincendo che l'algoritmo che preveda solo istruzioni di swapping
sia una leggenda(anch'io pensavo esistesse...ma chissà...)

PS Mi pare proprio che si chiami di Penetrazione giusto?[/size]

Fratello lo sai che ti amo.
e ho capito che ti sei un po' inC++ per il 3D negletto delle comparazioni.

Hai ragione l'algoritmo l'ho buttato giù così di "getto".
Hai ragione le regole di naming sono forse, sorprendentemente, la cosa più fondamentale della programmazione e azzardo che siano all'origine della programmazione ad oggetti.
Comunque in Fortran l'uso consolidato è di tipo algebrico e quindi con nomi di pochi caratteri ....
L'agoritmo di penetrazione è questo:


12 penetra il 2 in tutte le permutazioni a 1 elemento (1)
21

123 penetra il 3 in tutte le permutazioni a 2 elementi
213
132
231
312
321

1234 penetra il 4 in tutte le permutazioni a 3 elementi
2134
1324
2314
3124
3214

1243
2143
1342
2341
3142
3241

1423
2413
1432
2431
3412
3421

4123
4213
4132
4231
4312
4321

....


... ne riparliamo.





P.S.
questi vogliono fare R&D come si fa lobbing in parlamento ...

[lombardp]

Originally posted by "a2000"


... però, se non ho tradotto male dall'ostroCoto, ci deve essere un errore che porta alla ripetizione di alcune permutazioni (e all'assenza di altre) già con 4 elementi.

Guardando meglio... è vero!!!

Quando ho un po' di tempo lo riguardo.


<...dopo un po' di riflessione...>


VERLOC : Mi sa che hai ragione, non mi riesce trovare una sequenza sistematica di permutazioni. Il mio programmino non sembra avere speranze di funzionare.

[a2000]

sì ... sì ....

ma l'iscrizione agli ADORATORI DEL (detto anche Mont Venus) ???? g:

[lombardp]

[quote="a2000"]sì ... sì ....

ma l'iscrizione agli ADORATORI DEL (detto anche Mont Venus) ???? ig:[/quot]

Il link al modulo di iscrizione in PDF? ...

[a2000]

in P vuoi dir ...

[verloc]

TA DAAAAAAAA! [/siz]

#include <stdlib.h>
#include <stdio.h>


template<class T>
inline void SWAP(T &a, T &b)
{T dum=a; a=b; b=dum;}
  
  
void generate(int N,char *v)
{  
   int c;
   
  if (N == 1)  {printf("%s\n",v); return; }
  for (c = 1; c <=N; c++)
  {
    generate(N-1,v);
    SWAP(N % 2 ? v[0] :v[c-1],v[N-1] );
        
  }
  
}    

void main()
{
    
    
    char aElements[]={'a','b','c','d','\0'};
    generate(4,aElements);
    
getchar();
}

....BUGIA

credevate che l'avessi fatto io?


Ho fatto una "leggerissima trasposizione" dell'algoritmo di Heap
spiegato da un certo...Robert Sedgewick.

Quella sopra è la versione ricorsiva.
Per quella iterativa e per la trattazione sintetica del problema
http://www.cs.princeton.edu/~rs/talks/perms.pdf

Sono sotto tesi quindi l'altra versione fatela voi.
Sarebbe utile farne una funzione un po più generica (template etc)
Adesso sfogatevi con i benchmark (sarebbe interessante un confronto con il codice di a2000)che io ogni tanto vi vengo a guardare.

[a2000]

bravo, così si fa:

1) definizione del problema (janjan)
2) soluzione personale del problema (a2000, lombardp)
3) soluzioni al problema dello "stato dell'arte" (verloc)
4) nuova soluzione personale (al solito ahimè: ottimizzazione di una soluzione dello "stato dell'arte") (?)

prova-studia-riprova è l'unica permutazione giusta !

non vanno bene invece:

studia-prova-riprova (somaro)
prova-riprova-studia (dilettante)
studia-riprova-prova (secchione svogliato)
riprova-prova-studia (svogliato)
riprova-studia-prova (bravo ma non si applica)

[cionci]

Originally posted by "verloc"

TA DAAAAAAAA! [/siz]

Non vale...farlo ricorsivo era troppo facile... Poi mi pare che fosse stato richiesto esplicitamente non ricorsivo...

[verloc]

Scherzavo...Cionci.
In realtà non ho fatto nulla,ho solo dato una aggiustatina(quasi un copia incolla).
Sul pdf c'è tutto,anche quella iterativa,basta cambiare davvero poco.

[a2000]

verloc, dopo l'11 settembre non è più obbligatorio essere sempre concilianti.

<---------