Je veux une charge dans une liste la combinaison de n chiffre sans répétition, donnant à la saisie des éléments et du groupe. Par exemple, avec 4 éléments [1,2,3,4], j'ai pour:
for x1 := 1 to 2 do
for x2 := Succ(x1) to 3 do
for x3 := Succ(x2) to 4 do
begin
// x1, x2, x3 //
end
6 Réponses :
sauf si vous ne pouvez pas apporter des appels de fonction par certaines exigences, procédez comme suit:
select_n_from_list(int *selected, int n, int *list, int list_size):
if (n==0) {
// print all numbers from selected by traversing backward
// you can set the head to a special value or make the head location
// a static variable for lookup
}
for (int i=0; i<=list_size-n; i++) {
*selected = list[i];
select_n_from_list(selected+1, n-1, list+i+1, list_size-i-1);
}
}
la récursion est une bonne solution au problème, mais ce code est dans la mauvaise langue
lol, excusez-moi de ne pas connaître la langue souhaitée. Cela ressemble à Delphi, mais je préfère écrire dans Generic C pour s'assurer que c'est le bon code.
Suivre le lien que David a affiché et en cliquant autour de moi, m'a conduit à un article où ils monnaient au terme "la recherche du banquier", qui semble correspondre à votre modèle.
L'article fournit un exemple de solution en C ++, en utilisant la récursion:
Voici une solution plutôt amusante qui dépend de Bitsets. Comme il est limité, il est limité à des ensembles de taille non supérieurs à 32. Je ne pense pas que ce soit une limitation pratique car il y a un lot em> de sous-ensembles pour un ensemble de cardinalité supérieure à 32. la La sortie n'est pas dans l'ordre que vous voulez, mais cela serait suffisamment facile pour remédier si cela vous importe. P> {1,2}
{1,3}
{2,3}
{1,4}
{2,4}
{3,4}
Très bon, mais pour afficher uniquement l'ensemble de n élément avec le groupe M? Par exemple, avec le groupe = 2, Affichage uniquement: {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} Comme je peux l'ajuster? Merci beaucoup.
Merci beaucoup, cela résout le problème du mien. Merci encore. Il n'y a qu'un problème un peu, jusqu'à 20 éléments, il est ok, beaucoup rapide, mais avec 25 éléments de plus en jeu, c'est bien plus lentement :( est possible de résoudre ce problème, ne comprend pas ce qui prend beaucoup de temps. Merci encore .
Eh bien, si vous voulez tous les sous-ensembles, il est difficile d'aller beaucoup plus vite que la boucle de base ici. Il y a juste un nombre immense de sous-ensembles. Si vous ne voulez que sous-ensembles pour une certaine cardinalité, il devient plus traitable. Laisse-moi y penser.
@Marcello essayez mon autre réponse. Je pense que c'est exactement ce que vous voulez!
Il semble que vous recherchiez un algorithme rapide pour calculer toutes les combinaisons K. Le code Delphi suivant est une traduction directe du code C trouvé ici: générer Combinaisons . J'ai même corrigé un bogue dans ce code! {1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}
Merci, cette solution est plus rapide. Très très bon, merci encore :)
Il voit les sorties dans l'ordre que vous attendez. Bel algorithme.
Cela semble être une question qui se pose encore et encore quelques bits de code sont donner un coup de pied à ce sujet sur le problème. Un très bel algorithme dans certains codes a été écrit mais ce n'était pas strictement propre c et non portable sur Unix ou Linux ou tout Système POSIX, donc j'ai nettoyé et ajouté des messages d'avertissement, une utilisation et la Possibilité de fournir une taille de réglage et une taille SUB_SET sur la ligne de commande. Aussi peigne [] a été transmis à un pointeur plus général sur un éventail d'entiers et de calloc à zéro de la mémoire nécessaire à la taille de la définition que vous souhaitez.
Ce qui suit est ISO CEI 9899: 1999 C Nettoyer: P>
$ /usr/bin/time -p ./combinations 30 22 | wc -l real 18.62 user 17.76 sys 0.83 5852925
Cette question est étiquetée delphi , et il n'y a aucune mention de C que ce soit dans cette question. Votre réponse est comme poster "Si, señor" quand quelqu'un demande "Comment dites-vous" oui, monsieur "en chinois?". :-) (et nous n'utilisons pas de signatures dans des questions ou des réponses ici; vous avez un profil utilisateur où vous pouvez inclure des éléments comme votre adresse e-mail si vous voulez le faire, mais ne le faites pas dans vos messages. Le < un href = "http://stackvoerflow.com/faq" rel = "NOFOollow Noreferrer"> FAQ mentionne ceci, au cas où vous n'êtes pas sûr. Les questions et les réponses sont également automatiquement datées et horodatées, donc vous pas besoin d'ajouter ceux non plus.)
J'ai créé ce script ici et a travaillé très bien:
p>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<label for="">
<input type="text" id="fieldArray">
<button id="search">Search</button>
<br><small>Info the elements. Ex: "a,b,c"</small>
</label>
<hr>
<ul id="list"></ul>
Je pense que vous avez manqué [2,3], [2,4], [3,4].
Le nom de l'ensemble que vous souhaitez est appelé «les permutations» d'un ensemble ou d'un chiffre. Découvrez cet article Wikipedia: en.wikipedia.org/wiki/permutation
@Andreasrejbrand 'annidate' = imbriqué
@DWB Non, les permutations ont le même nombre d'éléments que l'ensemble d'origine.
Oui désolé, je l'oublie :( il suffit de distraire.
Cela a-t-il de l'aide:
L'exemple de boucle que vous avez fourni uniquement des œuvres avec des valeurs définies incrémentielles qui n'ont pas de lacunes au milieu. Est-ce votre cas?
@David, K-permutations peut avoir moins d'éléments. DWB pensait probablement que Marcello voulait calculer toutes les K-permutations de K ∈ {1..n}, lorsqu'il veut vraiment les combinaisons K pour la même gamme.