Newsgroup: it.comp.aiuto
Titolo: Permutazioni di una stringa!

Salve.
Qualcuno sa suggerirmi un algoritmo x generare tutte le n! permutazioni in
una sequenza di n elementi? Non mi interessa la  codifica in un linguaggio
particolare, ma soltanto l'algoritmo, anche in linguaggio naturale!
Grazie.
		Gino
--
Posted from 
ro...@relay.olivettiricerca.it
 [193.76.87.5]
via Mailgate.ORG Server - 
http://www.mailgate.org

		Gino
Mi rassegno, non c'e` NG piu` adatto (possibile non esista it.comp.algoritmi o
it.comp.programmare.algoritmi), forse it.scienza.informatica, ma mi sono sempre
sembrati un po' scontrosi ;).
Se ti serve un algoritmo per trovare anagrammi di senso compiuto, questo e`
diverso e -- anche se puo` sembrare assurdo -- piu` "facile".
Se vuoi (come chiedi) tutte le permutazioni invece puoi affidarti alla
ricorsione suddividendo il problema in problemi piu` piccoli:
Anagrammi(stringa)
{
	for i=1 to len(stringa)
		anagramma(n-esimo) = stringa[i] & Anagrammi("stringa 
												meno carattere i-esimo");
	/* con & concatenatore di stringa e = assegnazione tra stringhe */
	next i
}
questo in "code" molto "pseudo-" :)
_mirko_ (oh, se ci guadagni dei miliardi ricordati di me!)
_mirko_
PS: Se volete contattarmi in privato, NON ciucciatevi il calzino :).

		Gino
C'e` tutta una letteratura sull'argomento.  Se ti interessa
approfondirlo, potresti cercare di rintracciare questo articolo:
R. Sedgewick, "Permutation Generation Methods", ACM Computing
Surveys, Vol. 9, N. 2, June 1977 (non credo che ci siano state
novita` sconvolgenti, da allora).
Se invece ti basta risolvere il problema :) puoi usare questo
programmino in Turbo Pascal come modello. Ho utilizzato il classico
algoritmo di Johnson-Trotter, nella versione che appare in "An
Introduction to Computational Combinatorics" di Page e Wilson,
con qualche ritocco, e correggendo un errore di stampa che mandava 
il programma in loop.
L'algoritmo e` molto efficiente, ma genera le permutazioni in un
ordine piuttosto strano.  Se le permutazioni ti servissero in ordine
lessicografico, bisognerebbe utilizzare un altro algoritmo. 
ATTENZIONE  Se devi usare l'algoritmo in un programma C, usa un array
con un elemento in piu` e lavora solo sulla parte con gli indici che
vanno da 1 a N, ignorando il primo elemento.  L'algoritmo, in questa
versione, si basa sul fatto che gli indici partono da 1 e non da 0.
-- 
  Gianfranco Boggio
PROGRAM  permutations ;
CONST
    N = 5 ;
TYPE
    Array_Variable = ARRAY [1..N] OF Integer ;
VAR
    perm_e: Array_Variable  ;
    perm_d: Array_Variable  ;
FUNCTION  perm (VAR a: Array_Variable) : Boolean ;
VAR
    i, k, q, v, x: Integer ;
BEGIN
    IF  a[1] = 0  THEN
      BEGIN
        a[1] := 1 ;
        FOR  i := 2  TO  N  DO
          BEGIN
            a[i] := i ;
            perm_d[i] := i ;
            perm_e[i] := -1 ;
          END ;
        perm := True ;
        Exit ;
      END ;
    v := 0 ;
    FOR  k := N  DOWNTO 2  DO 
      BEGIN
        q := perm_d[k] + perm_e[k] ;
        perm_d[k] := q ;
        IF q = k  THEN
            perm_e[k] := -1 
        ELSE 
            IF  q = 0  THEN
              BEGIN
                perm_e[k] := 1 ;
                v := v + 1 ;
              END
            ELSE
              BEGIN 
                q := q + v ;
                x := a[q] ; a[q] := a[q+1]; a[q+1] := x ;
                perm := True ;
                Exit ;
              END ;
      END ;
    a[1] := 0   ;
    perm := False ;
END ;
VAR
    a:  Array_Variable ;
    i:  Integer ;   
    n_perm: LongInt;
BEGIN
    n_perm := 0 ;
    a[1] := 0 ;
    WHILE  perm (a) DO
      BEGIN
        n_perm := n_perm + 1 ;
        FOR  i := 1 TO N DO
            Write (a[i], ' ') ;
        Writeln ;
      END ;
    Writeln  ('N = ', N,  '   perm = ', n_perm) ;
END.