Discussions au sujet de NI LabVIEW

annuler
Affichage des résultats de 
Rechercher plutôt 
Vouliez-vous dire : 
Répondre

Générateur de combinaisons k parmis n

Résolu !
Accéder à la solution

Générateur de combinaisons k parmis n

Bonjour,

Ce que je souhaite faire:

Créer un générateur de combinaisons de k parmi n.

k et n doivent pouvoir être modifiés facilement

exemple 1:

k=2 et n=4

1 | 2

1 | 3

1 | 4

2 | 3

2 | 4

3 | 4

 

exemple 2:

k=3 et n=4

1 | 2 | 3

1 | 2 | 4

1 | 3 | 4

2 | 3 | 4

 

Voici des liens pour des articles sur le sujet:
https://www.dcode.fr/combinaisons (générateur disponible en haut de page)

http://villemin.gerard.free.fr/Denombre/CbinEnum.htm

https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size...

J'ai joint une image de ce que j'ai déjà réalisé.
Ma méthode fonctionne mais je ne peux pas modifier k facilement.

Je dois ajouter un boucle "for" pour pouvoir augmenter la valeur de k.

Savez vous comment régler mon problème ?
Avez-vous des pistes d'amélioration ?

Merci d'avance

0 Compliments
Message 1 sur 9
149 Visites

Re: Générateur de combinaisons k parmis n

Tu utilises un algorithme similaire à ce qui est décrit dans la section "Première approche simple" du deuxième lien. Cette approche est dédiée à une valeur spécifique de n (et pour n = 10 le code ressemblera à une pyramide aztèque Smiley très heureux) car on ne peut pas ajouter une boucle FOR de façon programmatique lorsque le vi roule.

 

Tu dois utiliser l'algorithme de la section "Algorithme", celle représentée par le diagramme avec les flèches rose et bleu. Cet algorithme est réalisable avec 2 boucles, je n'ai pas essayé mais ma première approche serait d'utiliser une boucle FOR externe (car on connait à priori le nombre d'itération "n") contenant une boucle WHILE utilisant les paramètres n et k pour déterminer les combinaisons possible.

 

Comme précisé dans le lien il est également possible d'utiliser l'approche récursive mais le concept est plus difficile à cerner (tu dois créer un sous-vi réentrant qui s'appelle lui-même jusqu'à ce qu'une condition d'arrêt prédéterminée soit réalisée).

 

Ben64

--------------------------------------------------
The best way to say thanks is to give kudos!
0 Compliments
Message 2 sur 9
92 Visites
Solution
Accepté par l'auteur du sujet SamuelGeiser
12-10-2018 01:32 PM

Re: Générateur de combinaisons k parmis n

Finalement j'ai trouvé ma solution.

J'ai programmé comme la section Algorithme du deuxième lien.
Mais avec beaucoup de valeurs générés, il faut les stockés et le programme ralenti.
J'essaie donc maintenant de l'optimiser pour qu'il sois plus rapide.

0 Compliments
Message 3 sur 9
88 Visites
Highlighted

Re: Générateur de combinaisons k parmis n

Bonsoir,

J'imagine que pour afficher quelque 20000 combinaison, il a fallu presque 15s,

le principe est celui du récursive VI comme ben64 a mentionné VI reentrant.

 

tu trouvera la méthode des boucles FOR en recursive VI sans boucle while.

 

Bonne soirée

 

 

 

Message 4 sur 9
72 Visites

Re: Générateur de combinaisons k parmis n

Salut,


J'ai essayé ton vi et j'arrive à un temps d'exécution d'environ 19 secondes pour k=6 et n=20.

Et avec ma méthode, j'arrive à un temps de 0.045 secondes. Smiley heureux
Je penses que la rapidité n'est pas comparable.

 

 

0 Compliments
Message 5 sur 9
35 Visites

Re: Générateur de combinaisons k parmis n

salut,

c’était le principe du fonctionnement de la recursive,

certes y a plein d'autre algorithmes, il faut choisir la meilleur.

 

J'ai amélioré un peu le mien du coup au lieu de 19 s j'en suis à 2s.

 

Pour ta méthode tu utilise quel principe et si tu peux m'en dire un peu plus, je te remercie.

0 Compliments
Message 6 sur 9
23 Visites

Re: Générateur de combinaisons k parmis n

As-tu consulté ce lien, dans la partie "Algorithme" ?
http://villemin.gerard.free.fr/Denombre/CbinEnum.htm

 

Ce qui a mon avis ralenti le plus le programme c'est de stocker les valeurs dans un tableau.
Lorsque le tableau deviens plus grand, cette opération prends plus de temps.

J'ai  deux parties à mon programme, une qui génére les combinaisons et les mets dans une fille d'attente.

Et une autre partie qui prends les données de cette file et le traites.


Je ne sais pas trop comment t'en dire plus car j'ai vraiment utilisé cette méthode.
Mais si tu as une question un peu plus précise sur un  ou plusieurs points, je pourrai te dire comment j'ai procédé.

0 Compliments
Message 7 sur 9
15 Visites

Re: Générateur de combinaisons k parmis n

salut,

Oui je l'ai consulté, évidemment le stockage et l'affichage ralenti beaucoup, tu verra dans le deuxième modèle que j'ai fait , se basant sur les DVR, réduit ce phénomène.

 

j'espere avoir repondu à ta question de départ.

bonne continuation Smiley heureux

 

 

 

0 Compliments
Message 8 sur 9
10 Visites

Re: Générateur de combinaisons k parmis n

Oui j'ai déjà consulté ton deuxième modèle.

 

Mais je trouve que la méthode que j'avais trouvé avant est quand même bien plus rapide.
Je vais rester sur celle là Smiley clignant de l'œil

 

Bonne continuation.

0 Compliments
Message 9 sur 9
6 Visites