Programma che scrive tutte le combinazioni semplici
se ho 10 numeri come faccio a scrivere un programma in c, c++ che mi scriva tutte le combinazioni semplici (cioè tutte le combinazioni che differiscono tra loro per la natura degli oggetti, ma non per l'ordine degli stessi) a gruppi di 3?
Risposte
Considerato le migliaia, o milioni di combinazioni che andrai a generare, io appoggerei le soluzioni in un file testo, cosi' sara' facilmente consultabile.
Ci metterai una cifra di tempo per fare tutta quella roba che dici di voler fare comunque un algoritmo molto semplice è questo.... l'ho fatto in Java!
Non leggere tutto il resto quarda solo il metodo prova, tutto il resto è per farti fare una prova veloce e farti vedere che funziona! Il metodo è ovviamente ricorsivo!
import java.util.Arrays;
public class Main {
private static char[] combo = "qwertyuiopasdfghjklzxcvbnm".toCharArray();
private static char[] combinazioni = new char[3];
private static int count = 0;
public static void main(String args[]){
prova();
msg("Stampate "+count+" combinazioni");
}
private static void msg(String msg){
System.out.println(msg);
}
private static void prova(){prova(0);}
private static void prova(int j){
for(int i = 0; i<combo.length; i++){
combinazioni[j] = combo[i];
if(j < combinazioni.length - 1)prova(j + 1);
else {
System.out.println(Arrays.toString(combinazioni));
count++;
}
}
}
}
Non leggere tutto il resto quarda solo il metodo prova, tutto il resto è per farti fare una prova veloce e farti vedere che funziona! Il metodo è ovviamente ricorsivo!
A proposito di questo argomento, praticamente identito tranne che per n=8, e il programma centrale fornito nella prima risposta data sono un po' insicura, non applicandomi da praticamente due anni, sul "contorno" del programma, non ricordo esattamente il processo da seguire ma ho sempre lavorato con html, non con java, quindi non riesco a fare uso dell'ultimo programma postato...potreste aiutarmi?
html è un linguaggio di markup e non è dotato delle funzionalità necessarie per scrivere un programma di questo tipo. È necessario fare ricorso a linguaggio client-side come javascript o a linguaggi server-side come php.
L'idea generale è uguale in praticamente ogni linguaggio di programmazione che supporti qualche tipo di iterazione o ricorsione. Se devi generare tutte le combinazioni non ordinate di lunghezza \(k\) prese da un alfabeto di \(n\) simboli si sceglie prima il primo elemento tra i primi \(n-k+1\) simboli, poi si sceglie il secondo in modo che sia compreso tra il primo simbolo scelto e \(n-k+2\) e così via fino all'ultimo elemento. Più precisamente i simboli \(s_i\) di ogni successione generata dall'algoritmo deve rispettare le seguenti condizioni (i simboli sono indicati con i numeri naturali da 1 a n per comodità):
\( 1 \le s_1 < n - k + 1, \; s_{i-1} \le s_i \le n - k + i \; \; \forall i \in \{2, 3 \dots, k \}. \)
Queste combinazioni vengono generate in ordine lessicografico crescente. Il seguente è un programma in javascript che genera tutte le combinazioni di 3 numeri da 1 a 8:
Nota che sono tutt'altro che un'esperto di javascript per cui non è probabilmente migliorabile.
L'idea generale è uguale in praticamente ogni linguaggio di programmazione che supporti qualche tipo di iterazione o ricorsione. Se devi generare tutte le combinazioni non ordinate di lunghezza \(k\) prese da un alfabeto di \(n\) simboli si sceglie prima il primo elemento tra i primi \(n-k+1\) simboli, poi si sceglie il secondo in modo che sia compreso tra il primo simbolo scelto e \(n-k+2\) e così via fino all'ultimo elemento. Più precisamente i simboli \(s_i\) di ogni successione generata dall'algoritmo deve rispettare le seguenti condizioni (i simboli sono indicati con i numeri naturali da 1 a n per comodità):
\( 1 \le s_1 < n - k + 1, \; s_{i-1} \le s_i \le n - k + i \; \; \forall i \in \{2, 3 \dots, k \}. \)
Queste combinazioni vengono generate in ordine lessicografico crescente. Il seguente è un programma in javascript che genera tutte le combinazioni di 3 numeri da 1 a 8:
<html>
<head>
<script type="text/javascript">
function combination(letters, k) {
combinationRic(letters, "", 0, k);
}
function combinationRic(letters, comb, m, k) {
if (k == 0) {
document.writeln(comb + '<br />');
} else {
for (var i=m; i < letters.length-k; ++i) {
combinationRic(letters, comb+letters[i]+' ', i+1, k-1);
}
}
}
</script>
</head>
<body>
<script type="text/javascript">
combination([1,2,3,4,5,6,7,8], 3);
</script>
</body>
</html>
Nota che sono tutt'altro che un'esperto di javascript per cui non è probabilmente migliorabile.
"apatriarca":
<html> <head> <script type="text/javascript"> function combination(letters, k) { combinationRic(letters, "", 0, k); } function combinationRic(letters, comb, m, k) { if (k == 0) { document.writeln(comb + '<br />'); } else { for (var i=m; i < letters.length-k; ++i) { combinationRic(letters, comb+letters[i]+' ', i+1, k-1); } } } </script> </head> <body> <script type="text/javascript"> combination([1,2,3,4,5,6,7,8], 3); </script> </body> </html>
Quindi se io desiderassi modificare questo programma da n che va da 1 a 8 a n da A ad H mi basterebbe all'inizio dove c'è
combinationRic(letters, "", 0, k);
mettere tra le virgolette le lettere separate da una virgola e alla fine in
combination([1,2,3,4,5,6,7,8], 3);
le 8 lettere al posto dei numeri?
Se ho detto delle gran cavolate me ne scuso!!
Devi semplicemente mettere al posto di
scrivere
Se poi ad esempio volessi le combinazioni di 4 lettere dovresti invece scrivere
combination([1,2,3,4,5,6,7,8], 3);
scrivere
combination("ABCDEFGH", 3);Se poi ad esempio volessi le combinazioni di 4 lettere dovresti invece scrivere
combination("ABCDEFGH", 4);
[OT in parte]
Ma qua si cerca di implementare quella che è una funzione iniettiva, e non tutti i sottoinsiemi di $k$ elementi da un insieme di $n$ elementi. Confondo sempre questi due problemi...
[/OT]
Ma qua si cerca di implementare quella che è una funzione iniettiva, e non tutti i sottoinsiemi di $k$ elementi da un insieme di $n$ elementi. Confondo sempre questi due problemi...
[/OT]
Non ho capito che intendi con il commento sulla funzione iniettiva*. Quelli che vengono trovati sono tutti i sottoinsiemi di \(k\) elementi di un insieme con \(n\) elementi.
* Ovviamente so che cos'è una funzione iniettiva e la mappa che manda il prodotto cartesiano degli insiemi dei possibili indici nei sottoinsiemi di \(k\) elementi dell'insieme dato è certamente iniettiva. Ma la mappa è anche invertibile (basta prendere gli indici di tutti gli elementi di un qualche sottoinsieme e riordinarli e si ottiene gli indici di partenza.
* Ovviamente so che cos'è una funzione iniettiva e la mappa che manda il prodotto cartesiano degli insiemi dei possibili indici nei sottoinsiemi di \(k\) elementi dell'insieme dato è certamente iniettiva. Ma la mappa è anche invertibile (basta prendere gli indici di tutti gli elementi di un qualche sottoinsieme e riordinarli e si ottiene gli indici di partenza.
Come mai per i numeri ci vogliono le virgole e per le lettere no?
Come ti ho detto, non sono un esperto di javascript, ho semplicemente sfogliato un tutorial per scoprire come si facevano funzioni e cicli e come si richiamava una funzione in modo che stampasse il risultato nella pagina web. La mia conoscenza del linguaggio è quindi molto limitata.
In ogni caso, posso usare "ABCDEFGH" al posto di ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] perché alcuni browser (non tutti a quanto ho appena letto su internet) permettono di usare le parentesi quadre per accedere ai caratteri della stringa come se fosse un array. Per cui, anche se sto usando un oggetto di tipo diverso, posso usare la stessa funzione perché hanno la stessa "interfaccia". Ma se vuoi imparare javascript ti consiglio di leggere qualche guida (se non sai programmare credo sia meglio partire da qualcosa di più completo che un semplice tutorial).
In ogni caso, posso usare "ABCDEFGH" al posto di ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] perché alcuni browser (non tutti a quanto ho appena letto su internet) permettono di usare le parentesi quadre per accedere ai caratteri della stringa come se fosse un array. Per cui, anche se sto usando un oggetto di tipo diverso, posso usare la stessa funzione perché hanno la stessa "interfaccia". Ma se vuoi imparare javascript ti consiglio di leggere qualche guida (se non sai programmare credo sia meglio partire da qualcosa di più completo che un semplice tutorial).
[OT]
perciò, scusa se insisto ma vorrei togliermi sto dubbio, noi siamo in quale delle due situazioni:
1. applicazione iniettiva $f: k -> n$ cioè disposizioni distinte di $k$ elementi da un isnieme di $n$ e rapprsentato da $D_k^n = (n!)/((n-k)!)$
2. insieme dei sottoinsieme di $N$ di cardinalità $k$, rappresentato da $C_k^n = ((n),(k))$
da quanto dici siamo nella 2. o sbaglio ancora?
[/OT]
"apatriarca":
Non ho capito che intendi con il commento sulla funzione iniettiva*. Quelli che vengono trovati sono tutti i sottoinsiemi di \(k\) elementi di un insieme con \(n\) elementi.
perciò, scusa se insisto ma vorrei togliermi sto dubbio, noi siamo in quale delle due situazioni:
1. applicazione iniettiva $f: k -> n$ cioè disposizioni distinte di $k$ elementi da un isnieme di $n$ e rapprsentato da $D_k^n = (n!)/((n-k)!)$
2. insieme dei sottoinsieme di $N$ di cardinalità $k$, rappresentato da $C_k^n = ((n),(k))$
da quanto dici siamo nella 2. o sbaglio ancora?
[/OT]
Siamo nel secondo caso perché l'ordine non ha importanza.
"Sara4ever13":
<html> <head> <script type="text/javascript"> function combination(letters, k) { combinationRic(letters, "", 0, k); } function combinationRic(letters, comb, m, k) { if (k == 0) { document.writeln(comb + '<br />'); } else { for (var i=m; i < letters.length-k; ++i) { combinationRic(letters, comb+letters[i]+' ', i+1, k-1); } } } </script> </head> <body> <script type="text/javascript"> combination([1,2,3,4,5,6,7,8], 3); </script> </body> </html>
"apatriarca":
Nota che sono tutt'altro che un'esperto di javascript per cui non è probabilmente migliorabile.
nemmeno io sono un esperto di javascript (non lo conosco nemmeno), ma l'algoritmo in se è sicuramente migliorabile... ma bisognerebbe introdurre altre condizioni ed una struttura dati di insieme (almeno nella versione in java). Se ne vale lo sforzo si può cercare di migliorarlo
"apatriarca":
Siamo nel secondo caso perché l'ordine non ha importanza.
ti ringrazio molto, ora ho chiarito finalmente sto dubbio
Il tuo programma non funziona ma ci sono riuscita! Lo posto nel caso possa servire a qualcuno!
<script>
var lettere= new Array("A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z")
function combi(a,M,j,k){
if(k==1)
for(var i=j;i<M;i++)
document.write(a,lettere[i],", ");
else
for (var i=j;i<M;i++)
combi(a+lettere[i],M,i+1,k-1)
}
combi(" ",8,0,3);
</script>
Usi internet explorer? Avevo in effetti scritto qualcosa sul fatto che in alcuni browser potesse non funzionare l'uso della stringa al posto degli array. Spero che non ti abbia dato troppi problemi.
Eh già! Comunque assolutamente ci ho solo girato un po' sopra ma è naturale che il concetto fosse giusto 
Il procedimento logico non è molto diverso =)
Il procedimento logico non è molto diverso =)
"Cheguevilla":
Per generalizzare il problema come proposto da Umby, non è conveniente ragionare in maniera iterativa, poichè sarebbe un suicidio.
Molto meglio affrontare un approccio ricorsivo.
Tuttavia, come già fatto notare, poichè si tratta semplicemente di "generare" numeri, il tempo necessario dipende quasi esclusivamente dal numero delle combinazioni che si ottengono.
Bada bene che la printf è una funzione esageratamente "lenta".
Se parli del superenalotto, siamo di poco sopra ai 620 milioni di combinazioni.
Toglimi una curiosità: una volta che sei riuscito a stamparle su schermo, cosa te ne fai?
Salve sono uno nuovo. Mi sono appena imbattuto in questa discussione e vorrei rispondere a questo post con il mio pensiero.
io penso che quando si parla di prestazioni normalmente è meglio non scegliere l'approccio ricorsivo bensì quello iterattivo e anche questo caso non mi sembra esente da questa considerazione. Oltrettutto in questo caso non mi sembra nemmeno così proibitivo ragionare in maniera iterattiva.
Ciao, sono "nuova" iscritta
Volevo sapere dove si usa il programma per generare combinazioni semplici?
Volevo sapere dove si usa il programma per generare combinazioni semplici?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo