Regroupement d'objets 3 par 3

Bonjour,

J’ai une liste d’objet dans la colonne A et je voudrais connaitre toutes les possibilités de les grouper 3 par 3, si nécessaire avec des objets laissés de côté. Pour 6 objets, j’attendrais donc le résultat suivant (du moins il me semble que c’est le résultat qu’on devrait obtenir) :

Objet 1 – Objet 2 – Objet 3 / Objet 4 – Objet 5 – Objet 6

Objet 1 – Objet 2 – Objet 4 / Objet 3 – Objet 5 – Objet 6

Objet 1 – Objet 2 – Objet 5 / Objet 3 – Objet 4 – Objet 6

Objet 1 – Objet 2 – Objet 6 / Objet 3 – Objet 4 – Objet 5

Objet 1 – Objet 3 – Objet 4 / Objet 2 – Objet 5 – Objet 6

Objet 1 – Objet 3 – Objet 5 / Objet 2 – Objet 4 – Objet 6

Objet 1 – Objet 3 – Objet 6 / Objet 2 – Objet 4 – Objet 5

Objet 1 – Objet 4 – Objet 5 / Objet 2 – Objet 3 – Objet 6

Objet 1 – Objet 4 – Objet 6 / Objet 2 – Objet 3 – Objet 5

Objet 1 – Objet 5 – Objet 6 / Objet 2 – Objet 3 – Objet 4

Objet 2 – Objet 3 – Objet 4 / Objet 1 – Objet 5 – Objet 6

Objet 2 – Objet 3 – Objet 5 / Objet 1 – Objet 4 – Objet 6

Objet 2 – Objet 3 – Objet 6 / Objet 1 – Objet 4 – Objet 5

Objet 2 – Objet 4 – Objet 5 / Objet 1 – Objet 3 – Objet 6

Objet 2 – Objet 4 – Objet 6 / Objet 1 – Objet 3 – Objet 5

Objet 2 – Objet 5 – Objet 6 / Objet 1 – Objet 3 – Objet 4

Objet 3 – Objet 4 – Objet 5 / Objet 1 – Objet 2 – Objet 6

Objet 3 – Objet 4 – Objet 6 / Objet 1 – Objet 2 – Objet 5

Objet 3 – Objet 5 – Objet 6 / Objet 1 – Objet 2 – Objet 4

Ca se complique s’il y a par exemple 10 objets. Une partie du résultat attendu ressemblerait à ça :

Objet 1 – Objet 2 – Objet 3 / Objet 4 – Objet 5 – Objet 6 / Objet 7 – Objet 8 – Objet 9 / Objet 10

…..

Objet 1 – Objet 7 – Objet 9 / Objet 3 – Objet 5 – Objet 10 / Objet 2 – Objet 4 – Objet 8 / Objet 6

…..

Objet 8 – Objet 9 – Objet 10 / Objet 5 – Objet 6 – Objet 7 / Objet 2 – Objet 3 – Objet 4 / Objet 1

…..

Mon but serait de pouvoir avoir entre 4 et 48 objets si possibles au départ. Ce serait évidemment le top.

Si cela est impossible, on pourrait soit partir dans la direction d’avoir moins d’objets au départ (par exemple se contenter d’un tel regroupement pour 15 objets seulement) ou décider de n’avoir que des multiples de 3 au départ. Pour ces deux dernières solutions, les objets surnuméraires seraient tout simplement éliminés au préalable par tirage au sort (mais je m’occupe de cette partie-là si nécessaire).

A titre d’information, ma liste d’objets est en colonne N et le résultat devrait être placé dans les colonnes suivantes, si possible avec chaque objet dans une colonne différente. Toutes ces colonnes ont des titres.

Cordialement.

36demo.xlsm (9.77 Ko)

Bonjour Yvouille

s'agit-il d'un vrai problème ou d'un bel exercice ?

en tout cas c'est possible avec un bel algo récursif (comme ceux que l'on faisait à l'école des informaticiens)

il s'agit de Permuter toutes les combinaisons possibles... mais j'ai déjà tenté quelques algo récursifs et Excel (malheureusement) fini par se décourager avant la fin !

cependant un "récursif" peut toujours se (re)tourner pour devenir "itératif" (même si en général on fait plutôt l'inverse) mais j'ai peur que la "tâche" soit longue (déjà avec 6 objets - donc à 10 tu imagines ?)

Merci pour ta réponse.

Il s'agit d'un vrai problème

Donc même si avec 9 ou 12 objets c'était possible, ce serait déjà bien.

(re)

Yvouille a écrit :

Il s'agit d'un vrai problème

Alors je vais tenter de "retrouver" une version itérative de ce classique problème, ce week-end... je reviens vers toi lundi ou mardi...

PS/ de toute façon... même s'il navait pas été un vrai problème je crois que je me serais laisser tenter quand même...

Encore une fois merci de t'intéresser à ce problème. Je suis impatient de connaitre le résultat de tes recherches

Bonjour Yvouille, bonjour Andrea...

je me suis cassé la tête dessus plus d'une heure cet après midi, en cherchant une manière de faire, mais déjà sur le papier, j'ai pas réussit a trouvé de fonction (récursive ou pas) pour faire le travail demandé....

je suis curieux aussi de voir la solution de Andrea, il est vrai je ne n'ais jamais fait ce genre d'exercice (pas d’école d'info non plus...)

on va donc patienté un peu

a+

fred

Bonjour (tous)

Mon alerte email vient de me signaler vos messages en particulier

fred2406 a écrit :

je me suis cassé la tête dessus plus d'une heure cet après midi, en cherchant une manière de faire, mais déjà sur le papier, j'ai pas réussit a trouvé de fonction (récursive ou pas) pour faire le travail demandé.... je suis curieux aussi de voir la solution de Andrea, il est vrai je ne n'ais jamais fait ce genre d'exercice (pas d’école d'info non plus...)

moi non plus j'ai n'est pas suivi de cours d'info ... mais ce genre de problème reste un classique et lors de mon apprentissage autodidacte... j'ai souvent été confronté à des problèmes "de ce genre là"

par contre (pardon Yvouille) je n'ai pas eu le loisir de regarder "à la solution"

mais j'ai promis... alors à la semaine prochaine... pour l'instant je suis un peu (beaucoup) surbooké...

bonjour Yvouille

Mais avec 48 objets vous n’aurez pas assez de colonnes sur la feuille ?!

Bonjour Yvouille, tous...

J'ai enfin retrouvé un algo récursif qui fait cela "dans les règles"... je suis en train de l'adapter à notre cher Excel !

Normalement un algo récursif est plus rapide, cependant comme je le disais précédemment Excel à tendance à lâcher prise dans la gestion de sa pile d'appels de fonctions...

Par contre mon pauvre Yvouille, le temps de traitement risque d'être long, et de plus en plus long au fur et à mesure que tu augmentes le nombre d'objets... approximativement 20 secondes pour 6 permutations de 12 objets

bonsoir

Yvouille a écrit :

J’ai une liste d’objet dans la colonne A et je voudrais connaitre toutes les possibilités de les grouper 3 par 3

Approximativement (1,40 secondes) pour 12 objets sans doublons

Cordialement

Bonjour,

une proposition (loin des performances promises par AMIR 1,4 secondes pour 12 objets)

1 min 20 secondes pour 11 objets (+/- 40 millions de possibilités) sans l'affichage,

objets à permuter à mettre en ligne 1 et lancer la macro aargh

Dim sol
Sub permute(n, ByRef a)
    If n = 1 Then
        sol = sol + 1
        Cells(sol, 1).Resize(, UBound(a) + 1) = a
    Else
        For i = 0 To n - 1
            permute n - 1, a
            If n Mod 2 = 0 Then
                w = a(i): a(i) = a(n - 1): a(n - 1) = w
            Else
                w = a(0): a(0) = a(n - 1): a(n - 1) = w
            End If
        Next
    End If
End Sub

Sub aargh()
    Dim a
    t = Timer
    sol = 1
    n = Cells(1, Columns.Count).End(xlToLeft).Column
    ReDim a(0 To n - 1)
    For i = 1 To n
        a(i - 1) = Cells(1, i)
    Next i
    permute n, a
    MsgBox Timer - t
End Sub

Bonjour à tous,

Je suis désolé de ne plus être intervenu sur mon propre fil, mais je n’ai pas reçu d’alerte m’indiquant qu’il y avait de nouveaux messages. Et comme Andrea m’avait dit qu’il allait regarder ça à tête reposée, je ne me suis pas trop inquiété à ce problème jusqu’à ce soir.

@ Andrea

andrea73 a écrit :

Par contre mon pauvre Yvouille, le temps de traitement risque d'être long, et de plus en plus long au fur et à mesure que tu augmentes le nombre d'objets... approximativement 20 secondes pour 6 permutations de 12 objets

J’ai compris que tu avais commencé à faire des essais chez toi, mais que tu ne voulais pas encore me fournir de première macro pour l’instant ? Si non, il me semble qu’il manque à ton message un fichier exemple ou une macro !! Au sujet du fait que ça risque d’être long, je pense que ce ne serait pas un gros problème si l’on pouvait par exemple traiter 18 objets en moins de 2 à 5 minutes. Et encore …..

@Amir

AMIR a écrit :

Approximativement (1,40 secondes) pour 12 objets sans doublons

As-tu une solution que tu pourrais nous montrer ?

@h2so4

Ta solution semble déjà une exellente piste. Mais pour moi le trio Objet 1 – Objet 2 – Objet 3 est le même que le trio Objet 1 – Objet 3 – Objet 2, que le trio Objet 2 – Objet 1 – Objet 3, que le trio Objet 2 – Objet 3 – Objet 1, que le trio Objet 3 – Objet 2 – Objet 1 ou que le trio Objet 3 – Objet 1 – Objet 2. Ta macro trouve donc 720 possibilités pour 6 objets alors que j’avais indiqué dans mon énoncé qu’il me fallait dans un tel cas – si je ne fais erreur - 19 résultats. Il y aurait bien entendu la possibilité de supprimer par la suite les résultats inutiles, mais n’y a-t-il pas quelque chose à gagner, du point de vue du temps de traitement, de ce côté-là ?

Amicalement.

bonsoir

j espere que j ai bien compris ton probleme:

18demov1.xlsm (22.77 Ko)

Salut Amir,

Alors non, le résultat escompté n'est pas celui que tu me fournis. Relis bien mon énoncé dans mon tout premier message. Je dis : "c’est le résultat qu’on devrait obtenir" et j'ai inscrit 19 lignes comportant les trios attendus.

Ta macro n'inscrit que les titres de colonnes, sans les résultats en-dessous (quelques milliers de lignes selon le nombre d'objets au départ).

Amicalement.

bonjour,

En réalité ton problème est pollué par une erreur de départ : la liste que tu as établie.

Si j'ai bien compris, il s'agit simplement de faire une liste de combinatoire (3/6 pour reprendre ta liste...)

En réalité la combinatoire comporte 20 éléments après tu les associes comme tu veux... et ton association n'est pas fausse mais elle est incomplète :

La vingtième ligne (manquante) est donc celle ci :

Objet 4 – Objet 5 – Objet 6 / Objet 1 – Objet 2 – Objet 3

Evidemment ce regroupement est le même que ton premier, mais pour moi ce sont tous des doublons / miroirs de la liste inverse...

Ton 2ème avec ton dernier

Ton 3ème avec l'antépénultième, etc...

Objet 1 – Objet 2 – Objet 3 / Objet 4 – Objet 5 – Objet 6

Objet 1 – Objet 2 – Objet 4 / Objet 3 – Objet 5 – Objet 6

Objet 1 – Objet 2 – Objet 5 / Objet 3 – Objet 4 – Objet 6

Objet 1 – Objet 2 – Objet 6 / Objet 3 – Objet 4 – Objet 5

Objet 1 – Objet 3 – Objet 4 / Objet 2 – Objet 5 – Objet 6

Objet 1 – Objet 3 – Objet 5 / Objet 2 – Objet 4 – Objet 6

Objet 1 – Objet 3 – Objet 6 / Objet 2 – Objet 4 – Objet 5

Objet 1 – Objet 4 – Objet 5 / Objet 2 – Objet 3 – Objet 6

Objet 1 – Objet 4 – Objet 6 / Objet 2 – Objet 3 – Objet 5

Objet 1 – Objet 5 – Objet 6 / Objet 2 – Objet 3 – Objet 4

Objet 2 – Objet 3 – Objet 4 / Objet 1 – Objet 5 – Objet 6

Objet 2 – Objet 3 – Objet 5 / Objet 1 – Objet 4 – Objet 6

Objet 2 – Objet 3 – Objet 6 / Objet 1 – Objet 4 – Objet 5

Objet 2 – Objet 4 – Objet 5 / Objet 1 – Objet 3 – Objet 6

Objet 2 – Objet 4 – Objet 6 / Objet 1 – Objet 3 – Objet 5

Objet 2 – Objet 5 – Objet 6 / Objet 1 – Objet 3 – Objet 4

Objet 3 – Objet 4 – Objet 5 / Objet 1 – Objet 2 – Objet 6

Objet 3 – Objet 4 – Objet 6 / Objet 1 – Objet 2 – Objet 5

Objet 3 – Objet 5 – Objet 6 / Objet 1 – Objet 2 – Objet 4

En conclusion le problème se résume donc à établir la liste combinatoire de n éléments, après les regroupements... ton approche me semble pour le moins, un peu biaisée !

A+

Salut Galopin,

Je te remercie pour tes remarques fort pertinentes. Comme il me semblait que ma liste de départ pouvait être erronée, j’avais bien indiqué que je ne la garantissais pas

Mais en fait, il ne manque pas la 20ème combinaison, c’est simplement que je m’étais rendu compte qu’elle faisait doublon avec la première et je l’avais éliminée.

Tu me fais remarquer maintenant que la deuxième combinaison est la même que la 19èmer, la 3ème la même que la 18ème, etc. et tu as tout à fait raison ; je n’avais pas poussé la réflexion assez loin.

La liste que je souhaiterais obtenir avec 6 objets est donc :

Objet 1 – Objet 2 – Objet 3 / Objet 4 – Objet 5 – Objet 6

Objet 1 – Objet 2 – Objet 4 / Objet 3 – Objet 5 – Objet 6

Objet 1 – Objet 2 – Objet 5 / Objet 3 – Objet 4 – Objet 6

Objet 1 – Objet 2 – Objet 6 / Objet 3 – Objet 4 – Objet 5

Objet 1 – Objet 3 – Objet 4 / Objet 2 – Objet 5 – Objet 6

Objet 1 – Objet 3 – Objet 5 / Objet 2 – Objet 4 – Objet 6

Objet 1 – Objet 3 – Objet 6 / Objet 2 – Objet 4 – Objet 5

Objet 1 – Objet 4 – Objet 5 / Objet 2 – Objet 3 – Objet 6

Objet 1 – Objet 4 – Objet 6 / Objet 2 – Objet 3 – Objet 5

Objet 1 – Objet 5 – Objet 6 / Objet 2 – Objet 3 – Objet 4

galopin01 a écrit :

En conclusion le problème se résume donc à établir la liste combinatoire de n éléments, après les regroupements.

Effectivement, mais comment y arriver avec 9, 12, 15 objets par exemple ?

Chaleureusement.

Bonjour Yvouille,

je n'avais effectivement pas bien lu l'énoncé.

voici une nouvelle proposition, objets à regrouper à mettre en ligne 1, moins de 2 secondes pour 12 objets

Dim a$(1 To 50), v&(1 To 50), u&(1 To 50), sol&
Sub permute(n&, Optional ind& = 1, Optional niveau& = 1)
    If niveau = 1 Then
        limi = 1
    ElseIf niveau Mod 3 = 1 Then
        limi = niveau + 2
        If limi > n Then limi = n
    Else
        limi = n
    End If
    For i& = ind To limi
        If u(i) = 0 Then
            u(i) = 1
            v(niveau) = i
            If niveau = n Then
                sol = sol + 1
                For j& = 1 To n
                    Cells(sol, j) = a(v(j))
                Next j
            Else
                If niveau Mod 3 = 0 Then
                    permute n, niveau - 2, niveau + 1
                Else
                    permute n, i + 1, niveau + 1
                End If
            End If
            u(i) = 0
        End If
    Next i
End Sub
Sub aargh()
    t = Timer
    Application.ScreenUpdating = False
    n& = Cells(1, Columns.Count).End(xlToLeft).Column
    sol = 1
    For i& = 1 To n
        a(i) = Cells(1, i)
    Next i
    permute n
    MsgBox sol - 1 & " permutations en " & Timer - t
    Application.ScreenUpdating = True
End Sub

Bonjour.

Fait à la va vite :

Sub Lewan()
Dim Liste(1 To 6) As String
Dim i As Integer
For i = 1 To 6 Step 1
Liste(i) = Cells(1, i) 
Next i
Dim k As Integer
k = 4
Dim j As Integer
For i = 2 To 6 Step 1
    For j = i + 1 To 6 Step 1
        Cells(k, 1).Value = Liste(1) & Liste(i) & Liste(j)
        k = k + 1
    Next j
Next i
    k = 4
Do Until IsEmpty(Cells(k, 1))
    For i = 1 To 6
        If InStr(Cells(k, 1).Value, Liste(i)) = 0 Then
            Cells(k, 2).Value = Cells(k, 2).Value & Liste(i)
        End If
    Next i
    k = k + 1
Loop
End Sub

Reste un "-" de trop, mais c'est juste de la mise en forme après

J'risque de me pencher sur un nombre d'objets variable si l'ennui me prend dans l'après midi

123yi3.xlsm (13.97 Ko)

Re...

Bon je t'ai fait une macro qui combine 3 sur 49 YAPUKA appuyer sur le bouton

18424 combinaison triées et tout et tout (environ 20" chez moi)

Après tu peux les arranger comme tu veux : Tu prends la deuxième moitié et tu la déplaces en colonne DEF par exemple...

Bon en fait j'ai fait 3/49 mais tu peux faire 3 sur 6, sur 9, sur 12... YAKA changer la valeur de N (Ligne 6)

Hum, pour faire bonne mesure j'ai fait une boucle de 500 000... En principe ça te sort les 18424 combinaisons à tous les coups...

S'il t'en manque 1 ou 2 c'est que tu n'as pas de chance : YAPUKA recommencer !

A+

13combinatoire.xlsm (22.47 Ko)

Bonjour tout le monde,

J’ai tout à coup beaucoup de solutions, c’est génial !

@ Elhevan

Effectivement qu’avec 6 objets la solution n’est pas trop compliquée. C’est bien dès que le nombre d’objets augmente que les choses se compliquent. D’autres membres m’ont proposé des solutions déjà très performantes ; à toi de voir si tu penses pouvoir arriver à quelque chose de mieux.

@ Galopin

J’avoue franchement que je n’ai pas très bien compris ta solution. Où inscris-tu les objets à disposition ? Déjà bloqué à ce niveau, j’ai eu un peu de peine à tester plus loin !

@ h2so4

On s’approche du pur bonheur ! J’ai une machine un peu moins performante que la tienne et il me faut 5 secondes pour 12 objets et 2 minutes 30 pour 15 objets (79201 permutations).

C’est déjà génial car j’ai rarement plus de 15 objets à traiter et – le cas échéant – je vais probablement partir dans la direction de traiter 2 x 9 objets séparément par exemple ou 3 x 9 objets + 1 x 6 pour 33 objets, etc.

A titre d’information, as-tu tenté de lancer ta macro avec 18 objets ? Chez moi j’ai stoppé la macro après un peu plus de 5 minutes. Je te pose la question afin de savoir si la puissance de l’ordinateur pourrait faire une bonne différence avec un tel nombre d’objets.

Bonnes salutations à vous tous.

EDIT DE 16 HEURES

@ h2so4

J’ai remarqué que si je lance la macro avec 13 objets par exemple, dans la dernière colonne, je n’ai pas tous les objets qui y apparaissent, alors que logiquement il devrait y avoir le même nombre d’occurrences dans cette colonne pour tous les objets. Après avoir formé 4 x 3 trios, il devrait régulièrement rester un dernier objet seul. Ce n’est pas très important car je vais probablement lancer ma macro qu’avec des multiples de 3 (dans le cas présenté ci-dessus avec 13 objets, j’en choisirais par exemple 12 au hasard), mais c’est juste pour avoir ton avis.

Rechercher des sujets similaires à "regroupement objets"