PDA

Visualizza la versione completa : [C-C++] Enumerare le possibili parole di k lettere da un alfabeto di n


Ol3iconfini
10-04-2008, 18:01
Ho il seguente "problemone": dato un alfabeto di n lettere (diciamo n=4) voglio enumerare, ovvero creare un contenitore al cui interno ci siano tutte le possibili combinazioni di parole di k lettere (diciamo k=2)...
Supponiamo che l'alfabeto sia composto da queste lettere: a,b,c,d.
Allora le possibili parole di due lettere sono:

ab
ac
ad
bc
bd
cd

Ovviamente non sono parole ammissibili quelle in cui una lettera è ripetuta più volte (cioé, aa non è ammissibile), e sono parole uguali quelle contenenti le stesse lettere in posizioni diverse (cioè ab=ba, per cui la creo solo una volta).

Come posso procedere per l'implementazione, considerando che dovrò scalare su numeri piuttosto grandi?:master:
Mi conviene creare un array di stringhe, o un array di array?
Altrimenti?

Grazie per i suggerimenti!

XWolverineX
10-04-2008, 18:25
Potresti leggere questo (http://forum.html.it/forum/showthread.php?s=&threadid=1078791&perpage=15&highlight=permutazioni&pagenumber=1)

Ol3iconfini
10-04-2008, 18:36
Ho letto tutti i thread che contengono la parola chiave combinazioni... In pratica si risolvevano problemi di permutazioni... Qui il problema è differente.
Il problema qui è che devo creare tutte le combinazioni di k lettere da un alfabeto di n lettere, con n>k...

Come posso procedere?

menphisx
11-04-2008, 11:13
Stampare tutte le combinazioni di un alfabeto di 4 lettere equivale a contare in base 4.
Esempio:


00
01
02
03
10
11
12
13
20
21
22
23
30
31
32
33


se consideriamo le singole cifre di un numero, come posizione della lettera nell'alfabeto, ed effettivamente lo sono, basta sostituire le varie cifre con la lettera corrispondente.
Esempio:


00 --> aa
01 --> ab
02 --> ac
03 --> ad
10 --> ba
11 --> bb
12 --> bc
13 --> bd
20 --> ca
21 --> cb
22 --> cc
23 --> cd
30 --> da
31 --> db
32 --> dc
33 --> dd


:ciauz:

Loading