Newsgroup: it.comp.lang.visual-basic
Titolo: permutazioni

Qualcuno è in grado di fornirmi un algoritmo che mi permetta di avere tutte
le permutazioni possibili di una serie di dati?
Non preoccupatevi non mi serve per trovare delle password! :)
Grazie Paolo


  Ciao,
questa tua domanda, semplice in apparenza, ha allontanato da me ogni gaiezza
per ben due giorni, non postare mai piu' domande del genere! :-))))))
  Scherzi a parte, al problema da te posto avevo da poco cominciato ad
interessarmi anch'io (che mi sono messo in testa di realizzare un
prgrammello per diventare in poco tempo miliardario con il SuperEnalotto),
avevo raccolto qualche appunto ed ora ti racconto quel poco che ho'
imparato.
  Anzitutto con il termine Permutazioni, in senso lato, si indicano
generalmente: Disposizioni con ripetizione (Campioni), Disposizioni semplici
(Permutazioni), Combinazioni semplici e con Ripetizione, ecc.. Quindi e'
bene specificare fin da principio cosa si vuole ottenere per evitare
equivoci. Ecco un brevissimo campionario di termini e concetti di Calcolo
Combinatorio:
1. __Disposizioni con ripetizione (Campioni)__
  Consideriamo ad esempio la serie di numeri naturali, se ci chiedessimo
quanti numeri è possibile scrivere utilizzando le prime tre cifre senza
tener conto delle ripetizioni di ogni simbolo, allora parleremmo di
Campioni.
  Ex1:
    I campioni generabili utilizzando i primi 3 numeri naturali sono:
            111, 112, ..., 221, 222, ..., 333.
  Ex2:
    I campioni estraibili dai simboli 1,2,3 ragruppati a 2 a 2 con
ripetizioni sono:
         11, 12, 13, 21, 22, 23, 31, 32, 33.
  Piu' in generale considereremo la seguente definizione
  DISPOSIZIONI CON RIPETIZIONI - Dati 'n' oggetti distinti e detto 'k' un
numero intero positivo, si chiamano disposizioni con ripetizione, di questi
'n oggetti a k a k', tutti i gruppi che si possono formare con gli n oggetti
dati in modo che ogni gruppo contenga k oggetti distinti o coincidenti (in
tutto o in parte) e inoltre due gruppi differiscano tra loro o per qualche
elemento o per l'ordine con cui gli oggetti sono disposti.
  Il numero delle disposizioni con ripetizione di n oggetti a k a k si suole
denotare col
           (r)                   (r)    k
simbolo   D     e si prova che  D    = n .
           n,k                   n,k
  Un metodo banale ed immediato per la generazione, ad esempio, dei campioni
dell'Ex2, consiste nell'utilizzare cicli For..Next nidificati, ad ex:
   :
   For i=1 to 3
     For j=1 to 3
       Debug.Print i & " " & j
     Next j
   Next i
   :
OSS: per trovare una password, conoscendo il nmero di simboli di cui è
composta e considerando che essi potrebbero essere ripetuti, dovremmo
prendere in considerazione i campioni e non le permutazioni.
2. __Combinazioni semplici (Combinazioni senza ripetizioni)__
  Supponiamo di avere a disposizione un mazzo di 10 carte da poker
(dall'asso al 10) e estrarre da esso ogni volta a caso tre carte. Quanti
insiemi diversi di 3 carte potremo avere?
  In questo caso si parlera' di COMBINAZIONI; in particolare diremo che il
processo di 'generazione delle combinazioni' genera "tutte le permutazioni
di n simboli, presi k alla volta, senza ripetizioni"
  In particolare questa e' la definizione di combinazioni senza ripetizione:
  COMBINAZIONI SENZA RIPETIZIONI - Dati 'n' oggetti distinti e detto 'k' un
numero intero positivo non maggiore di n, si chiamano combinazioni semplici,
di questi 'n oggetti a k a k', tutti i gruppi che si possono formare con gli
n oggetti dati in modo che ogni gruppo contenga k oggetti distinti,
ritenendo due gruppi non distinti se e solo se contengono gli stessi
elementi.
  Il numero delle Combinazioni semplici di n oggetti a k a k si suole
denotare col
                                       n·(n-1)·(n-2)·...·(n-k+1)
simbolo   C     e si prova che  C    = ------------------------- .
           n,k                   n,k               k!
  Un metodo banale ed immediato per la generazione, ad esempio, delle
combinazioni dei primi 5 interi presi 3 alla volta, e':
   :
   For i=1 to 3
     For j=i+1 to 4
       For k=j+1 to 5
         Debug.Print i & " " & j & " " k
       Next k
     Next j
   Next i
   :
3. __Disposizioni semplici (permutazioni)__
  Nel caso precedente abbiamo considerato il caso in cui l'ordine dei
simboli all'interno di una permutazione non era da tenere in conto (ad ex.
nel gioco del poker le due permutazioni [10, J, Q, K, A] e [Q, A, 10, K, J]
rappresentano la stessa, fortunata :-), combinazione).
  Ora, invece, ci proponiamo di conoscere il numero dei sottoinsiemi di k
elementi (diversi in ordine e contenuto) estraibile da un insieme di 'n'
simboli distinti. Questi sottoinsiemi si indicheranno col nome di
disposizioni semplici.
  In maniera piu' formale possiamo dare la seguente definizione:
  DISPOSIZIONI SEMPLICI - Dati 'n' oggetti distinti e detto 'k' un intero
(con 0 < k <= n), si chiamano _disposizioni_semplici_ di questi n oggetti a
k a k tutti i gruppi che si possono formare con gli n oggetti dati in modo
che ogni gruppo contenga k oggetti (distinti) e inoltre due gruppi qualsiasi
differiscano tra loro per qualche oggetto o per l'ordine con cui gli oggetti
sono disposti.
  Il numero delle Disposizioni semplici di n oggetti a k a k si denota col
simbolo   D     e si prova che  D    = n·(n-1)·(n-2)·...·(n-k+1).
           n,k                   n,k
  Un metodo immediato per la generazione, ad esempio, delle disposizioni
semplici dei primi 5 interi presi 3 alla volta, e':
   :
   For i=1 to 5
     For j=1 to 5
       For k=1 to 5
         if (i<>j and i<>k and j<>k) then Debug.Print i & " " & j & " " k
       Next k
     Next j
   Next i
   :
4. ___Considerazioni e Bibliografia___
  Tutti gli ALGORITMI sopra esposti funzionano ma NON SONO GENERALIZZABILI.
Con i metodi su esposti non e' possibile realizzare un algoritmo che possa
funzionare per valori differenti di 'n' e di 'k'.
  Dopo essermi inutilmente cimentato nella ricerca di un metodo fai-da-te
per cercare una soluzione generale ai (semplici) problemi sopra esposti, son
dovuto ricorrere al consulto di alcuni polverosi testi della mia libreria.
  Gli algoritmi compaiono nel programma CombPerm che provvedero' ad
uploadare al piu' presto (appena avro' ricevuto il permesso) su
it.binari.visual-basic .
  Ecco i testi da cui ho tratto le mie informazionii:
  "ALGORITMI FONDAMENTALI" di R. Geoff Dromey (Gruppo Editoriale Jackson,
1989) da qui ho tratto gli algoritmi ricorsivi implementati nel programma;
rimando ad esso per la spiegazione degli algoritmi e per una bibliografia
piu' approfondita su questi argomenti.
  "LEZIONI DI ANALISI MATEMATICA 1" di C. Vinti (Galileo Editrice - Perugia)
da qui ho rispolverato formulette e concetti relativi al calcolo
combinatorio.
                                          Simone Falchetti
 
Simon...@tiscalinet.it

 wrote in message
MFYU3.8596$s17.1...@typhoon.libero.it...



  Su it.binari.visual-basic ho caricato un programmino contenente le
funzioni (VB) che risolvono i problemi di combinazioni/permutazioni di cui
parlavo nel mio precedente msg.
  Ciao.