Newsgroup: it.comp.lang.visual-basic
Titolo: Richiesta algoritmo

Avrei bisogno dell'algoritmo che data una serie di numeri, mi
snoccioli tutte le combinazioni in cui possono essere messi tali
numeri;
Faccio un esempio per spiegarmi meglio:
La serie di numeri supponiamo sia di 3 numeri:
1,2,3
Il programma dovrebbe darmi come risultato:
123
132
213
231
321
312
Ovviamente dovrebbe essere possibile inserire il numero di cifre (da 2
a n)
Se non chiedo troppo non sarebbe male che ci fosse la possibilità di
escludere o meno i duplicati
Per esempio dati 3 numeri su 2 posizioni
1,2,3
dovrebbe dare come risultato:
11
12
13
21
22
23
31
32
33
I meno giovani risorderanno che era uscito qualcosa di questo genere
su una rubrica di MC-Microcomputer ai bei tempi quando c'erano le
rubriche "Algoritmi" e "Intelligiochi" che fornivano spunti
interessanti per problemi pratici di programmazione.
Mi pare che quello che serva a me si chiamino "Permutazioni" se non
ricordo male (parliamo di circa 10/15 anni addietro)
Ringrazio anticipatamente chiunque possa e voglia aiutarmi.
Inviare anche risposte e-mail a 
am...@hotmail.com
Alberto Muzio.

guarda che non è difficile
iniziamo subito col dire una cosa:
se il 'range' di cifre ad esempio è dieci, e il numero di cifre da mettere è
5 il totale delle combinazioni sarà 10^5 (dieci elevato alla potenza 5 ->
10*10*10*10*10 -> 100000)
poi ti basta costruire tanti array quante sono le cifre (o caratteri)
disponibili e 'sfasarle' di un byte ognuna
non so se mi spiego. ad esempio abbiamo "a", "b", "c", "d" come caratteri
disponibili. dobbiamo creare 4 array
(ne puoi benissimo fare a meno, ma per rendere la spiegazione molto più
semplice adesso facciamo così)
array1 = {"a", "b", "c", "d"};
array2 = {"b", "c", "d", "a"}; ecc... (lo possiamo anche fare da codice)
poi dommiano lavorare in base della lunghezza dell'array, cioè se la
password da scoprire sarà di soli numeri, e quindi iol range sarà da 0 a 9,
cioè 10 elementi, useremo un numero in base 10 per andare a scovare tutte le
possibili combinazioni
quindi con quattro cifre decimali dovremo usare un ciclo for che incrementi
un numero base 10 da 0 a 9999
dobbiamo fare una funzione che riempia gli spazi vuoti con zeri, cioè se
abbiamo 72 ci deve restituire 0072, ma non è difficile da fare
poi ci dobbiamo fare una funzione che dalla stringa che ci ha ritornato la
funzione precedente ci ritorni un'array, con tanti elementi quanti sono i
caratteri della stringa (quindi in questo caso 4, e ci dovrà tornare {"0",
"0", "7", "2"}...)
adesso, memorizziamo tutte le combinazioni in un array, tra,mite un ciclo
for
supponiamo che i 4 elementi che ci ha passato la funzione siano f[0], f[1],
f[2], f[3], scriveremo
combinazione[contatore] = f[0]+f[1]+f[2]+f[3]
o ancora meglio:
for (a=0; a<=f.length; a++) combinazione[contatore] += f[a];
ti ho dato un'idea di come fare il programma
adesso il codice telo scrivi da solo! ;-)
altrimenti su NewOrder, Astalavista, HDC è pieno di questo toolz, basta
cercare che ne so.. "brute force password hacking"...   ;-))
ciao
PhoBoS

 wrote in message
5A12OWHMrifbTZ...@4ax.com...


numeri;
potresti implementare l'algoritmo in modo ricorsivo, usando il concetto di
insieme:
le permutazioni di [a, b, c] sono ottenibili nel seguente modo:
    a più le permutazioni di [b, c]
                   ovvero
                        b più le permutazioni di [c] = bc
                        c più le permutazioni di [b] = cb
    più b più le permutazioni di [a, c]
                    ....
    più c più le permutazioni di [a, b]
                    ....
ossia la tua funzione riceve insieme su cui effettuare le permutazioni.
Compie una iterazione sull'insieme, e per ogni elemento richiama sè stessa
passando come parametro l'insieme di partenza privato dell'elemento. E'
necessario anche passare un "prefisso" con la parte di permutazioni già
sviluppata da precedenti istanze della funzione.
Il numero di permutazioni è n!, dove n è il numero di elementi dell'insieme.
L'uscita dalla ricorsione è quando l'insieme contiene un solo elemento.
Puoi implementare gli insiemi usando una variabile byte e gli operatori
logici bit a bit (ogni bit è un elemento, 0 = assente, 1=presente), o le
stringhe (ogni carattere è un elemento), oppure le collezioni.
Ti faccio un esempio usando le stringhe
Public Sub Permuta(ByVal I As String, Optional ByVal prefix As String = "")
 Dim ct As Integer
    If Len(I) = 1 Then
        Debug.Print prefix & I
     Else
        For ct = 1 To Len(I)
            Permuta Left$(I, ct - 1) & Mid$(I, ct + 1), prefix & Mid$(I, ct,
1)
        Next
   End If
End Sub
prova a chiamare Permuta "ABCD"
per le combinazioni di n elementi a k a k... segui l'esempio, e procedi, un
altro post da mezz'ora e il capo mi sopprime!
Ciao e buon lavoro
Sig
_________________________________________________________
Luca Sigfrido Percich              
sigf...@tiscalinet.it
_________________________________________________________
non avere stile è il mio stile

altro post da mezz'ora e il capo mi sopprime!
sbagliavo, č bastato un minuto (a stomaco pieno si ragiona meglio)
Public Sub Combina(ByVal I As String, ByVal MaxElements As Integer)
 Dim ct As Integer
    If Len(I) = MaxElements Then
        Permuta I
     Else
        For ct = 1 To Len(I)
            Combina Left$(I, ct - 1) & Mid$(I, ct + 1), MaxElements
        Next
   End If
End Sub
prova Call Combina("ABCD", 2)
la SUb Permuta č definita nel post precedente...
In pratica la funzione ottiene tutti i possibili sottoinsiemi sottraento un
elemento per volta e richiamandosi ricorsivamente; quando l'insieme passato
ha la cardinalitą voluta, allora ne effettua le permutazioni (vedi post
prec.).
Ciao
Sig

Ripeto il messaggio che ho inviato recentemente, in risposta ad una domanda simile.
Sul Sito Comune (e ora anche su 
http://members.xoom.it/flanguasco/
) ho messo un
progettino con le routines per calcolare disposizioni e combinazioni (e quindi
anche permutazioni) semplici di N oggetti della classe K, con N e K variabili.
Spero che possa essere utile.
Franco


 > numeri;


Luca:
  complimenti: raramente ho visto risolvere un problema in maniera
cosi' semplice ed elegante.
Se sei d'accordo vorrei includere il tuo codice nel mio progetto
CalcComb (come riferimento e citando, ovviamente, la fonte) anche
se le mie routines (che mi sono costate parecchie ore di contemplazione)
dovessero, al confronto, sfigurare.
Ancora bravo e ciao.
Franco


 Ciao,

 wrote in message
8l5g5d$joe$1...@lacerta.tiscalinet.it...


 tempo a morire...
infatti il b.f.pwd hacking non č il sistema preferito dagli hackers... ;-)
va usato solo in casi drastici, e in quei casi si usano dizionari di
password
--
ciao
- Xaero -
"Quando ero piccolo i miei genitori mi
 volevano cosě bene che nella culla mi
 misero un orsacchiotto vero"

a qualcuno sapere cosa calcola.   :))
Ora so che puoi capirmi e perdonare i miei errori: č gią difficile
esprimersi in italiano, figuriamoci scrivere algoritmi. :o)
Se ho ben capito la richiesta, cerco di risponderti: sempre dal redivivo
testo di algebra, scopro che la mia funzione avrebbe dovuto calcolare le
Disposizioni semplici. Avrebbe dovuto, perché in effetti produce duplicati.
Ecco quindi l'implementazione corretta della funzione:
Public Sub Disponi(ByVal I As String, ByVal MaxElements As Integer, Optional
ByVal prefix As String = "")
 Dim ct As Integer
 For ct = 1 To Len(I) - MaxElements + 1
    If MaxElements = 1 Then
        Permuta prefix & Mid$(I, ct, 1)
     Else
        Disponi Mid$(I, ct + 1), MaxElements - 1, prefix & Mid$(I, ct, 1)
    End If
 Next
End Sub
L'implementazione č la stessa di Combina, ma invece di restituire
direttamente l'allineamento, ne effettua la permutazione. Credo che quanto
originariamente richiesto dall'uomo di Gotham City fosse proprio questo,
oltre alle Permutazioni, ossia le Disposizioni.
Doppio casino, quindi: confuso le combinazioni con le disposizioni. Cannato
l'algoritmo delle disposizioni. Mi scuso ancora per l'errore, dovuto ad una
mia imperdonabile leggerezza, se pur spiegabile da uno stato di torpore
post-prandiale, ma imputabile principalmente alle mie eterne carenze in
matematica. Coglierei quindi l'occasione per salutare tutte le mie ex prof.
di matematica, le quali, unite nel considerarmi l'anello mancante tra
scimmia e uomo, non hanno mai smesso di cazziarmi a morte. La storia sembra
dar loro ragione. :o)
PS: non so se sia meglio scrivere codice dopo pranzo o alle due e passa di
notte... non vorrei che l'indomani rivelasse nuovi, tragici errori... ma so
di poter contare su degli ottimi beta-tester, per cui vado a nanna
tranquillo. Abbiate pietą! ;o)
Auguro buona notte a tutto il NG!
Sig
_________________________________________________________
Luca Sigfrido Percich              
sigf...@tiscalinet.it
_________________________________________________________
non avere stile č il mio stile

CalcComb (come riferimento e citando, ovviamente, la fonte)
Grazie mille, mi fai troppo onore. Usa tranquillamente il codice, sta' solo
attento a inserire le sub giuste: guarda il cazziatone che mi sono beccato
da ramarro e il mio Errata Corrige... :o)
Ciao e grazie
Sig

...

che consentano al dilettante di fare un pò di pratica ?
Se non ce l'hai, ti consiglio il bellissimo "Algoritmi + strutture dati =
programmi" di N. Wirth, lo trovi in edizione italiana e inglese, come
preferisci. E' basato su Pascal (che Wirth ha tra l'altro inventato, se non
ricordo male), comunque va benissimo anche per chi non conosce questo
linguaggio o ne ha avuta solo una infarinatura a scuola.
La ricorsione, come tutte le tecniche di programmazione, si impara
tranquillamente con un po' di pratica! Puoi inizialmente applicarla a casi
semplici, che addirittura non richiederebbero una soluzione ricorsiva: il
caso più semplice è il fattoriale di un numero
function Fattoriale(N)
    if N = 1
        Fattoriale = 1
      else
        Fattoriale = N * Fattoriale (N - 1)
    end if
end function
che potresti risolvere benissimo con un ciclo for o un do..loop, in questo
caso l'uso della ricorsione è solo più elegante, ma più pesante dal pdv
delle risorse impiegate.
Pensa infatti che tutte le volte che chiami una sub/function il programma
deve copiare sullo stack registri e parametri, e creare spazio per le
variabili globali. Questo significa altresì che, dato che la ricorsione
implica la creazione di istanze di funzioni in memoria con i loro ambienti
(var locali e parametri), di fatto si ha la costruzione di una struttura
dati dinamica. Ci sono anche linguaggi, come Prolog, che ti consentono di
definire strutture dati ricorsive, strutture che puoi comunque implementare
in altri linguaggi (C, Pascal) con i puntatori, e in VB con gli oggetti.
Ogni volta che chiami una sub da se' stessa, "congeli" lo stato della sub
chiamante sullo stack. Puoi pensare di applicare questa tecnica al gioco
degli scacchi: anche mentalmente "provi le mosse", ovvero parti da una
situazione, ipotizzi che ci siano, diciamo 3 mosse possibili. Provi la
prima. A questo punto pero', sei in una nuova situazione, quindi hai ancora,
diciamo, quattro mosse possibili. Provi la prima. A un certo punto devi
tornare indietro, quando scopri che la mossa era sbagliata... tutte le mosse
possibili sono disposte su un albero, ogni mossa genera un nuovo stato e
quindi nuove possibili mosse. Dopo che hai provato la prima, e percorso
tutte le sue possibili conseguenze, provi la seconda. E così via.


      nemmeno in grado di concepire ).
La soluzione a cui mi riferivo riguardava l'implementazione degli insiemi
per mezzo dell'aritmetica bit-a-bit. considera l'insieme [A, B, C, D]. Crei
una corrispondenza tra ogni elemento è una posizione in una nibble (sequenza
di 4 bit):
A B C D
0 1 2 3
Ad A corrisponde il bit 0, quindi 2^0 = 1;
a B corrsiponde il bit 1, quindi 2^1 = 2;
C = 2^2 = 4 etc.
Const A = 2^0    ' 1, 0001
Const B = 2^1    ' 2, 0010
Const C = 2^2    ' 4, 0100
Const D = 2^3    ' 8, 1000
Dim S as byte ' S è la variabile che rappresenta l'insieme.
S = 0    ' L'insieme è vuoto
S = S or A    ' L'insieme contiene A
S = S or B or C or D    ' L'insieme è "Pieno"
S = S and not C    ' L'insieme è [A,B,D], ho escluso C.
Ogni bit della nibble si comporta come una variabile boolean, per cui, detta
B tale variabile, valgono le regole:
B and True = B    ' Lascio invariato B
B or False = B    ' Lascio invariato B
B or True = True    ' Setto il bit a 1
B and False = False    ' Setto il bit a 0
Lo svantaggio di questo approccio è che, essendo la rappresentazione degli
elementi posizionale, non mi permette di gestire sequenze ordinate. A è
sempre il bit 0, non posso cambiargli di posto.
Per ovviare a ciò, devo usare un passaggio intermedio:
Dim I(4) as string*1 ' Assumo che sia 1-based
I(1) = "A": I(2) = "B": I(3) = "C": I(4) = "D"
per includere I(n): S = S or 2 ^ (n - 1)
per escludere I(n): S = S and not 2^(n - 1)
posso quindi implementare le sequenze ordinate swappando gli elementi della
matrice I, mentre l'algoritmo che gestisc l'insieme lavora solo sugli indici
della matrice, senza curarsi del contenuto.
Il risultato è comunque macchinoso, quindi nel nostro caso la stringa ci
permette di risolvere entrambi i problemi in un colpo solo, comportandosi di
fatto come una lista (sequenza ordinata).
L'implementazione delle combinazioni (quindi non ordinate) con l'aritmetica
bit-a-bit potrebbe essere:
Public Sub Combina_Bin(ByVal I As Byte, ByVal MaxElements As Integer,
Optional ByVal prefix As Byte = 0)
 Dim ct As Integer, B As Integer
 For ct = 1 To 8 - MaxElements + 1
  B = (2 ^ (ct - 1))    ' Elemento corrente
  If (I And B) = B Then   ' E' presente nell'insieme
    If MaxElements = 1 Then
        Debug.Print Bin(prefix Or B)    ' Aggiunge al prefisso e stampa
     Else
        I = I And Not B    ' Toglie dall'insieme
        Combina_Bin I, MaxElements - 1, prefix Or B
    End If
  End If
 Next
End Sub
' Conversione binario - decimale
Public Function Dec(B As String) As Long
 Dim ct As Integer, Result As Long
 For ct = Len(B) To 1 Step -1
    If Mid$(B, ct, 1) = "1" Then
      Result = Result + 2 ^ (Len(B) - ct)
    End If
 Next
 Dec = Result
End Function
Public Function Bin(ByVal D As Long, Optional ByVal Cifre As Byte = 8) As
String
 Dim ct As Byte, Result As String
 For ct = 0 To Cifre - 1
  If (D And (2 ^ ct)) = (2 ^ ct) Then
    Result = "1" & Result
   Else
    Result = "0" & Result
  End If
 Next
 Bin = Result
End Function
Prova con
combina_bin dec("1111"), 2
i bit vanno letti da destra a sinistra


 Ciao ramarro,

ai numeri siano anch'essi ordinati ) per (n) e (m) qualsiasi.
Secondo questo modo di vedere, una colonna del totocalcio è un numero di
tredici cifre in base 3, dove X=0, 1 = 1, 2=2: puoi ottenere tutte le
permutazioni aggiungendo 1 ogni volta
XXXXXXXXXXXXX + 1 = XXXXXXXXXXXX1
XXXXXXXXXXXX1 + 1 = XXXXXXXXXXXX2
XXXXXXXXXXXX2 + 1 = XXXXXXXXXXX1X
L'unico "inconveniente" di questo sistema è che hai ripetizione di cifre (es
0001 o 1224, oppure 1XXX2), cosa che, del resto, in taluni casi può fare
comodo. In qualche post precedente si parlava di password hacking... gli
esempi visti prima con permutazioni e combinazioni non sono adatti, perché,
al contrario di quando immetti una password, non generano caratteri
duplicati.
Così non ci si può accusare di essere hackers...
Ciao e grazie di nuovo
Sig

 Ciao Ramarro,

o mi sbaglio ?
No, è possibilissimo, il problema è capire a che livello ti trovi.
Siccome ad ogni chiamata ricorsiva tu hai comunque una copia delle variabili
locali sullo stack, potresti definire delle variabili locali che ti servono
a tracciare l'esecuzione; potresti aggiungere una variabile Static che
incrementi all'entrata e decrementi all'uscita per tener conto del numero di
istanze. Anche i parametri passati sono salvati sullo stack chiamata per
chiamata, quindi puoi usare anche parametri ad hoc per tracciare il flusso.
Poi si tratta di visualizzare lo tack delle chiamate e di aprirti una
finestra di variabili locali per osservare i valori. E' un lavoraccio
faticoso, comunque.
Per tornare all'esempio dell'albero, la ricorsione arriva alla prima foglia
del primo ramo, quindi passa alle altre foglie del primo ramo, quindi passa
al secondo ramo.
Un classico esercizio di ricorsione è proprio il disegno di un albero
partendo dal tronco:
sub DisegnaAlbero(Angolo, lunghezza)
       delay(1000)
       linea angolo, lunghezza
       if lunghezza > min then
            DisegnaAlbero(Angolo - 45, lunghezza - 1)
            DisegnaAlbero(Angolo + 45, lunghezza - 1)
       end if
end sub
le pseudo-istruzioni utilizzano una grafica tipo turtle-graphics, in cui dai
la direzione della penna e la distanza da coprire.
Purtroppo non ho tempo di sviluppare l'esempio su un form VB, ma basterebbe
un quarto d'ora, credo!
