[C] creazione file testo con tutte le combinazioni possibili di alfanumeric

[I.G.C.]

Salve ragazzi, complimenti come al solito per il servizio che offrite. Avrei bisogno di qualche dritta per scrivere in C un programma che crei un file di testo contenente tutte le possibili combinazioni delle 26 lettere con i 10 numerali,nel file di testo devono essere scritte le combinazioni che vanno da 1 a 16 caratteri. Non importa quanto ci metta il pc a generarlo. Per capirci la tecnica di creazione dovrebbe essere simile a quella applicata per fare un attacco brute-force. Grazie mille in anticipo per l'aiuto.

Gabrio

[MdE2005]

Originariamente inviato da I.G.C.
Salve ragazzi, complimenti come al solito per il servizio che offrite. Avrei bisogno di qualche dritta per scrivere in C un programma che crei un file di testo contenente tutte le possibili combinazioni delle 26 lettere con i 10 numerali,nel file di testo devono essere scritte le combinazioni che vanno da 1 a 16 caratteri. Non importa quanto ci metta il pc a generarlo. Per capirci la tecnica di creazione dovrebbe essere simile a quella applicata per fare un attacco brute-force. Grazie mille in anticipo per l'aiuto.

Gabrio

Forse non ti rendi conto di ciò che chiedi , in ogni caso si tratta di disposizioni di n elementi di classe n con ripetizione la cui definizione è la seguente: [I"Dati n elementi distinti e un numero k<=n si dicono disposizioni con ripetizione di questi n elementi, presi a k a k (o di classe k), D'(n,k), tutti i gruppi che si possono formare con gli elementi dati, in modo che: 1. ogni gruppo contenga k elementi non necessariamente distinti 2. ogni elemento possa trovarsi ripetuto nel gruppo fino a k volte 3. due gruppi qualunque differiscano fra loro per qualche elemento oppure per l'ordine in cui gli elementi sono disposti".

La formula è la seguente: D'(n,k) = n^k; nel tuo caso n = 36 e k va da 1 a 16, quindi per calcolare quante combinazioni ricavi guarda questo pseudocodice:

for (k=1; k<=17;k++){
num = 36^k
tot = tot + num	
}

Ecco il risultato:

8.18605142737344E+24


Visto che ti interessa l’argomento:

• Reingold et al., "Combinatorial Algorithms " (http://www.amazon.com/Combinatorial-.../dp/013152447X), Prentice Hall, 1977

• Nijenhius & Wilf, "Combinatorial Algorithms , 2nd ed." (http://www.math.upenn.edu/~wilf/webs...AlgDownld.html), Academic Press, 1978

• Kreher & Stinson, "Combinatorial Algorithms " (http://www.math.mtu.edu/~kreher/cages.html), CRC Press, 1998

• T. Hu & M. Shing, "Combinatorial Algorithms " (http://books.google.it/books?id=BF5_...age&q=&f=false), Dover, 2002

• Frank Ruskey, "Combinatorial Generation " (http://www.ioprogrammo.it/bookshelf_...-t17050.0.html), 2003

• Joerg Arndt, "Matters Computational " (http://www.ioprogrammo.it/bookshelf_...-t15745.0.html), di prossima pubblicazione


Spero di essere stato chiaro


Ciao

[Ippo343]

Diciamo, per amore di discussione, che il tuo programma riesca a calcolarne 10 miliardi al secondo. Sfruttando molto i multicore e con grande efficienza, riesci in qualche modo a portarlo a questo livello:

8.18605142737344E+24 combinazioni = 818605142737344 secondi = 13643419045622 minuti = 227390317427 ore = 9474596559 giorni = 25957798,8 anni.

Circa 26 milioni di anni di computazione ininterrotta. Mi sa di no

[I.G.C.]

Mmmmh mi aspettavo venisse un numero alto, ma la seconda risposta mi ha chiarito abbastanza le idee xD Che poi non sarebbero 36, ma 62, perchè andrebbero considerate anche le maiuscole xD vabbè... supponendo che si voglia fare una cosa più in piccolo... tipo facendo disposizioni dei primi 5 numeri, quindi {0,1,2,3,4} idi classe 3, con ripetizione. Non risolvo il problema che mi ero posto, ma capirete bene che mi è rimasta la curiosità di capire come strutturare un programma del genere...

[MdE2005]

Originariamente inviato da I.G.C.
Mmmmh mi aspettavo venisse un numero alto, ma la seconda risposta mi ha chiarito abbastanza le idee xD Che poi non sarebbero 36, ma 62, perchè andrebbero considerate anche le maiuscole xD vabbè... supponendo che si voglia fare una cosa più in piccolo... tipo facendo disposizioni dei primi 5 numeri, quindi {0,1,2,3,4} idi classe 3, con ripetizione. Non risolvo il problema che mi ero posto, ma capirete bene che mi è rimasta la curiosità di capire come strutturare un programma del genere...

In questo caso la situazione si semplifica ulteriormente e la risoluzione *può* prescindere dalla combinatorica: fai un ciclo da 0 a 999 (visto che k = 3), accettando solo quei numeri che non contengono 5,6,7,8,9, semplicemente con un costrutto If esclusivo. Ovviamente con questo metodo devi formattare alla fine le cifre, ovvero 10 corrisponderà a 010, 89 a 089, 8 a 008.
Come ci suggerisce la matematica, in questo caso le tue combinazioni saranno 5^3 = 125 .

Se invece vuoi un approccio iterativo/ricorsivo, la bibliografia che ti ho postato è più che sufficiente, e in più potresti fare una ricerca nel forum, visto che l'argomento è già stato trattato.


Ciao