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.
- Messages
- 1'123
- Excel
- 2013 FR
- Inscrit
- 18/09/2015
- Emploi
- Développeur Bureautique Indépendant (Excel)
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.
- Messages
- 1'123
- Excel
- 2013 FR
- Inscrit
- 18/09/2015
- Emploi
- Développeur Bureautique Indépendant (Excel)
(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
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
- Messages
- 1'123
- Excel
- 2013 FR
- Inscrit
- 18/09/2015
- Emploi
- Développeur Bureautique Indépendant (Excel)
Bonjour (tous)
Mon alerte email vient de me signaler vos messages en particulier
moi non plus j'ai n'est pas suivi de cours d'infofred2406 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...)
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 ?!
- Messages
- 1'123
- Excel
- 2013 FR
- Inscrit
- 18/09/2015
- Emploi
- Développeur Bureautique Indépendant (Excel)
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...
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
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 …..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
@Amir
As-tu une solution que tu pourrais nous montrer ?AMIR a écrit :Approximativement (1,40 secondes) pour 12 objets sans doublons
@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.
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
Effectivement, mais comment y arriver avec 9, 12, 15 objets par exemple ?galopin01 a écrit :En conclusion le problème se résume donc à établir la liste combinatoire de n éléments, après les regroupements.
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
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+
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.