Arrangement / Combinaison

Question

Bonjour à vous,

Déjà je tenais à signaler que je ne suis ni une mathématicienne, ni une informaticienne, je ne sais donc pas programmer et je n'ai donc pas votre langage technique (c'est pourquoi je ne savais pas quoi écrire dans la recherche).
Et là vous vous dites : "Éh merde, voilà un boulet" :-p

Mais je vais tout de même vous exposer mon problème, on ne sait jamais ^^

J'aimerais soit un logiciel en ligne, soit une formule (sous Excel ou OpenCalc) pour pouvoir me trouver des combinaisons.
Comme un exemple va être plus parlant en voici un :

Je dispose de 3 chiffres (1, 2, 3) et je veux faire une combinaison de 4 chiffres, je peux donc obtenir ce genre de combinaison :
1111
1112
1121
1211
2111
1113
2211
1231
...

Cependant comme dans cette combinaison il n'y a pas de "début" et de "fin" les combinaisons suivantes sont les "même" et font donc "doublon" (quadruplon pour le coup ^^).
1112 = 1121 = 1211 = 2111

1231 = 1123 = 3112 = 2311
qui est différent de :
3121 = 1312 = 2131 = 1213
...

Il faudrait donc dans les résultats de toutes les combinaisons, garder qu'une combinaison parmi les "même".

La finalité est toujours de faire une combinaison de 4 (ou 6) chiffres mais avec plus de chiffres (1, 2, 3, 4, 5, 6, 7...)

J'espère avoir été tout de même assez claire et je vous remercie d'avance pour votre aide. 

Configuration: Windows 7 / Firefox 8.0

ccm81 · Answer

bonjour

Pour le vocabulaire, ce sont des combinaisons avec répétition que tu cherches
et le nombre de combinaisons avec répétitions de p éléments choisis parmi m est 
Combin(m + p - 1, p)
un exemple
https://www.cjoint.com/?0KwhP64qNOn 

bonne suite

Kamijee · Answer

Je souhaitais aussi partager ce qu'on a put me répondre sur d'autre forum, si ça peut aider à m'aider ^^

Algorithme de Joe Sawada :
http://www.cis.uoguelph.ca/~sawada/papers/alph.pdf

Je ne sais pas si ça correspond à mon problème...
Ensuite je ne maitrise pas assez Excel pour traduire l'algo en VBA. Mais il ne fait qu'une dizaine de lignes, donc ca ne pose peut être pas problème à ceux qui maitrisent ce langage.

ccm81 · Answer

re 

je ne comprends pas bien ce que tu veux 
pour m = 3 et p = 4, par exemple 
la combinaison avec répétition 1132 figure bien parmi les 15 possibles, mais sous la forme 1123 
et comme tu as précisé 
Il faudrait donc dans les résultats de toutes les combinaisons, garder qu'une combinaison parmi les "même".  
1132 et 1123 sont deux arrangements différents mais de la même combinaison avec répétition

RQ. dans un arrangement l'ordre est pris en compte 1123 est différent de 1213, 
       dans une combinaison non et 1123 = 1213 

bonne suite

yoda · Answer

Bonjour,

J'ai ecrit une petite macro en VBA Excel capable de trouver toutes les combinaisons de 4 chiffres possibles en suivant les règles de non-repetition.

Sub cmb_4()

Dim tab_cmb(2000) As String, nbr_cmb As Integer, cnt_cmb As Integer
Dim str_cmb As String, txt_cmb As String, xst_cmb As Boolean
Dim i1 As Integer, i2 As Integer, i3 As Integer, i4 As Integer
Dim MAX_CAR As Integer

MAX_CAR = 9 'indiquer le nombre de chiffres (minimum 1, maximum 9)

nbr_cmb = 0
For i1 = 1 To MAX_CAR
    For i2 = 1 To MAX_CAR
        For i3 = 1 To MAX_CAR
            For i4 = 1 To MAX_CAR
                txt_cmb = Trim(Str(i1)) + Trim(Str(i2)) + Trim(Str(i3)) + Trim(Str(i4))
                xst_cmb = False
                For cnt_cmb = 1 To nbr_cmb
                    str_cmb = tab_cmb(cnt_cmb) + tab_cmb(cnt_cmb)
                    If InStr(str_cmb, txt_cmb) > 0 Then
                        xst_cmb = True
                        Exit For
                    End If
                Next cnt_cmb
                If Not xst_cmb Then
                    nbr_cmb = nbr_cmb + 1
                    tab_cmb(nbr_cmb) = txt_cmb
                End If
            Next i4
        Next i3
    Next i2
Next i1
MsgBox ("Nombre de combinaisons : " & nbr_cmb)
If nbr_cmb > 0 Then
For cnt_cmb = 1 To nbr_cmb
    Range("A" & cnt_cmb).Value = tab_cmb(cnt_cmb)
Next cnt_cmb
Range("A" & cnt_cmb).Value = "*FIN*"
End If

End Sub

ccm81 · Answer

bonjour yoda

dans mon exemple j'avais donné les combinaisons avec répétition
mais
si j'ai bien compris, Kamijee veut des arrangements avec répétition, mais en en ne gardant qu'un exemplaire de ceux qui sont invariants par permutation circulaire.
exemple pour m = 3 et p = 4, avec 1 , 1, 2 , 3 ça donnerait
1123 et on ne garde pas 3112, 2311, 1231
1213 et on ne garde pas 3121, 1312, 2131
etc ...
c'est un problème intéressant !

Arrangement / Combinaison

5 réponses

Discussions similaires

Newsletters