Problème Algorithme combinatoire

Version imprimable

09/02/2012, 14h12
Neiflheim

Problème Algorithme combinatoire

Bonjour à tous,

Je bloque un peu sur la résolution d'un algorithme combinatoire.

J'ai par exemple une colonne C1 qui contient n index
J'ai un seuil de m index défini au départ

J'aimerais avoir toutes les combinaisons de C1 par groupe de m index, sans doublons.

Bon je m'enfonce, je vais donner un exemple :cry:

C1(1 à 7 index)

Seuil : 3

Combinaisons possibles (retour chariot pour plus de lisibilité) :
123 123 125 126 127
134 135 136 137
145 146 147
156 157
167

234 235 236 237
245 246 247
256 257
267

etc jusqu'à 567

Merci de m'aiguiller sur la bonne piste ;)
09/02/2012, 14h18
Alexis.M

Ben il suffit de faire exactement ce que tu as fait pour écrire la
09/02/2012, 14h21
Neiflheim

Euh oui mais là c'était un exemple :mrgreen:

Quand je vais avoir 1000 index avec un seuils de 30, ça va pas être la même chose ;)

J'ai oublié de préciser que je programmais en .NET (VB ou C#) !

Avec un truc récursif du genre:

Code:

1
2
3
4
5
6
7
8
9
10
 
 
def build_sequence(n,m,curr_seq,sequences):
    if length(curr_seq) == m :
        sequences.append(curr_seq)
    else :
        last_val = last(curr_seq)
        for i = last_val+1 .. n :
             new_seq = curr_seq + i
             build_sequences(n,m,new_seq,sequences)

et si ce n'est pas possible tu mime les appels récursifs avec une pile.

Merci beaucoup tu m'as mis sur la bonne voie avec la boucle sur une procédure (je ne suis pas encore très familier avec la récursivité). Avec ta fonction j'avais un problème à partir de 10, j'ai donc modifié un peu le principe :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  Sub Main()
        Dim n As Integer = 148
        Dim m As Integer = 5
        For i = 1 To n
            BuildCombinaison(n, m, i)
        Next
    End Sub
 
 
    Private Sub BuildCombinaison(ByVal n As Integer, ByVal m As Integer, ByVal Current As String)
        If Current.Split("-").Length  = m Then
            Console.WriteLine(Current.ToString)
        Else
            Dim Chaine() As String = Current.Split("-")
            Dim Dernier As Integer = Chaine(Chaine.Length - 1)
            For i = Dernier + 1 To n
                Dim NouvelleSequence As String = Current & "-" & i
                BuildCombinaison(n, m, NouvelleSequence)
            Next
        End If
    End Sub