Problème Algorithme combinatoire [Résolu]

[Neiflheim]

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

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

[Alexis.M]

Ben il suffit de faire exactement ce que tu as fait pour écrire la

[Neiflheim]

Euh oui mais là c'était un exemple

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#) !

[Alexis.M]

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.

[Neiflheim]

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