Generatore di combinazioni
pm
Ho la necessità di generare su Excel le diverse combinazioni che di
formano da un insieme di N oggetti presi a gruppi di K, con N>K.
Ho trovato il codice di 3 Public Function che generano combinazioni
usando l’algoritmo dell’odometro.
L’algoritmo si basa sul concetto di funzionamento dello strumento che
misura la distanza percorsa da un veicolo.
Un esempio per illustrare. Prendiamo un insieme formato dai primi 5
numeri interi. Le combinazioni che si possono formare in gruppi di K=3
sono 10. Immaginiamo di prendere 3 corone circolari concentriche (una
corona per ogni elemento di K) e di mettere in ognuna di esse in
sequenza i 5 numeri. Allineiamo rispetto a un comune raggio i numeri 1
di ogni corona. Poi, partendo dalla corona più esterna (escludendo
combinazioni non ammissibili tipo 1,1,1 o 1,2,2, ecc.), avanziamo di
uno scatto fino a completare il passaggio di ogni numero dei 5. Al
primo giro della corona più esterna avremo la seguente sequenza
#1 = 1,2,3
#2 = 1,2,4
#3 = 1,2,5
A questo punto, completato il giro sulla corona più esterna, si fa
scattare di un numero la corona intermedia e si riprende dopo a far
ruotare la corona più esterna. Questo dà:
#4 = 1,3,4
#5 = 1,3,5
Finito questo giro si prosegue a far completare il giro alla corona
intermedia per poi passare a far completare il giro anche ai numeri
della corona più interna.
#6 = 1,4,5
#7 = 2,3,4
#8 = 2,3,5
#9 = 2,4,5
#10 = 3,4,5
Si ottengono così le combinazioni in ordine lexicografico.
Il codice delle tre Function è il seguente:
Option Explicit
Dim Cwheel() As Long
Public Sub SetCombination(ByVal N As Long, ByVal K As Long, ByVal
Combn As String)
ReDim token(K) As String
token = Split(Combn, ",")
If UBound(token) <> K - 1 Then Exit Sub
Dim W As Long
ReDim Cwheel(0 To K)
For W = 1 To K
Cwheel(W) = Val(token(W - 1))
If Cwheel(W) <= Cwheel(W - 1) Then Exit Sub ' invalid combn
If Cwheel(W) > N Then Exit Sub ' ditto
Next
End Sub
Public Function ThisCombination() As String
'
' Current Combination readout
'
Dim i As Long, Comb As String
Comb = Cwheel(1)
For i = 2 To UBound(Cwheel)
Comb = Comb & ", " & Cwheel(i)
Next
ThisCombination = Comb
End Function
Public Sub NextCombination(ByVal N As Long, ByVal K As Long)
' "Combination Odometer"
'
' the array Cwheel contains the current
' K items combined, in increasing order.
' Each call to this sub will adjust Cwheel so it
contains
' the NEXT combination in lexographic order
'
Dim i As Long
Dim j As Long
i = K
While Cwheel(i) >= N - K + i
i = i - 1 ' find rightmost wheel that allows an increment
If i = 0 Then
' wraps around (natch!)
i = 1
Cwheel(1) = 0
End If
Wend
Cwheel(i) = Cwheel(i) + 1
For j = i + 1 To K
Cwheel(j) = Cwheel(i) + j - i
Next
End Sub
A questo punto non so come far girare il programma per avere su un
foglio di Excel le celle riempite dalle diverse combinazioni di N
numeri presi a gruppi di K, con N>K.
Chi può darmi una mano?
Grazie
Mario
Tiziano Marmiroli
>Ho la necessit� di generare su Excel le diverse combinazioni che di
>formano da un insieme di N oggetti presi a gruppi di K, con N>K.
>Ho trovato il codice di 3 Public Function che generano combinazioni
>usando l�algoritmo dell�odometro.
>A questo punto non so come far girare il programma per avere su un
>foglio di Excel le celle riempite dalle diverse combinazioni di N
>numeri presi a gruppi di K, con N>K.
>
>Chi pu� darmi una mano?
Menu Strumenti> Macro> Visual Basic Editor
Menu Inserisci> Modulo
e ci incolli il codice che trovi qui
http://www.excelabo.net/trucs/arrangements
Torni a Excel
A1: C (per indicare che vuoi ottenere le permutazioni)
A2: 3 corrispondente a K
A3: 1 da A3 in poi inserisci i N numeri
A4: 2
A5: 3
A6: 4
A7: 5
Selezioni la cella A1 e lanci la macro ListPermutations
Facci sapere se e come hai risolto, grazie.
--
Tiziano Marmiroli
Microsoft MVP - Office System
http://www.riolab.org
pm
> Il Mon, 14 Sep 2009 04:30:45 -0700 (PDT), pm ha scritto:
>
> >formano da un insieme di N oggetti presi a gruppi di K, con N>K.
> >Ho trovato il codice di 3 Public Function che generano combinazioni
> >usando l’algoritmo dell’odometro.
> >A questo punto non so come far girare il programma per avere su un
> >foglio di Excel le celle riempite dalle diverse combinazioni di N
> >numeri presi a gruppi di K, con N>K.
>
>
> Menu Strumenti> Macro> Visual Basic Editor
> Menu Inserisci> Modulo
>
> Torni a Excel
>
> A1: C (per indicare che vuoi ottenere le permutazioni)
> A2: 3 corrispondente a K
> A3: 1 da A3 in poi inserisci i N numeri
> A4: 2
> A5: 3
> A6: 4
> A7: 5
>
> Selezioni la cella A1 e lanci la macro ListPermutations
>
> Facci sapere se e come hai risolto, grazie.
> --
> Tiziano Marmiroli
> Microsoft MVP - Office Systemhttp://www.riolab.org
C’est magnifique, vraiment etonnant
Allez les bleus!
Tiziano, ad maiora
Many thanks
With kindest regards
Mario
pm
>
> >formano da un insieme di N oggetti presi a gruppi di K, con N>K.
> >Ho trovato il codice di 3 Public Function che generano combinazioni
> >usando l’algoritmo dell’odometro.
> >A questo punto non so come far girare il programma per avere su un
> >foglio di Excel le celle riempite dalle diverse combinazioni di N
> >numeri presi a gruppi di K, con N>K.
>
>
> Menu Strumenti> Macro> Visual Basic Editor
> Menu Inserisci> Modulo
>
> Torni a Excel
>
> A1: C (per indicare che vuoi ottenere le permutazioni)
> A2: 3 corrispondente a K
> A3: 1 da A3 in poi inserisci i N numeri
> A4: 2
> A5: 3
> A6: 4
> A7: 5
>
> Selezioni la cella A1 e lanci la macro ListPermutations
>
> Facci sapere se e come hai risolto, grazie.
> --
> Tiziano Marmiroli
> Microsoft MVP - Office Systemhttp://www.riolab.org
Tiziano,
un'ulteriore considerazione.
Nel caso in cui il numero delle righe della permutazione/combinazione
superasse quelle consentite in un foglio (65536)
come dirlo al programma?
Grazie ancora
Mario
Bruno Campanini
news:fb8c9641-b8be-47c9...@s6g2000vbp.googlegroups.com...
> Buongiorno,
>
> Ho la necessit� di generare su Excel le diverse combinazioni che di
> formano da un insieme di N oggetti presi a gruppi di K, con N>K.
Vatiante economica:
==============================
Sub Combinazioni_N()
Dim i As Long, j As Long, h As Long
Dim NumComb As Long, Comb_N() As Long
Dim N As Long, K As Long, S As String
Dim ES, TargetRange As Range
' Combinazioni di N elementi numerici presi K a K
' ------------------------------------------------
N = 15 ' Numero elementi
K = 4 ' Classe
ES = " " ' Separatore di elemento
Set TargetRange = [Sheet10!P15] ' Destinazione
' ------------------------------------------------
Application.Calculation = xlCalculationManual
Application.ScreenUpdating = False
NumComb = 1
For i = 0 To K - 1
NumComb = NumComb * (N - i) / (i + 1)
Next
ReDim Comb_N(1 To NumComb, 1 To K)
For j = 1 To K
Comb_N(1, j) = j
Next
For i = 2 To NumComb
h = K
Do Until Comb_N(i - 1, h) < N - K + h
h = h - 1
Loop
For j = 1 To h - 1
Comb_N(i, j) = Comb_N(i - 1, j)
Next
Comb_N(i, h) = Comb_N(i - 1, h) + 1
For j = h + 1 To K
Comb_N(i, j) = Comb_N(i, j - 1) + 1
Next
Next
h = 0
For i = 1 To UBound(Comb_N, 1)
For j = 1 To UBound(Comb_N, 2)
S = S & ES & Comb_N(i, j)
Next
h = h + 1
TargetRange(h) = S
S = ""
Next
Application.Calculation = xlCalculationAutomatic
Application.ScreenUpdating = True
End Sub
==================================
Se gli N elementi sono stringhe occorre qualche modifica.
Bruno
eliano
"pm" ha scritto:
Ciao Mario.
Glielo hanno già detto.:-))
Vedi un recente (quasi) post di Norman dove trattava routines di Myrna Lois
dell'anno 2000: http://tinyurl.com/d2ylx6
Qua si sta un po' ballando; speriamo che finisca alla svelta.
Saluti
Eliano
pm
>
> - Mostra testo citato -
Grazie Bruno per l’indicazione del codice.
Eliano,
forse non so ancora usare la modalità “ricerca” tra le risorse di
questo Gruppo e per questo chiedo venia.
Infatti, lancio la ricerca con le parole chiave “combinazioni” e
“Myrna” cliccando “Cerca in questo gruppo”, ma non riesco a replicare
il thread con la serie di messaggi che tu hai riassunto nel link:
http://tinyurl.com/l7w6p
Cliccando sul tuo link ottengo invece quest’altro collegamento:
http://groups.google.it/group/microsoft.public.it.office.excel/browse_thread/thread/48be6a9c4d6081e0?hl=it&tvc=2&q=combinazioni+myrna+
Per evitare di porre quesiti a cui il Gruppo ha già risposto in
passato, puoi indicarmi, per favore, il percorso per arrivare al link
da te segnalato?
Grazie per la risposta
Ciao, Mario
eliano
"pm" ha scritto:
> Eliano,
>
> forse non so ancora usare la modalità “ricerca” tra le risorse di
> questo Gruppo e per questo chiedo venia.
> Infatti, lancio la ricerca con le parole chiave “combinazioni” e
> “Myrna” cliccando “Cerca in questo gruppo”, ma non riesco a replicare
> il thread con la serie di messaggi che tu hai riassunto nel link:
> http://tinyurl.com/l7w6p
>
> Cliccando sul tuo link ottengo invece quest’altro collegamento:
> http://groups.google.it/group/microsoft.public.it.office.excel/browse_thread/thread/48be6a9c4d6081e0?hl=it&tvc=2&q=combinazioni+myrna+
>
> Per evitare di porre quesiti a cui il Gruppo ha già risposto in
> passato, puoi indicarmi, per favore, il percorso per arrivare al link
> da te segnalato?
>
Ciao Mario.
Ti confermo che il link è quello già comunicato che ti dovrebbe portare al
thread: Combinazioni contenente la macro di interesse.
Per evitarti anche la fatica di una nuova ricerca :-)) vedi sul mio disco
remoto:
http://mio.discoremoto.alice.it/falinieliano/ il file:
combinazioniMyrna_Norman
Facci sapere,
Eliano
pm
> "pm" ha scritto:
>
>
>
>
>
> > Eliano,
>
> > forse non so ancora usare la modalità “ricerca” tra le risorse di
> > questo Gruppo e per questo chiedo venia.
> > Infatti, lancio la ricerca con le parole chiave “combinazioni” e
> > “Myrna” cliccando “Cerca in questo gruppo”, ma non riesco a replicare
> > il thread con la serie di messaggi che tu hai riassunto nel link:
> >http://tinyurl.com/l7w6p
>
> > Cliccando sul tuo link ottengo invece quest’altro collegamento:
>
> > Per evitare di porre quesiti a cui il Gruppo ha già risposto in
> > passato, puoi indicarmi, per favore, il percorso per arrivare al link
> > da te segnalato?
>
> Ciao Mario.
> Ti confermo che il link è quello già comunicato che ti dovrebbe portare al
> thread: Combinazioni contenente la macro di interesse.
>
> Per evitarti anche la fatica di una nuova ricerca :-)) vedi sul mio disco
> remoto:http://mio.discoremoto.alice.it/falinieliano/ il file:
> combinazioniMyrna_Norman
>
> Facci sapere,
>
> - Mostra testo citato -
Eliano
grazie per la risposta e riconoscente per il link al tuo disco remoto.
Ciao Mario
Marcovince
combinazioni possibili (numeri in gioco da 1 a 20)che rispettino
queste -ad esempio- SOLO e a TUTTE queste condizioni:
3 numeri isolati (cioè non consecutivi)
+ 2 coppie di numeri consecutivi
+ 1 terzina di di numeri consecutivi
+ 10 spazi vuoti (tot = 20 numeri)
oppure:
2 numeri isolati (cioè non consecutivi)
+ 2 quartine di di numeri consecutivi
+ 10 spazi vuoti (tot = 20 numeri)?
grazie!!!