Anagrammi

di

Generare tutti gli anagrammi di una parola.
Data una certa sequenza di caratteri generare tutte le possibili sequenze di caratteri.

Sia amor la parola da anagrammare.

Ciascuno dei caratteri presenti deve occupare la prima posizione e rimangono gli altri 3 caratteri da anagrammare

  • a[mor]
  • m[aor], scambia a e m
    • riscambia a e m: amor
  • o[mar], scambia a e o
    • riscambia a e o: amor
  • r[moa], scambia a e r
    • riscambia a e r: amor

Ogni volta in parentesi quadre rimane una sequenza da anagrammare: continua in modo ricorsivo.

amora[mor]am[or]amo[r]amor
amr[o]amro
ao[mr]aom[r]aomr
aor[m]aorm
ar[mo]arm[o]armo
aro[m]arom
m[aor]ma[or]mao[r]maor
mar[o]maro
mo[ar]moa[r]moar
mor[a]mora
mr[oa]mro[a]mroa
mra[o]mrao
o[mar]om[ar]oma[r]omar
omr[a]omra
oa[mr]oam[r]oamr
oar[m]oarm
or[ma]orm[a]orma
ora[m]oram
r[moa]rm[oa]rmo[a]rmoa
rma[a]rmao
ro[ma]rom[a]roma
roa[m]roam
ra[mo]ram[o]ramo
rao[m]raom

Quando la sequenza nelle parentesi quadre contiene un solo carattere è già anagrammata.

In ordine alfabetico

L’algoritmo precedente produce tutti gli anagrammi ma non sono in ordine alfabetico.

Il nuovo algoritmo

  1. La sequenza iniziale è ordinata: amor
    • Continua con la ricorsione
  2. La 2° lettera, m, si sposta in 1° posizione e la a in 2°: m[aor]
    • Continua con la ricorsione
  3. La 3° lettera, o, si sposta in 1° posizione e la a in 2°: o[amr]
    • Continua con la ricorsione
  4. La 4° lettera, r, si sposta in 1° posizione e la a in 2°: r[amo]

Con questa accortezza la sottosequenza è sempre ordinata

amora[mor]am[or]amo[r]amor
amr[o]amro
ao[mr]aom[r]aomr
aor[m]aorm
ar[mo]arm[o]armo
aro[m]arom
m[aor]ma[or]mao[r]maor
mar[o]maro
mo[ar]moa[r]moar
mor[a]mora
mr[ao]mra[o]mrao
mro[a]mroa
o[amr]oa[mr]oam[r]oamr
oar[m]oarm
om[ar]oma[r]omar
omr[a]omra
or[am]ora[m]oram
orm[a]orma
r[amo]ra[mo]ram[o]ramo
rao[m]raom
rm[ao]rma[o]rmao
rmo[a]rmoa
ro[am]roa[m]roam
rom[a]roma
Python