Newsgroup: it.comp.lang.c
Titolo: Algoritmo per Permutazioni.

Ciao, sto cercando il modo migliore per realizzare un algoritmo che da
un numero n di numeri mi ricavi tutte le permutazioni possibili. Non
sono ancora riuscito a creare nulla di buono!!
Nessuno mi saprebbe aiutare?
Grazie.

 un numero n di numeri mi ricavi tutte le permutazioni possibili.
Non so se questo è il modo *migliore*, comunque prova a dargli
un'occhiata:
--//--
#include <stdlib.h>
#include <stdio.h>
#define MAX_N 16
static char alphas[MAX_N] = {
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  'A', 'B', 'C', 'D', 'E', 'F'
};
/*
 * perm_gen(n, fp)
 * n : number of items (with 0 < n <= MAX_N)
 * fp: output file
 * returns: 0 = success (valid n), -1 = failure (invalid n)
 */
int
perm_gen(const int n, FILE *fp)
{
  register int i, j, k;
  int idxs[MAX_N];
  int vtds[MAX_N];
  if(n <= 0 || n > MAX_N) return -1;
  for(i=0; i<n; i++) idxs[i] = 0;
  do {
    for(i=0; i<n; i++) vtds[i] = 0;
    for(i=n-1; i>=0; i--) {
      for(j=k=0; k<=idxs[i]; j++)
        if(!vtds[j]) k++;
      fputc(alphas[--j], fp);
      vtds[j] = 1;
    }
    fputc('\n', fp);
    for(i=1; i<n && ++idxs[i]>i; i++) idxs[i] = 0;
  } while(i < n);
  return 0;
}
--//--
In generale, ti consiglierei un buon libro sugli algoritmi, tipo
l'ottimo R. Sedgewick, "Algorithms in C", Addison-Wesley 1990 (ho visto
anche la traduzione italiana in giro).
Comunque, se c'è qualcosa di poco chiaro nel codice contattami senza
problemi.
Ciao, julio di egidio
ju...@webzone.it

Grazie.
Vedi se ti puo' andare bene questo.
Usa la ricorsione ed e' estremamente semplice.
Occhio che il numero di permutazioni e' il fattoriale della dimensione dell'input.
** La stringa [s] poteva anche essere dichiarata globale ed evitare di inserirla nella
ricorsione, ma, secondo
le buone regole della programmazione, e' meglio evitare variabili globali
// permutazioni
#include <stdio.h>
#include <string.h>
static void perm(char *s,char *s1,int l);
static void scambia(char *s,int i);
static void out(char *s);
char SPAZI[82];
void main(void)
{
char s[256];
int l,i;
printf("Immettere la stringa da permutare -> ");
scanf("%s",s);
l = strlen(s);
SPAZI[0] = 32;
for(i=1;80 % (l+i);i++) SPAZI[i] = 32;
perm(s,s,l);
printf("\n");
}
void perm(char *s,char *s1,int l)
{
int i;
if(l > 1) {
   perm(s,s1+1,l-1);
   for(i=1;i<l;i++) {
     scambia(s1,i);
     perm(s,s1+1,l-1);
     out(s);
     scambia(s1,i);
     }
   }
}
void out(char *s)
{
printf("%s%s",s,SPAZI);
}
void scambia(char *s,int i)
{
char c = s[0];
s[0] = s[i];
s[i] = c;
}

 Grazie.
Avrei molto apprezzato un minimo di feedback per il codice... anche un
altro semplice grazie.
E' vero che mi ci sono divertito, ma comunque implementare un algoritmo
non-ricorsivo efficiente mi è costato una mezza giornata di lavoro.
A buon rendere, julio di egidio
ju...@webzone.it

 Occhio che il numero di permutazioni e' il fattoriale della dimensione dell'input.
Giusto a titolo di approfondimento (nel senso che non è in nessun modo
un attacco), ritieni che, a parte fini didattici, un algoritmo O(n!)
implementato ricorsivamente possa in qualche modo essere utilizzabile
nella vita reale?
Nel senso che se n = 10, n! = 3.628.000... non rischia di esplodere lo
stack? :)


...


stack? :)
Guarda che con le permutazioni la profondita' max dell stack e' n, non
n! (questo e' il numero toaale di call). Cmq resta sempre
ineffieciente. :-)
___
Fabio Forno
=============================================
Votate per it.cultura.fantascienza.startrek
=============================================
scia...@inorbit.com
http://rampage.ml.org/sector1/~sciasbat/
=============================================


So perfettamente che una routine ricorsiva e' "generalmente" meno efficiente di una
iterativa, ma si guadagna molto in semplicita' e manutenibilita'.
Per inciso, ho voluto confrontare le prestazioni delle due routine e, caso strano, la
routine ricorsiva si dimostra piu' veloce di quella iterativa :-)))
Spero che Julio non se la prenda :-)))
Ho anche effettuato la scrittura su disco di un byte alla volta per evitare che soluzioni
diverse potessero falsare il confronto.
Questo e' il codice che confronta le due soluzioni.
// permutazioni
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <dos.h>
static void stamparis(struct time *t);
static void subtime(struct time *prima,struct time *dopo);
static void perm(char *s,char *s1,int l);
static void scambia(char *s,int j);
static void out(char *s);
static char SPAZI[80];
static FILE *f;
static int  perm_gen(const int n, FILE *fp);
void main(void)
{
 char s[256];
 int l,i;
 struct time t1,t2;
 printf("\n\nImmettere la stringa da permutare -> ");
 scanf("%s",s);
 l = strlen(s);
 SPAZI[0] = 32;
 for(i=1;80 % (l+i);i++) SPAZI[i] = 32;
 f = fopen("TEST1","w");
 printf("\n\n*********** Ricorsiva *************\n");
 gettime(&t1);
 perm(s,s,l);
 gettime(&t2);
 subtime(&t1,&t2);
 stamparis(&t2);
 fclose(f);
 f = fopen("TEST2","w");
 i = strlen(s);
 printf("\n\n*********** Iterativa *************\n");
 gettime(&t1);
 perm_gen(i,f);
 gettime(&t2);
 subtime(&t1,&t2);
 stamparis(&t2);
 fclose(f);
}
void perm(char *s,char *s1,int l)
{
 int i;
 if(l > 1) {
   perm(s,s1+1,l-1);
   for(i=1;i<l;i++) {
     scambia(s1,i);
     perm(s,s1+1,l-1);
     out(s);
     scambia(s1,i);
     }
   }
}
void out(char *s)
{
 int i;
 for(;*s;++s)
   fputc(*s,f);
 fputc('\n',f);
}
void scambia(char *s,int j)
{
 char c;
 c = s[0];
 s[0] = s[j];
 s[j] = c;
}
/////////////////////////////////////////////////////////////





  return 0;
}
///////////////////////////////////////////////////////////
static void stamparis(struct time *t)
{
   printf("Tempo di elaborazione -> %02d:%02d:%02d:%02d\n",
     (int)t->ti_hour,(int)t->ti_min,(int)t->ti_sec,(int)t->ti_hund);
}
static void subtime(struct time *prima,struct time *dopo)
{
 dopo->ti_hund -= prima->ti_hund;
 dopo->ti_sec  -= prima->ti_sec;
 dopo->ti_min  -= prima->ti_min;
 dopo->ti_hour -= prima->ti_hour;
 if(dopo->ti_hund > 99) { dopo->ti_hund += 100; dopo->ti_sec--; }
 if(dopo->ti_sec  > 59) { dopo->ti_sec  += 60;  dopo->ti_min--; }
 if(dopo->ti_min  > 59) { dopo->ti_min  += 60;  dopo->ti_hour--; }
 if(dopo->ti_hour > 23)   dopo->ti_hour += 24;
}


Che fai, mi provochi? :-)))
Sei sicuro che la tua sia piu' veloce? Da un test che ho fatto non mi sembra.
E considera che la mia non e' affatto ottimizzata.
Tutti quei parametri passati a una funzione ricorsiva!!! E' quasi un suicidio :-)
L'avevo messa cosi' solo per dargli una forma un po' accademica.
Cmq ho voluto provare ad usare un po' di variabili globali, a portare la funzione di swap
all'interno e, per prevenire imprevisti dovuti alla cache del disco, ho disabilitato la
scrittura su file. Cosi' si esegue solo calcolo puro (a parte lo scheduling di win95).
Con una dimensioni in input di undici caratteri (39.916.800 permutazioni), la mia se l'e'
cavata con 8~9 secondi, mentre la tua ha viaggiato intorno ai 29~30 secondi. (Tra l'altro,
ti ho anche migliorato la tua togliendo quei antipatici unsigned char per gli indici
promuovendoli a unsigned, cosi' da eliminare un po' di inevitabili conversioni).
P.S. Non ti conviene utilizzare la keyword register. Ormai ogni buon compilatore se la sa
cavare egregiamente nell'assegnare alcune variabili ai registri.
Questo e' il codice che usa variabili globali. Era sicuramente piu' elegante quello
originario.:-)
Ciao
Nazzareno
------------------------------------------------------------
static int Init,Len;
static char _S[256];
// ... Init=0; Len = strlen(_S);
void perm()
{
 int i;
 char swap;
 if(Len > 1) {
   if(--Len > 1) {
     ++Init;
     perm();
     --Init;
     }
   ++Len;
   for(i=1;i<Len;i++) {
     swap = _S[i+Init];  _S[i+Init] = _S[Init];  _S[Init] = swap;
     if(--Len > 1) {
       ++Init;
       perm();
       --Init;
       }
     ++Len;
//   out();
     swap = _S[i+Init];  _S[i+Init] = _S[Init];  _S[Init] = swap;
     }
   }
}