Y a-t-il une bibliothèque ou une fonction équivalente qui me donnera la prochaine combinaison d'un ensemble de valeurs telles que Next_permutation en fait pour moi?
6 Réponses :
googling pour C ++ "NEXT_COMBINATION" tourné Ce .
- recherche de "mi-" à l'envers jusqu'à ce que vous trouviez un élément plus petit que * (fin - 1). C'est l'élément Nous devrions augmenter. Appelez ceci "Head_Pos".
- Recherchez dans "Fin" à l'envers jusqu'à ce que vous trouviez le dernier élément qui est toujours plus grand que * head_pos. Appeler "Tail_Pos".
- Swap Head_Pos et Tail_Pos. Rétro commande des éléments de [Head_Pos + 1, MID [ et [Tail_Pos + 1, fin [En augmentant Commande.
@Bobber: Pouvez-vous être plus précis?
Je ne suis pas au courant d'un. L'idée de base est de représenter vos éléments comme une matrice de bit. Donc, par exemple, vous avez l'ensemble S:
000 // {}
001 // {c}
010 // {b}
011 // {b, c}
100 // {a}
101 // {a, c}
110 // {a, b}
111 // {a, b, c}
Vraiment vraiment comme cette idée!
Avoir du mal à mettre en œuvre cette idée malheureusement.
@ Bobber205 Pourriez-vous expliquer quel trouble vous êtes confronté?
Convertir un entier à un tableau de bit. J'aurais juré que j'avais l'habitude d'utiliser une fonction intégrée pour cela avant, alors j'essaie de l'écrire moi-même. XD
@Bobber: Le concept ici est un powerset. Il est différent de quelles «combinaisons» se réfèrent généralement à. Rechercher cela à la place. Voir également Stackoverflow.com/Questions/2506119/comminations-algorithm .
@Potatoswatter pourriez-vous expliquer ce que vous voulez dire. Étant donné que l'ensemble de puissance d'un ensemble est l'ensemble de toutes les combinaisons possibles de l'ensemble. Je pense que vous voulez dire, il existe de meilleurs moyens de produire des combinaisons pour un nombre spécifié d'éléments de l'ensemble.
@Arak: Le Powerset est l'ensemble de tous les sous-ensembles possibles d'un ensemble. La définition habituelle de "combinaison" est en.wikipedia.org/wiki/combination
@Potatoswatter me corrige si je me trompe s'il vous plaît. Un sous-ensemble d'un ensemble n'est qu'une combinaison de cet ensemble avec des éléments r sur n. Fondamentalement, le jeu de puissance représente ceci: S est un ensemble avec n éléments, puis p (s) est le suivant: c (n, 0) + C (n, 1) + C (n, 2) + ... + C (n, r) + ... + c (n, n)
C (N, K) est le nombre de combinaisons. Σ [k = 0..n] (c (n, k)) = 2 ^ N est un triangle de la célèbre identité de Pascal. Peut-être parce que la fonction C prend des arguments k, certains ont tendance à assumer que la question des combinaisons est fondée sur un nombre particulier d'éléments à choisir.
J'ai utilisé Cette bibliothèque quand j'ai besoin de Faites cela. Il a une interface très similaire à std :: Next_permutation de sorte qu'il sera facile à utiliser si vous avez utilisé cela avant.
Cela ne semble pas être une véritable bibliothèque de boost ...
Non, mais cela fonctionne et est sous licence sous la licence logicielle Boost, alors collez simplement le fichier d'en-tête avec votre code source ...
Si vous n'ayez pas d'autre choix, mais pour mettre en œuvre votre propre fonction, peut-être que cette horreur peut aider un peu ou peut-être d'autres horreurs parmi les réponses à cette question.
algorithme pour renvoyer toutes les combinaisons d'éléments k de n
Je l'ai écrit il y a quelque temps et la photo complète m'éludote maintenant :), mais l'idée de base est la suivante: Vous avez la combinaison d'origine et la combinaison actuelle est un vecteur d'itérateurs aux éléments sélectionnés. Pour obtenir la prochaine combinaison, vous numérisez votre jeu de droite à gauche à la recherche d'une "bulle". Par "bulle", je veux dire un ou plusieurs éléments adjacents non sélectionnés. La "bulle" pourrait être immédiatement à droite. Ensuite, dans votre combinaison, vous échangez le premier élément à gauche de la "bulle" et tous les autres éléments de la combinaison, qui sont à droite dans l'ensemble, avec un sous-ensemble d'éléments adjacents qui commencent au début de la " Bubble ".
Enumération du Powerset (c'est-à-dire que toutes les combinaisons de toutes tailles) peuvent utiliser une adaptation de l'algorithme d'incrémentation binaire.
size 1: apples size 2: apples apples size 1: beans size 2: apples beans size 3: apples apples beans size 2: beans beans size 3: apples beans beans size 4: apples apples beans beans size 1: cherries size 2: apples cherries size 3: apples apples cherries size 2: beans cherries size 3: apples beans cherries size 4: apples apples beans cherries size 3: beans beans cherries size 4: apples beans beans cherries size 5: apples apples beans beans cherries
Combinaisons: De Mark Nelson's Article sur le même sujet, nous avons Next_Combination http: // marknelson .US / 2002/03/01 / Next-permutation
Permutations: de stl nous avons STD :: Next_permutation
template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
if ((first == last) || (first == k) || (last == k))
return false;
Iterator itr1 = first;
Iterator itr2 = last;
++itr1;
if (last == itr1)
return false;
itr1 = last;
--itr1;
itr1 = k;
--itr2;
while (first != itr1)
{
if (*--itr1 < *itr2)
{
Iterator j = k;
while (!(*itr1 < *j)) ++j;
std::iter_swap(itr1,j);
++itr1;
++j;
itr2 = k;
std::rotate(itr1,j,last);
while (last != j)
{
++j;
++itr2;
}
std::rotate(k,itr2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
J'ai du mal à faire confiance à cet algorithme avec sa variable atroceuse nommée, son code mort évident, etc.
Je ne suis toujours pas sûr de la correction, mais au moins voici une version légèrement plus propre Paste.ubuntu.com / p / yxgtdjtyfd
Le web paresseux est revenu avec cette implémentation qui semble être beaucoup plus robuste. HOWARDHINNANT.GITUB.IO/COMBINATIONS.HTML / CC @ HOWARD-HINNANT
Vous devez être beaucoup plus spécifique
Probablement même un peu plus précis.
Dupliqué possible de Stackoverflow.com/questions/2211915/... < / a>