Calcolo delle combinazioni semplici

[El Gioppinho]

Vorrei scrivere un programma che calcoli tutte le combinazioni semplici
possibili in un insieme di n numeri, presi k alla volta senza ripetizioni.
Le combinazioni possibili sono, com'è logico :

n!
---------
k! (n-k)!

Il programma dovrebbe calcolare tutte le varie combinazioni possibili, ad
esempio se n sono i primi 4 numeri naturali e k=2, dovrebbe fornire :

1-2
1-3
1-4
2-3
2-4
3-4

senza dare combinazioni tipo 2-1, visto che l'ordine non è importante (c'è
già 1-2).
Purtroppo non riesco a definire il procedimento ricorsivo quando k>=3,
potete aiutarmi ?

[priamo]

Ecco una funzione ricorsiva scritta in GAP (vedi http://www.gap-system.org/)

combinazioni := function (n,k)
local comb, smallercombs, i, tmp, tmpcomb, x, tmpresult;


if (n<k or k<0 or n<0) then
return [];
elif k=0 then
return [[]];
fi;
comb:=[];
smallercombs:=combinazioni(n-1,k-1);
for i in [1..n-k+1] do
for tmp in smallercombs do
tmpcomb:=ShallowCopy(tmp);
if tmpcomb<>[] then
for x in [1..Length(tmpcomb)] do
tmpcomb[x]:= tmpcomb[x]+i;
od;
fi;
tmpresult:=[i];
Append(tmpresult,tmpcomb);
Add(comb,tmpresult);
od;
od;
return comb;
end;


Con un esempio di output:

gap> combinazioni(6,4);
[ [ 1, 2, 3, 4 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 6 ], [ 1, 2, 4, 5 ],
[ 1, 2, 4, 6 ], [ 1, 2, 4, 7 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 7 ],
[ 1, 2, 5, 8 ], [ 1, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 3, 4, 7 ],
[ 1, 3, 5, 6 ], [ 1, 3, 5, 7 ], [ 1, 3, 5, 8 ], [ 1, 3, 6, 7 ],
[ 1, 3, 6, 8 ], [ 1, 3, 6, 9 ], [ 1, 4, 5, 6 ], [ 1, 4, 5, 7 ],
[ 1, 4, 5, 8 ], [ 1, 4, 6, 7 ], [ 1, 4, 6, 8 ], [ 1, 4, 6, 9 ],
[ 1, 4, 7, 8 ], [ 1, 4, 7, 9 ], [ 1, 4, 7, 10 ], [ 2, 3, 4, 5 ],
[ 2, 3, 4, 6 ], [ 2, 3, 4, 7 ], [ 2, 3, 5, 6 ], [ 2, 3, 5, 7 ],
[ 2, 3, 5, 8 ], [ 2, 3, 6, 7 ], [ 2, 3, 6, 8 ], [ 2, 3, 6, 9 ],
[ 2, 4, 5, 6 ], [ 2, 4, 5, 7 ], [ 2, 4, 5, 8 ], [ 2, 4, 6, 7 ],
[ 2, 4, 6, 8 ], [ 2, 4, 6, 9 ], [ 2, 4, 7, 8 ], [ 2, 4, 7, 9 ],
[ 2, 4, 7, 10 ], [ 2, 5, 6, 7 ], [ 2, 5, 6, 8 ], [ 2, 5, 6, 9 ],
[ 2, 5, 7, 8 ], [ 2, 5, 7, 9 ], [ 2, 5, 7, 10 ], [ 2, 5, 8, 9 ],
[ 2, 5, 8, 10 ], [ 2, 5, 8, 11 ], [ 3, 4, 5, 6 ], [ 3, 4, 5, 7 ],
[ 3, 4, 5, 8 ], [ 3, 4, 6, 7 ], [ 3, 4, 6, 8 ], [ 3, 4, 6, 9 ],
[ 3, 4, 7, 8 ], [ 3, 4, 7, 9 ], [ 3, 4, 7, 10 ], [ 3, 5, 6, 7 ],
[ 3, 5, 6, 8 ], [ 3, 5, 6, 9 ], [ 3, 5, 7, 8 ], [ 3, 5, 7, 9 ],
[ 3, 5, 7, 10 ], [ 3, 5, 8, 9 ], [ 3, 5, 8, 10 ], [ 3, 5, 8, 11 ],
[ 3, 6, 7, 8 ], [ 3, 6, 7, 9 ], [ 3, 6, 7, 10 ], [ 3, 6, 8, 9 ],
[ 3, 6, 8, 10 ], [ 3, 6, 8, 11 ], [ 3, 6, 9, 10 ], [ 3, 6, 9, 11 ],
[ 3, 6, 9, 12 ] ]

Post by El Gioppinho
Vorrei scrivere un programma che calcoli tutte le combinazioni semplici
possibili in un insieme di n numeri, presi k alla volta senza ripetizioni.
n!
---------
k! (n-k)!
Il programma dovrebbe calcolare tutte le varie combinazioni possibili, ad
1-2
1-3
1-4
2-3
2-4
3-4
senza dare combinazioni tipo 2-1, visto che l'ordine non è importante (c'è
già 1-2).
Purtroppo non riesco a definire il procedimento ricorsivo quando k>=3,
potete aiutarmi ?

[El Gioppinho]

Ti ringrazio moltissimo, ma avrei qualche domandina da farti, se non ti
dispiace. Innanzitutto, sul risultato che appare con questo programma : se
nell'esempio cerca le combinazioni identificate dal coefficiente binomiale
(6 su 4), com'è possibile che ci siano numeri fino al 12 ? Non dovrebbero
essere tutte le combinazioni degli interi tra 1 e 6, a gruppi di 4 ?

Seconda domanda : dato che non conosco il linguaggio GAP, vorrei sapere se :

le variabili dichiarate local sono tutte di tipo intero ?
od indica la fine di un ciclo for...do ?
fi indica la fine di un ciclo if...then ?
elif sta per ELSE IF ?
a cosa serve la funzione SHALLOWCOPY ?
a cosa serve la funzione APPEND ?

Scusami ma questo GAP proprio non lo conosco, e mi sembra un pò arduo da
decifrare. Ti ringrazio ancora tantissimo se con pazienza vorrai
rispondermi...

Ciao

Post by priamo
Ecco una funzione ricorsiva scritta in GAP (vedi
http://www.gap-system.org/)
combinazioni := function (n,k)
local comb, smallercombs, i, tmp, tmpcomb, x, tmpresult;
if (n<k or k<0 or n<0) then
return [];
elif k=0 then
return [[]];
fi;
comb:=[];
smallercombs:=combinazioni(n-1,k-1);
for i in [1..n-k+1] do
for tmp in smallercombs do
tmpcomb:=ShallowCopy(tmp);
if tmpcomb<>[] then
for x in [1..Length(tmpcomb)] do
tmpcomb[x]:= tmpcomb[x]+i;
od;
fi;
tmpresult:=[i];
Append(tmpresult,tmpcomb);
Add(comb,tmpresult);
od;
od;
return comb;
end;
gap> combinazioni(6,4);
[ [ 1, 2, 3, 4 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 6 ], [ 1, 2, 4, 5 ],
[ 1, 2, 4, 6 ], [ 1, 2, 4, 7 ], [ 1, 2, 5, 6 ], [ 1, 2, 5, 7 ],
[ 1, 2, 5, 8 ], [ 1, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 3, 4, 7 ],
[ 1, 3, 5, 6 ], [ 1, 3, 5, 7 ], [ 1, 3, 5, 8 ], [ 1, 3, 6, 7 ],
[ 1, 3, 6, 8 ], [ 1, 3, 6, 9 ], [ 1, 4, 5, 6 ], [ 1, 4, 5, 7 ],
[ 1, 4, 5, 8 ], [ 1, 4, 6, 7 ], [ 1, 4, 6, 8 ], [ 1, 4, 6, 9 ],
[ 1, 4, 7, 8 ], [ 1, 4, 7, 9 ], [ 1, 4, 7, 10 ], [ 2, 3, 4, 5 ],
[ 2, 3, 4, 6 ], [ 2, 3, 4, 7 ], [ 2, 3, 5, 6 ], [ 2, 3, 5, 7 ],
[ 2, 3, 5, 8 ], [ 2, 3, 6, 7 ], [ 2, 3, 6, 8 ], [ 2, 3, 6, 9 ],
[ 2, 4, 5, 6 ], [ 2, 4, 5, 7 ], [ 2, 4, 5, 8 ], [ 2, 4, 6, 7 ],
[ 2, 4, 6, 8 ], [ 2, 4, 6, 9 ], [ 2, 4, 7, 8 ], [ 2, 4, 7, 9 ],
[ 2, 4, 7, 10 ], [ 2, 5, 6, 7 ], [ 2, 5, 6, 8 ], [ 2, 5, 6, 9 ],
[ 2, 5, 7, 8 ], [ 2, 5, 7, 9 ], [ 2, 5, 7, 10 ], [ 2, 5, 8, 9 ],
[ 2, 5, 8, 10 ], [ 2, 5, 8, 11 ], [ 3, 4, 5, 6 ], [ 3, 4, 5, 7 ],
[ 3, 4, 5, 8 ], [ 3, 4, 6, 7 ], [ 3, 4, 6, 8 ], [ 3, 4, 6, 9 ],
[ 3, 4, 7, 8 ], [ 3, 4, 7, 9 ], [ 3, 4, 7, 10 ], [ 3, 5, 6, 7 ],
[ 3, 5, 6, 8 ], [ 3, 5, 6, 9 ], [ 3, 5, 7, 8 ], [ 3, 5, 7, 9 ],
[ 3, 5, 7, 10 ], [ 3, 5, 8, 9 ], [ 3, 5, 8, 10 ], [ 3, 5, 8, 11 ],
[ 3, 6, 7, 8 ], [ 3, 6, 7, 9 ], [ 3, 6, 7, 10 ], [ 3, 6, 8, 9 ],
[ 3, 6, 8, 10 ], [ 3, 6, 8, 11 ], [ 3, 6, 9, 10 ], [ 3, 6, 9, 11 ],
[ 3, 6, 9, 12 ] ]

Post by El Gioppinho
Vorrei scrivere un programma che calcoli tutte le combinazioni semplici
possibili in un insieme di n numeri, presi k alla volta senza
ripetizioni.
n!
---------
k! (n-k)!
Il programma dovrebbe calcolare tutte le varie combinazioni possibili, ad
1-2
1-3
1-4
2-3
2-4
3-4
senza dare combinazioni tipo 2-1, visto che l'ordine non è importante (c'è
già 1-2).
Purtroppo non riesco a definire il procedimento ricorsivo quando k>=3,
potete aiutarmi ?

[priamo]

oops...

Ecco la versione corretta. Per la fretta non avevo guardato nemmeno
l'output (smallercombs andava definito in dipendenza da i...)
---------------------------------------------------------------------
combinazioni := function (n,k)
local comb, smallercombs, i, tmp, tmpcomb, x, tmpresult;

if (n<k or k<0 or n<0) then
return [];
elif k=0 then
return [[]];
fi;
comb:=[];
for i in [1..n-k+1] do
smallercombs:=combinazioni(n-i,k-1);
for tmp in smallercombs do
tmpcomb:=ShallowCopy(tmp);
if tmpcomb<>[] then
for x in [1..Length(tmpcomb)] do
tmpcomb[x]:= tmpcomb[x]+i;
od;
fi;
tmpresult:=[i];
Append(tmpresult,tmpcomb);
Add(comb,tmpresult);
od;
od;
return comb;
end;


---------------------------------------------------------------------
gap> combinazioni(6,4);
[ [ 1, 2, 3, 4 ], [ 1, 2, 3, 5 ], [ 1, 2, 3, 6 ], [ 1, 2, 4, 5 ],
[ 1, 2, 4, 6 ], [ 1, 2, 5, 6 ], [ 1, 3, 4, 5 ], [ 1, 3, 4, 6 ],
[ 1, 3, 5, 6 ], [ 1, 4, 5, 6 ], [ 2, 3, 4, 5 ], [ 2, 3, 4, 6 ],
[ 2, 3, 5, 6 ], [ 2, 4, 5, 6 ], [ 3, 4, 5, 6 ] ]
---------------------------------------------------------------------

Post by El Gioppinho
le variabili dichiarate local sono tutte di tipo intero ?

In GAP non serve dichiarare i tipi

Post by El Gioppinho
od indica la fine di un ciclo for...do ?

il for è sempre su una lista

Post by El Gioppinho
fi indica la fine di un ciclo if...then ?

yes

Post by El Gioppinho
elif sta per ELSE IF ?

yes

Post by El Gioppinho
a cosa serve la funzione SHALLOWCOPY ?

Serve a produrre una copia separata e mutabile di una lista (in modo da
non alterarela lista originale)

Post by El Gioppinho
a cosa serve la funzione APPEND ?

Aggiunge una lista alla fine di un'altra

Post by El Gioppinho
Scusami ma questo GAP proprio non lo conosco, e mi sembra un pò arduo da
decifrare. Ti ringrazio ancora tantissimo se con pazienza vorrai
rispondermi...

Se conosci python non ci vuole molto ad adattare il programma. Ma credo
che sia semplicissimo trasposrlo in c o che altro lo schema e` il seguente

devo creare tutte le combinazioni n su k

for i= 1 to n...

calcolo le combinazioni di n-i+1 oggetti a k-1 a k-1 (sono liste che
contengono gli interi tra 1 e n-i+1)

aggiungo i a ciascun numero che compare in queste combinazioni.

a ciascuna di queste combinazioni modificate antepongo i come inizio lista

il gioco e` fatto.

Bye

Post by El Gioppinho
Ciao

[priamo]

Errata

Post by priamo
calcolo le combinazioni di n-i+1 oggetti a k-1 a k-1 (sono liste che
contengono gli interi tra 1 e n-i+1)

Corrige

calcolo le combinazioni di n-i oggetti a k-1 a k-1 (sono liste che
contengono gli interi tra 1 e n-i)

[priamo]

Post by priamo

Post by El Gioppinho
a cosa serve la funzione SHALLOWCOPY ?

Serve a produrre una copia separata e mutabile di una lista (in modo da
non alterarela lista originale)

In realta` in questa seconda versione si poteva omettere.

Per ottimizzare il programma si puo` anche calcolare tutte le combinazioni
di n-k+1 fuori del ciclo for sulla i e dentro il ciclo estrarre il subset
di queste il cui elemento massimo non supera n-i. Si risparmiano un po
di chiamate ricorsive alla funzione in oggetto.

[priamo]

Ecco l'analogo programma scritto in python (http://www.python.org).
Attenzione: l'indentazione è fondamentale per il suo funzionamento.

-------------------------CUT HERE---------------------------------

def combinazioni(n,k):


if (n<k or k<0 or n<0):
return []
elif k==0:
return [[]]
elif n==k:
return [range(1,n+1)]

comb=[]
for i in range(1,n-k+2):
smallercombs=combinazioni(n-i,k-1)
if smallercombs <> []:
l=len(smallercombs[0])
else:
l=-1

for tmp in smallercombs:
if tmp <> []:
for x in range(l):
tmp[x]=tmp[x]+i

tmpresult=[i]+tmp
comb=comb+[tmpresult]

return comb



print combinazioni(6,4)

[Genetic Prime]

Post by El Gioppinho
Vorrei scrivere un programma che calcoli tutte le combinazioni semplici
possibili in un insieme di n numeri, presi k alla volta senza ripetizioni.
n!
---------
k! (n-k)!

Usare gooogleeee ogni tanto... ;-)
Post del 28 Dic 2004 14:37, codice in Visual Basic ed altro...

http://groups.google.it/group/it.scienza.matematica/browse_frm/thread/d09a5289c70f3107/5a307ad1b236c5de?tvc=1&q=gprime+combinazioni&hl=it#5a307ad1b236c5
de