Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C# / VB.NET - [C#] combinazioni tutte differenti
Forum - C# / VB.NET - [C#] combinazioni tutte differenti

Avatar
kaprone (Normal User)
Newbie


Messaggi: 7
Iscritto: 10/09/2010

Segnala al moderatore
Postato alle 3:17
Domenica, 27/03/2011
salve,

da un arraylist dovrei tirare fuori tutte le combinazioni possibili senza ripetizioni, le combinazioni devono essere di una lunghezza di 4 valori.
ipotizzando di avere una lista da 1 a 9


arraylist = 1, 2, 3, 4, 5, 6, 7, 8, 9

arraycomb[0] = 1, 2, 3, 4;
arraycomb[1] = 1, 2, 3, 5;
e cosi via..

come iterare sulla lista per estrarre i valori a 4 a 4 senza ripetizioni?
come dichiarare l'array delle combinazioni non sapendo di preciso quanti indici avra?

spero possiate aiutarmi a risolvere questa cosa, ringrazio anticipatamente.

---------------------------------------------------------------------------

niente da fare non riesco a rispondere, cmq al momento ho risolto facendo una cosa del genere:
Codice sorgente - presumibilmente C++
  1. void addComb(int a, int b, int c, int d)
  2.     {
  3.         ar_comb.Add(a);
  4.         ar_comb.Add(b);
  5.         ar_comb.Add(c);
  6.         ar_comb.Add(d);
  7.     }
  8.  
  9.     void getComb(object sender, EventArgs ev)
  10.     {
  11.         for (int a = 1; a <= ar.Count; a++)
  12.             for (int b = a + 1; b <= ar.Count; b++)
  13.                 for (int c = b + 1; c <= ar.Count; c++)
  14.                     for (int d = c + 1; d <= ar.Count; d++)
  15.                         addComb(a, b, c, d);
  16.     }


però ci dovrebbe essere un modo di farlo senza troppi for, perchè se le combinazioni invece di 4 elementi devono essere più grandi? o peggio ancora se si lascia all'utente la scelta di quanti ne deve avere che si fa un mega overload di cicli for?

Ultima modifica effettuata da kaprone il 28/03/2011 alle 11:15
PM
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Up
3
Down
V
Segnala al moderatore
Postato alle 12:05
Domenica, 27/03/2011
Non ti serve dichiarare un array per le combinazioni. Anzi, non ha senso: se stai già usando un ArrayList per le cifre, usane uno anche per le combinazioni.
Per evitare ripetizioni basta controllare se la sequenza estratta esiste già in arraycomb. Se esiste, ripeti l'estrazione, altrimenti vai avanti.

PM
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Up
2
Down
V
Segnala al moderatore
Postato alle 19:12
Lunedì, 28/03/2011
Considera di provare questa generalizzazione. Vale per ogni lista di numeri (non necessariamente in sequenza) e per ogni n. calculateCombinations restituisce però luna lista di array di indici e non di elementi.
Codice sorgente - presumibilmente C++
  1. namespace proof
  2. {
  3.     class Program
  4.     {
  5.         static List<Int32> numberList = new List<Int32>();
  6.  
  7.         static void scale(Int32[] combination, Int32 index)
  8.         {
  9.             if (index < 0)
  10.                 return;
  11.             combination[index]++;
  12.             if ( (index > 0) && (combination[index] >= numberList.Count - index) )
  13.             {
  14.                 scale(combination, index - 1);
  15.                 combination[index] = combination[index - 1] + 1;
  16.             }
  17.         }
  18.  
  19.         static List<Int32[]> calculateCombinations(Int32 n)
  20.         {
  21.             Int32[] combination = Enumerable.Range(0, n).ToArray();
  22.             List<Int32[]> combinations = new List<Int32[]>();
  23.  
  24.             while (combination[0] <= numberList.Count - n)
  25.             {
  26.                 if (combination.All(x => x < numberList.Count))
  27.                     combinations.Add(combination.Clone() as Int32[]);
  28.                 scale(combination, n - 1);
  29.             }
  30.  
  31.             return combinations;
  32.         }
  33.  
  34.         static void Main(string[] args)
  35.         {
  36.             numberList.AddRange(new Int32[] { 3, 8, 10, 23, 12 });
  37.            
  38.             var clist = calculateCombinations(3);
  39.             foreach (Int32[] c in clist)
  40.                 Console.WriteLine(c.Aggregate("", (acc, cur) => acc + ' ' + numberList[cur]));
  41.  
  42.             Console.ReadKey();
  43.         }
  44.     }
  45. }

PM
Avatar
HeDo (Founder Member)
Guru^2


Messaggi: 2765
Iscritto: 21/09/2007

Up
1
Down
V
Segnala al moderatore
Postato alle 11:10
Domenica, 27/03/2011

fai un cross join e poi scarti tutte quelle combinazioni costituite dagli stessi numeri.

per array di 5 numeri, come in questo caso, l'eleganza del codice e la sua leggibilità sono preferiti all'efficienza... che poi se considerato l'overhead del clr ci mettiamo a ridere - HeDo - 28/03/11 19:59
PM
Avatar
gigisoft (Member)
Guru


Messaggi: 696
Iscritto: 11/10/2008

Up
1
Down
V
Segnala al moderatore
Postato alle 10:22
Lunedì, 28/03/2011
Ciao,
se ho capito bene tu hai un array:

arraylist = 1, 2, 3, 4, 5, 6, 7, 8, 9

di N elementi

allora fai così:

Codice sorgente - presumibilmente Delphi
  1. for (I1 = 0; I1 < N; I1++) {
  2.     for I2 = (I2 = (I1 + 1); I2 < N; I2++) {
  3.         for I3 = (I3 = (I2 + 1); I3 < N; I3++) {
  4.             for I4 = (I4 = (I3 + 1); I4 < N; I4++) {
  5.                 Comb[0] = arraylist[I1]
  6.                 Comb[1] = arraylist[I2]
  7.                 Comb[2] = arraylist[I3]
  8.                 Comb[3] = arraylist[I4]
  9.                 /*Stampa o memorizza la combinazione [b]Comb[/b] *
  10.             }
  11.         }
  12.     }
  13. }


di volta in volta ti troverai tutte le combinazioni di 4 su N elementi senza ripetizioni.

:ot: Pensa che e' il metodo che uso io, a mente, per risolvere i sudoku killer :rotfl: :ot:

Ciao. :k:

Luigi

Ultima modifica effettuata da gigisoft il 28/03/2011 alle 10:30
PM