Newsgroup: it.comp.appl.access
Titolo: Programmazione: Permutazioni e dintorni

Oggi ho avuto un pò di tempo e così ho corredato la funzione che genera le
permutazioni, postata ieri in risposta a News,
con alcune considerazioni, che forse sono di interesse generale.
'Crea un nuovo modulo e...
'copia a partire da qui
Option Compare Database
Option Explicit
Option Base 1
'***************************************************************************
****
' CONSIDERAZIONI GENERALI
'***************************************************************************
****
'
'Esistono almeno una ventina di algoritmi diversi per la generazione
'delle permutazioni di n elementi presi k alla volta.
'Ho imparato molto sulla ricorsione, dallo studio di questi algoritmi.
'Se per te programmare è anche un'arte, ti  consiglio di tentare di
'abbozzare una soluzione usando la creatività e non la memoria...
'
'La complessità computazionale di questo algoritmo è:
'  n!
'------
'(n-k)!
'
'Se k = n => O(n) = n!
'
'ATTENZIONE perciò ad invocare questa funzione.
'Già con n = 10 vengono eseguite 3.628.800 volte le istruzioni del ciclo
For...Next
'della funzione Permutazioni!!!
'
'***************************************************************************
****
' CONSIDERAZIONI SUL NAMING
'***************************************************************************
****
'
'Questo è il mio naming
'xyZzzz
'x------------> Visibilità:
'                                   g = global/public
'                                   m = modulo
'                                   l locale alla routine
'y------------> Tipo, un carattere è poco per rappresentare tutti i tipi ma
il 95% dei tipi che io uso sono
'                                   i = Integer
'                                   l = Long
'                                   s = String
'                                   f = Single /Double
'                                   d = Date
'                      nell'altro 5% cadono tutti gli altri tipi
'                                   v = Tutti gli altri per me sono come i
variant,
'
'Zzzz---------> Stringa significativa...
'Nel codice da me scritto non troverete mai
'                                   byt Byte
'                                   f Boolean
'                                   int Integer
'                                   lng Long
'                                   sng Single
'                                   dbl Double
'                                   cur Currency
'                                   dat Date
'                                   obj Object
'                                   str String
'                                   stf String (fixed length)
'                                   var Variant
'Trovo troppo costoso usare tre caratteri...
'non mi interessa conoscere il tipo di pochissime variabili...
'so che su questo molti non sono d'accordo, ma a me non interessa ;-)
'
'Condivido invece il naming Reddick per i controlli:
'                                   app Application
'*                                  chk CheckBox
'*                                  cbo ComboBox
'*                                  cmd CommandButton
'*                                  ctl Control
'                                   ctls Controls
'                                   ocx CustomControl
'                                   dcm DoCmd
'*                                  frm Form
'                                   frms Forms
'                                   grl GroupLevel
'*                                  img Image
'*                                  lbl Label
'                                   lin Line
'*                                  lst ListBox
'                                   bas Module
'                                   ole ObjectFrame
'*                                  opt OptionButton
'                                   fra OptionGroup(frame)
'                                   brk PageBreak
'                                   pal PaletteButton
'                                   prps Properties
'                                   shp Rectangle
'*                                  rpt Report
'                                   rpts Reports
'                                   scr Screen
'*                                  sec Section
'                                   sfr SubForm
'                                   srp SubReport
'*                                  txt TextBox
'*                                  tgl ToggleButton
'
'anche se io ho avuto la necessità di definire solo quelli con * ...
'
'Mi sto trovando molto bene anche con il naming dei documenti Access
'                                   zt  per le tabelle,  esempio  ztClienti
'                                   zq  per le query,    esempio  zqClienti
'                                   zf  per le maschere, esempio  zfClienti
'                                   zr  per i  report,   esempio  zrCatalogo
'                                   zs  per le macro,    esempio  zsCompila
'                                   zm  per i  moduli    esempio  zmUtility
'Se in fase di analisi, ho la sfiga di chiamare un documento con il nome
sbagliato
'grazie e strumenti tipo find & replace
'(del mio amico Rick 
http://www.rickworld.com/download.html
, shareware e
funzionante
'anche per chi non si registra), fare un rinomina globale è relativamente
facile.
'***************************************************************************
****
' PERMUTAZIONI by M.A.Engineering di Michele Amato
' 
http://utenti.worldonline.it/micheleamato
'***************************************************************************
****
' Per commenti e/o delucidazioni
' 
maengi...@libero.it
'
'***************************************************************************
****
Dim msColumns() As String * 1
Dim mlN As Long
Dim mlR As Long
Dim msPermutazioni As String 'Elenco delle permutazioni separate da ;
Const cSEPARATORE = ";"
Public Function Permuta(rsAlfabeto As String, Optional rlKappaPerVolta As
Integer) As String
Dim llK As Long
  mlN = Len(rsAlfabeto)
  If IsMissing(rlKappaPerVolta) Then
    mlR = mlN
  Else
    If rlKappaPerVolta <= mlN Then
      mlR = rlKappaPerVolta
    Else
      Err.Raise 12321, "Permuta", "Argomento della funzione Permuta NON
valido."
      Exit Function
    End If
  End If
  ReDim msColumns(mlN)
  For llK = 1 To mlN
    msColumns(llK) = Mid(rsAlfabeto, llK, 1)
  Next llK
  msPermutazioni = vbNullString
  Call Permutazioni(1)
  Permuta = msPermutazioni
End Function
'***************************************************************************
****
' COMPLESSITA' COMPUTAZIONALE
'***************************************************************************
****
'
'La complessità computazionale di questo algoritmo è:
'n=mlN
'k=mlK
'
'                 n!
'O(n,k) = ------
'              (n-k)!
'
'Se k = n => O(n) = n!
'
'ATTENZIONE perciò ad invocare questa funzione.
'Già con n = 10 vengono eseguite 3.628.800 volte le istruzioni del ciclo
For...Next
'della funzione Permutazioni!!!
Private Function Permutazioni(rlK As Long)
Dim llI As Long
Dim llJ As Long
Dim lsTemp As String
Dim lsPermutazione As String
  For llJ = rlK To mlN
    lsTemp = msColumns(rlK)
    msColumns(rlK) = msColumns(llJ)
    msColumns(llJ) = lsTemp
    If rlK < mlR Then
      Permutazioni (rlK + 1)
    Else
      lsPermutazione = vbNullString
      For llI = 1 To mlR
        lsPermutazione = lsPermutazione & msColumns(llI)
      Next
      'Qui puoi personalizzare la routine per farle fare ciò che a te
interessa
      '1)
      'per esempio potresti decidere di generare dei record...
      'mvRecordSet.AddNew ...
      '2)
      'Salvarle in un file di testo...
      'Print #miFileHandler, lsPermutazione
      '3)
      '"Appendere" la permutazione appena costruita ad una stringa
      'ATTENZIONE perchè questo potrebbe creare problemi già con
Len(rsAlfabeto) > 6
      'msPermutazioni = msPermutazioni & lsPermutazione & cSEPARATORE
      '4)
      'Testing
      Debug.Print lsPermutazione
    End If
    lsTemp = msColumns(rlK)
    msColumns(rlK) = msColumns(llJ)
    msColumns(llJ) = lsTemp
  Next llJ
End Function
'Fine Codice
'Altro algoritmino interessante per capire la ricorsione...
Public Function Fattoriale(n As Integer) As Double
  If n <= 1 Then
    Fattoriale = 1
  Else
    Fattoriale = n * Fattoriale(n - 1)
  End If
End Function
'Copia fino a qui
HTH
Un saluto a tutti
Michele Amato

 permutazioni, postata ieri in risposta a News,
cut
Ciao Michele,
scusa, hai letto la risposta che ho dato al post delle "concatenazioni"?
Premetto che non avevo ancora scaricato il NG la mattina e quindi non avevo
letto la tua soluzione, ma mi sembra che la mia soluzione sia piu' compatta.
Personalmente mi sono molto dedicato al metodo prima di scrivere sono
partito dal presupposto che la ricorsione si puo' gestire su una stringa via
via piu' corta, questo semplifica molto i passaggi consentendo di conservare
una certa semplicità nella funzione ricorsiva e, contemporaneamente, una
diminuzione della complessita' dell'elaborazione grazie al fatto di dover
processare una stringa piu' corta della precedente ogni volta.
Oltre tutto l'elaborazione si riduce a un "frapponimento" del carattere
"rimasto fuori" sulla sequela generata dall'elaborazione sottostante.
Cosa ne pensi?
Ciao, Sib


Te lo faccio sapere presto,
un saluto
Michele Amato

   End If
In conclusione, complimenti per la soluzione, frutto di un ragionamento
semplice e lineare, ma è necessario lavorarci sopra ancora un pò, al fine di
rendere
l'algoritmo meno assetato di memoria ;-)
Se hai voglia di migliorarlo considera anche l'introduzione del "k per
volta".
Saluti
Michele Amato

 volta".
Non ho capito bene cosa intendi con "K per volta", la prima cosa che mi
viene in mente e' il calcolo delle combinazioni sottostanti, ma sarebbe
appunto cio' che ho fatto.
Grazie e ciao, Sib

 piu' di sette caratteri aveva poco significato dal punto di vista...
Sono d'accordo con te, perň, per principio, cerco di avere nel "corredo"
algoritmi con il minor numero possibile di limiti.
Saluti
Michele Amato

 Michele Amato
ad ogni modo non e' affatto difficile, qualora ve ne fosse la necessita',
applicare lo stesso ragionamento, invece che a una matrice di stringhe, a
una singola stringa o, molto meglio, a una tabella (dato che estrarre dati
da una stringa non e' comodo) e questo risolverebbe alla radice il problema
che poni.
D'altro canto sostituendo le variabili che ho dichiarato Integer con delle
Long si calcolano tranquillamentepermutazioni anche di 10 simboli (di piu'
non ho neanche provato dato che gia' con dieci simboli si ottengono
3.628.800 elementi)
Se fai due conti significa che una stringa che debba contenere tutti questi
elementi sarebbe lunga (10 (i simboli) + 1 (il separatore))*3628800 (gli
elementi) che fa circa 40.000.000 di byte (non poco! pensa a farci delle
ricerche all'interno!), per non dire che gia' con disposizioni di 12
elementi ti servirebbe una stringa di oltre 6 miliardi di byte (stringa che,
ovviemente, non esiste dato che la stringa piu' grande che puoi fare e' di
2Gb)
Ciao, Sib

 sarebbe  appunto cio' che ho fatto.
Vediamo se un esempio è sufficiente...:
Ho un insieme di 10 simboli (cifre decimali),
voglio tutte le disposizioni di questi 10 simboli presi 4 per volta...
0123, 0124, 0125, ..., 9999
n = 10
k = 4
Ok?
HTH
Michele Amato

 > "Michele Amato"

cut
Anche se ho confuso il termine "combinazione", avevo intuito che intendevi
"presi  a K a K" (questa, sono sicuro, e' la dicitura esatta)
Ad ogni modo non credo che questo apporterebbe notevoli miglioramenti,
infatti e' il numero finale delle combinazioni che crea il problema, non
l'elaborazione in se.
Ciao, Sib