Newsgroup: it.comp.lang.pascal
Titolo: ! Algoritmo x Anagrammi

Qualcuno ha qualche idea di come si potrebbe fare un algoritmo per calcolare
gli anagrammi di un nome di n lettere?
Io l'unico metodo che ho in mente e' quello di tanti cicli nidificati quanti
sono le lettere della parola, con una guardia molto forte che esclude che la
stessa componente sia ripetuta piu' volte, saltando il ciclo in cui appare
piu' volte, riducendo cosi' il numero delle stampe da n^n a n!, chedovrebbe
essere il numero di anagrammi per una parola di n lettere.
Ora, funziona, ma il problema e' che vorrei fare un algoritmo, un programma
piu' generale, cioe' che funzioni con nomi di qualsiasi lunghezza, e non
prestabilita.
Ho pensato anche alla ricorsione, ma non mi viene in mente come sfruttarla.
Si riesca iterativamente?
Vi ringrazio in anticipo,
Alex

gli anagrammi di un nome di n lettere?
Ti propongo una mia soluziona che funziona con una parola di lunghezza
qualunque.
Non e' che sia un mostro di efficenza. L'idea e' la stessa che hai
avuto tu, generare delle permutazioni con ripetizione e poi eliminare
quelle che non vanno bene (questo viene fatto dalla funzione BUONA).
Partendo dalla permutazione iniziale 1234...L  tramite la procedura
PERM_SUCC vinene generata la permutazione successiva.
Questa procedura e' a dir poco eccezionale:-)  In pratica funziona
come qunado si fa a mano la somma con riporto.
program   permutazioni;
const     max=10;
var       l,i:byte;
          v:array[1..max] of byte;
          s:String;
function  buona:boolean;
var       b:array[1..max] of boolean;
          j:byte;
begin
          for j:=1 to l do
              b[j]:=false;
          j:=1;
          while (not b[v[j]]) and (j<=l) do begin
              b[v[j]]:=true;
              inc(j)
          end;
          buona:= (j>l)
end;
procedure perm_succ;
var       i:byte;
begin
          i:=l;
          inc(v[i]);
          while (v[i]>l) and (i>1) do begin
             v[i]:=1;
             dec(i);
             inc(v[i])
          end
end;
begin
        readln(s);
        writeln;
        l:=length(s);
        for i:=1 to l do
            v[i]:=i;
        repeat
            if buona then begin
               for i:=1 to l do
                   write(s[v[i]]);
               writeln
            end;
            perm_succ
        until v[1]>l
end.
Sucuramente questo e' l'algoritmo che ha complessita' maggiore di
tutti gli ipotizzabili ma e' abbastanza semplice ed intuitivo.
Qualcuno che ha studiato le permutazioni protra' farne sicuramente uno
con complessità inferiore.
Ciao,  Fabio
fabi...@rocketmail.com

Ho pensato anche alla ricorsione, ma non mi viene in mente come sfruttarla.
Ecco la soluzione ricorsiva :
var s         : string;
    stack     : string;
    stack_idx : longint;
function estratto(t : string; i : integer) : string;
begin
  delete(t, i, 1);
  estratto := t;
end;
procedure scrivi_anagrammi(t : string);
var i : integer;
begin
  if length(t) = 0 then
  begin
    inc(stack_idx);
    writeln(stack_idx:5, ') ' + stack);
  end
  else
    for i := 1 to length(t) do
    begin
      stack := stack + t[i];
      scrivi_anagrammi(estratto(t, i));
      stack := copy(stack, 1, length(stack)-1);
    end;
end;
begin
  stack := '';
  stack_idx := 0;
  write('parola : '); readln(s);
  scrivi_anagrammi(s);
end.
Io l'ho pensata cosi' :
Scrivere gli algoritmi di ROMA equivale a scrivere di volta in volta
R antecedente tutti gli anagrammi di OMA
O antecedente tutti gli anagrammi di RMA
M antecedente tutti gli anagrammi di ROA
A antecedente tutti gli anagrammi di ROM
e cosi' via per ciascuno degli estratti cioe', per esempio per 'OMA'
O antecedente tutti gli anagrammi di MA
M antecedente tutti gli anagrammi di OA
A antecedente tutti gli anagrammi di OM
etc.... etc...
Andrea, mica uno qualunque...
--------------------------------------------------
"Ho cambiato signature, si vede ?"
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

e cosi' via per ciascuno degli estratti cioe', per esempio per 'OMA'
Complimenti.
Fabio
fabi...@rocketmail.com

Complimenti.
;) 


A me all'epoca semnbro' molto bello...
Si, e' vero.
A me invece piaceva il gioco "PAROLIAMO" che facevano in TV dove si estraeva una
sequenza casuale di vocali e consonanti tipo "CNITAAMNET" e il computer scandiva
il dizionario alla ricerca di tutte quelle parole, di lunghezza variabile, che
era possibile creare con la sequenza.
In realta' la tecnica e' molto semplice :
(1) introduci la sequenza ;
(2) crea una chiave madre di 26 byte in cui, in corrispondenza dell'indice di
ogni lettera della sequenza, viene memorizzato il numero di volte che essa
compare nella stessa ;
(3) leggi una parola dal dizionario finche' non e' vuoto ; 
(4) come (2) crea una chiave figlia per la parola del dizionario ;
(5) controlla che i valori della chiave madre siano tutti >= di quelli della
chiave figlia ; 
    se SI allora accetta la parola ; 
    se NO allora salta al (3) ;
Skyscraper
---------------------------
andrea_...@bigfoot.com


anagrammi "esistenti" di una parola qualsiasi.
Quali sono le riviste che parlano del pascal (non delphi) ?
Davide
davi...@usa.net
ICQ: 20331544