Je cherche un algorithme au moins complexe de temps qui résoudrait une variante du problème de somme parfait (initialement: trouver toutes les combinaisons de sous-ensemble de taille variable à partir d'une matrice [*] d'entiers de taille Je suis conscient que ce problème est NP-dur, donc je ne m'attends donc pas à une solution générale parfaite, mais quelque chose qui pourrait au moins courir dans un délai raisonnable dans mon cas, avec choses que j'ai essayé jusqu'à présent: Trouver une combinaison, puis faire des modifications successives sur elle et ses modifications
Supposons que j'ai un tableau tel que:
donc j'ai J'ai trouvé grâce à une méthode obscure (bruteforce?) Un sous-ensemble de ce sous-ensemble i «M trouvez d'autres combinaisons possibles en prenant deux éléments de celui-ci et en les remplaçant avec d'autres éléments qui résument la même somme, c'est-à-dire que Le problème principal comme suggéré ici est que Il est difficile de déterminer quand c'est fait et cette méthode est plutôt chaotique. J'ai imaginé des variantes de cette méthode, mais elles travaillent vraiment en cours assez explicite. Ceci est une méthode naïve qui ne fonctionne pas bien dans mon cas depuis que j'ai un assez grand J'ai expérimenté plusieurs mécanismes liés à la définition d'une zone de recherche au lieu d'itération stupidement toutes les possibilités, mais c'est plutôt compliqué et travaille toujours en cours < / p> Que suggéreriez-vous? (Les extraits peuvent être dans n'importe quelle langue, mais je préfère C ++) [*] Pour effacer le doute sur la question de savoir si la collection de base peut contenir des doublons, j'ai utilisé le terme "tableau" au lieu de "SET" être plus précis. La collection peut contenir des entiers en double dans mon cas et beaucoup, avec 70 entiers différents pour 1000 éléments (comptes arrondis), par exemple n cette somme à un nombre spécifique x ) où la taille de combinaison sous-ensemble est d'une taille fixe k et renvoie les combinaisons possibles sans direct et également indirecte (quand il y a une combinaison contenant la exactement les mêmes éléments d'un autre dans un autre ordre dans un autre ordre) DUPLICATES. n proche de 1000 et k autour de 10
n = 8 , et j'aimerais x = 10 pour k = 3 [3,3,4] (3, 3) peut être remplacé par (1, 5) < / Code> Comme les deux ont la même somme et que les numéros de remplacement ne sont pas déjà utilisés. Donc j'obtence un autre sous-ensemble [1,5,4] , puis je répète le processus pour tous les sous-ensembles obtenus ... indéfiniment?
k combinaisons longues qui somme à x
N et un k qui n'est pas suffisamment petit pour éviter un nombre de combinaisons catastrophiques (La magnitude du nombre de combinaisons est de 10 ^ 27!)
4 Réponses :
Vous devez d'abord trier le soi-disant tableau. Deuxièmement, vous devez déterminer si le problème est réellement résoluble, pour gagner du temps ... Donc, ce que vous faites est que vous prenez les derniers éléments K et voyez si la somme de ceux-ci est plus grande ou égale à la valeur X, si elle est plus petite, si elle est plus petite, Vous avez terminé, il n'est pas possible de faire quelque chose comme ça ... S'il est en fait égal, oui, vous êtes également fait, il n'y a pas d'autres permutations ... O (n) Sent bien. Si c'est plus grand, que vous avez beaucoup de travail à faire ..... Vous devez stocker toutes les permutations d'une matrice séparée .... Ensuite, vous allez de l'avant et remplacez le plus petit chiffre K avec le plus petit élément Dans la matrice .... Si cela est toujours plus grand que X, vous le faites pour les deuxième et troisième et ainsi de suite jusqu'à ce que vous obteniez quelque chose de plus petit que X. Une fois que vous avez atteint un point où vous avez la somme inférieure à X, vous pouvez aller de l'avant et commencer à augmenter la valeur de la dernière position que vous avez arrêtée jusqu'à ce que vous frappiez x ... une fois que vous avez frappé X c'est votre combinaison ... . Ensuite, vous pouvez aller de l'avant et obtenir l'élément précédent, donc si vous aviez 1,1,5, 6 dans votre truc, vous pouvez aller de l'avant et prendre le 1 aussi, ajoutez-le à votre plus petit élément, 5 pour obtenir 6, suivant Vous vérifiez, pouvez-vous écrire ce numéro 6 comme une combinaison de deux valeurs, vous arrêtez une fois que vous avez touché la valeur .... Ensuite, vous pouvez répéter pour les autres aussi .... Vous pouvez résoudre le problème dans O (n! ) Temps dans le pire des cas ... Je ne vous suggère pas que vous 10 ^ 27 combinaisons, ce qui signifie que vous avez plus de 10 ^ 27 éléments, MHMMM Bad Idée avez-vous même beaucoup d'espace ??? C'est comme 3bits pour l'en-tête et 8 bits pour chaque entier, vous auriez besoin de 9.8765 * 10 ^ 25 téraoctets pour stocker ce réseau de closses, plus de mémoire qu'un superordinateur, vous devriez vous inquiéter de savoir si votre ordinateur peut même stocker ce monstre plutôt que si vous Peut résoudre le problème, que de nombreuses combinaisons, même si vous trouvez une solution quadratique, elle écrase votre ordinateur, et vous savez ce que le quadratique est un long passage de O (n!) ...
"Je ne suggérais pas que vous avez 10 ^ 27 combinaisons, ce qui signifie que vous avez plus de 10 ^ 27 éléments". Si votre réponse est basée sur le stockage des combinaisons K Éléments K, vous pouvez obtenir d'un réseau N éléments, puis je crains que ce ne soit problématique
"Vous devez stocker toutes les permutations d'une matrice séparée .... Ensuite, vous allez de l'avant et remplacez le plus petit des nombres K avec le plus petit élément de la matrice." Depuis que nous parlons de permutations, les éléments de cet ensemble sont les mêmes éléments avec un tri différent? Alors, comment le remplacement du plus petit nombre de chaque élément aidera-t-il? Il restera la même chose avec un tri différent, encore une fois
"Alors, comment remplacer le plus petit nombre de chaque élément aidera? Il restera la même chose avec un tri différent, à nouveau -" Ce n'est pas ce que j'ai dit ... J'ai dit remplacer le plus petit des éléments K (les éléments vous avez besoin) avec le plus petit, donc si vous en avez besoin trois, prenez les trois plus gros et voyez s'ils le dépassent s'ils remplacent le plus petit avec le plus petit élément de la matrice, vous pouvez encore continuer à faire ça .... Aussi vous Seulement ces éléments K, alors pensez récursif, ....
Deuxièmement les 10 ^ 27 éléments, meh hein, tu veux les imprimer tous ?? Parce que c'est ce que la question suggère ?? Vous avez une idée de combien de temps ça va prendre ?? Si vous avez commencé à imprimer 10 ^ 27 sans effectuer de calculs, il faudra jusqu'à l'année prochaine ... Si vous avez essayé de trouver 10 ^ 27 combinaisons, bien revenez lorsque vous avez 10 ans de plus ... peut-être que vous avez du mal à Indiquez comment le grand 10 ^ 27 est ?? Si vous avez eu beaucoup de gouttes d'eau, vous pouvez remplir toute une masse de tous les océans et des icebergs dans le système solaire, y compris Mars Moon, etc.
Je n'ai jamais mentionné que je voulais imprimer toutes les combinaisons de la taille K du tableau et que vous ne pouvez pas voir quoi dans ma question suggère que
@CodeTalker Que voulez-vous faire avec les permutations alors ?? Si la réponse n'est rien que vous préférez ne pas le faire, le moyen le plus efficacement de résoudre des problèmes est de vous débarrasser des choses que vous n'avez pas besoin ....
Je pense que vous n'avez pas bien compris ma question. Il s'agit d'obtenir toutes les combinaisons de longueur k pouvant être obtenue à partir d'une matrice de taille n et somme à un numéro x . Et fyi, permutations! = Combinaisons
@CodeTalker Vous devez être spécifique pourquoi voulez-vous les permutations ??
Une méthode de force brute à l'aide de la récursion peut ressembler à ce ...
Par exemple, donnée des variables définies, X, K, le pseudo-code suivant pourrait fonctionner: p>
setSumStructure find(int[] set, int x, int k, int setIdx)
{
int sz = set.length - setIdx;
if (sz < x) return null;
if (sz == x) check sum of set[setIdx] -> set[set.size] == k. if it does, return the set together with the sum, else return null;
for (int i = setIdx; i < set.size - (k - 1); i++)
filter(find (set, x - set[i], k - 1, i + 1));
return filteredSets;
}
La bruteforcing n'est-elle pas recommandée avec une valeur de grande N (taille de tableau)?
Oui, la forçage brute n'est pas idéale - il s'agit d'une solution simple qui peut gérer N = 1000. Le filtre supprime les nuls de la sortie et crée une liste sur le tas. Il doit s'agir de tas et pas de pile car la récursion peut être à 1000 profondeur, ce qui permet d'économiser de l'espace de pile est critique.
Avec une somme de somme raisonnable Ce problème pourrait être résolu en utilisant l'extension de l'approche de programmation dynamique pour le problème de la somme sous-ensemble ou le problème de changement de monnaie avec un nombre prédéterminé de pièces de monnaie. Notez que nous pouvons Faire une matrice 3D, une liste ou un vecteur avec une dimension extérieure Nous pouvons parcourir tous les éléments (appel de courant Item code>) de "SET" initial (j'ai remarqué des éléments répétés dans votre exemple, il n'est donc pas vrai Set). P> Now Scannez une liste [] code> de la dernière entrée au début. (Cette astuce aide à éviter de répéter l'utilisation du même article). P> si après la numérisation complète Sortie de mon programme Delphi rapide pour les données suivantes: P> compter code> toutes les variantes en pseudopolynomial Time O (x * N) code>, mais la taille de la sortie peut augmenter de manière exponentielle, la génération de toutes les variantes pourrait donc être un problème. x-1 code> par exemple: a [] [] [] code>. Chaque élément A [p] code> de cette liste contient une liste des sous-ensembles possibles avec la somme p code>. P> a [i-item] code> contient des sous-ensembles avec la taille k code>, nous Peut ajouter tous ces sous-ensembles à A [i] code> Ajout élément code>. p> A [x] code> contient sous-ensembles de taille k code> et moins, avoir la somme x code>, et nous pouvons filtrer uniquement ceux de taille k code> p> int main()
{
vector<vector<vector<int>>> A;
vector<int> Lst = { 1, 2, 3, 3, 4, 5, 6, 7 };
int k = 3;
int sum = 10;
A.push_back({ {0} }); //fictive array to make non-empty variant
for (int i = 0; i < sum; i++)
A.push_back({{}});
for (int item : Lst) {
for (int i = sum; i >= item; i--) {
for (int j = 0; j < A[i - item].size(); j++)
if (A[i - item][j].size() < k + 1 &&
A[i - item][j].size() > 0) {
vector<int> t = A[i - item][j];
t.push_back(item);
A[i].push_back(t); //add new variant including current item
}
}
}
//output needed variants
for (int i = 0; i < A[sum].size(); i++)
if (A[sum][i].size() == k + 1) {
for (int j = 1; j < A[sum][i].size(); j++) //excluding fictive 0
cout << A[sum][i][j] << " ";
cout << endl;
}
}
Pourriez-vous s'il vous plaît fournir un lien de ce que vous faites référence au premier paragraphe? Cela aiderait à comprendre votre solution
Vous pouvez trouver un problème général Sous-Somme sous-ensemble (sans limite de taille) dans de nombreuses sources. Ici, je fournis un code Delphi de travail, espérons que c'est compréhensible pour vous.
L'extrait fourni aide beaucoup, bien que je ne comprenne toujours pas complètement depuis que la solution est très difficile pour moi de suivre. Juste une note: il semble donner des résultats incorrects lorsque la matrice contient plusieurs duplicats (testés contre vecteur
Voici une solution complète en Python. La traduction de C ++ est laissée au lecteur.
Comme la somme sous réserve habituelle, la génération du résumé doublement lié des solutions est pseudo-polynomial. Il est incidemment pour votre exemple, ici sont les solutions: O (count_values * distincts_sums * profondeurs_of_f_sums) . Cependant, il y a réellement itération à travers eux peut être exponentiel. Mais en utilisant des générateurs comme je l'ai évité d'utiliser beaucoup de mémoire pour générer cette liste, même si cela peut prendre beaucoup de temps à exécuter.
L'approche de générer les solutions sur le go au lieu de les stocker est exactement ce que je cherche. Pensez-vous que la mise en œuvre du filtrage en double avec cette solution serait possible?
@CodeTalker Ce code fait déjà du filtrage en double. Notez que [1, 3, 6] ne se produit qu'une fois, même s'il y a 2 3 ans disponible.
Cela dit, j'ai eu un bogue dans le filtrage en double. Fixation maintenant.
Était sur le point de le mentionner. Merci!
trier votre ensemble; Choisissez des nombres en elle tout en maintenant la taille de sous-ensemble actuelle et la somme cible. Mettez à jour cette somme sur chaque choix en soustrayant l'élément cueilli. Lorsque la cible de somme actuelle est inférieure à l'élément disponible suivant de l'ensemble, c'est une branche ayant échoué. Pour les chenilles K = 10, cela signifie créer des boucles nées K. Faites-le avec la récursion, réagissant au succès de l'invocation la plus interne.
@Willness Merci de votre réponse, mais j'ai du mal à comprendre certains points. Quoi de "maintenir la taille de sous-ensemble actuelle et la somme cible" signifie dans ce contexte? Je me demande aussi pourquoi tu l'as posté ici dans les commentaires
Je cherche un algorithme C ++ complexe le moins chronométrique - algorithmes ne se souciez pas du langage de programmation qu'ils sont écrits.
Est
x restreint par une valeur raisonnable?@Paulmckenzie Je voulais dire de préférence si un extrait est fourni
@Mbo
x est une somme que vous pouvez toujours obtenir dans mon cas, si c'est votre questionLes problèmes de CodeTalke avec la somme = 100, 1000000 ou 10 ^ 15 peuvent être résolus avec différentes approches.
@Mbo n'a pas imaginé que cela pourrait être, désolé. Dans mon cas, la somme peut aller de 0 (facilement obtenue dans ce cas, aucun algorithme spécifique n'est nécessaire) à 3000. Je mettrai à jour ma question pour être plus claire
ici une réponse connexe de la mine. C'est en Lisp commun mais il y a beaucoup de verbiage et un pseudocode. mettre en œuvre les boucles imbriquées avec une récursion; Ajoutez un argument supplémentaire à la fonction, la somme de la sélection actuelle et utilisez-la pour éviter tout calcul de ne pas conduire à une solution. Sautez sur les questions liées de cette réponse, trouvez quelques réponses plus pertinentes de moi, bien qu'aucun n'est en C / C ++. cf. Stackoverflow.com/a/34562122/849891 Stackoverflow.com/q/62764261/f#COMMENT111052017_62765370 Stackoverflow.com/a/15179576/849891 < / a>
et Ce (si pas déjà inclus dans Le commentaire ci-dessus), bien qu'il s'agisse d'un joli code pillonné pour un programmeur non-SCHEMER à lire ... mais toujours la discussion et les liens qu'il pourrait être utile.
this < / a> est aussi quelque peu liée. C'est en C ++.
Que voulez-vous faire après avoir trouvé les combinaisons ?? Stockez-les ?? Je ne pense pas que ce soit réaliste ?? Trouver le plus grand ?? Trouver le plus petit ?? Pourquoi avez-vous besoin d'eux ?? Résoudre ces problèmes d'abord ..... une manière la plus efficace à travers un graphique ???