Disons que nous avons un tel tableau: myArray = [A, A, B, B, C, C, D, E]
Je voudrais créer un algorithme pour qu'il trouve toutes les combinaisons qui s'additionnent à l'ensemble du tableau, où aucun des éléments sont répétés.
Exemples de combinaisons:
var myArray = ["A", "A", "B", "B", "C", "C", "D", "E"] console.log([...new Set(myArray)])
Précision: [A, B, C] [A, B, C] [D, E] et [A, B, C] [D, E] [A, B, C] sont les mêmes combinaisons. La commande avec les sous-ensembles n'a pas non plus d'importance. Par exemple, [A, B, C] et [B, A, C] doivent être identiques.
Jusqu'à présent, je n'ai pas progressé au-delà de
[A, B, C, D, E] [A, B, C] [A, B, C, D] [A, B, C, E] [A, B, C] [A, B, C] [D, E]
Mais cela n'aide pas du tout, cela renvoie juste un ensemble distinct. Je n'ai pas trouvé de problème similaire publié auparavant, alors quelqu'un pourrait-il me guider ici pour savoir comment y parvenir?
5 Réponses :
Ceci génère toutes les permutations possibles du résultat recherché, donc il ne répond pas à la question.
function* combinations(combos) {
yield combos;
for(const [i1, group] of combos.entries()) {
for(const [i2, group2] of combos.slice(i1 + 1).entries()) {
if(group.some(v => group2.includes(v))) continue;
yield* combinations([
...combos.filter((_, index) => index !== i1 && index !== i2),
[...group, ...group2]
]);
}
}
}
console.log([...combinations([1, 2, 3, 4, 1].map(v => ([v])))]);
Vous pouvez commencer avec un tableau avec des combinaisons ne contenant qu'un seul élément, puis passez en revue ces combinaisons et fusionnez deux tableaux d'entre eux, procédez de manière récursive.
Vous pouvez le faire en énumérant toutes les combinaisons possibles, puis en trouvant les permutatinos pour chaque combinaison, puis en filtrant l'élément pour vous assurer qu'ils sont uniques. Ce filtrage peut être effectué en l'insérant dans un ensemble.
La fonction du sous-ensemble provient de @le_m ( Vérifiez cette réponse ) .
function* subsets(array, offset = 0) {
while (offset < array.length) {
let first = array[offset++];
for (let subset of subsets(array, offset)) {
subset.push(first);
yield subset;
}
}
yield [];
}
function* permutations(elements) {
if (elements.length === 1) {
yield elements;
} else {
let [first, ...rest] = elements;
for (let perm of permutations(rest)) {
for (let i = 0; i < elements.length; i++) {
let start = perm.slice(0, i);
let rest = perm.slice(i);
yield [...start, first, ...rest];
}
}
}
}
const arr = ['A', 'a', 'B', 'b', 'C', 'c', 'd', 'e'];
const results = new Set();
for (let subset of subsets(arr)) {
if (subset.length) {
for (let permut of permutations(subset)) {
results.add(permut.join(''));
}
}
}
console.log([...results]);
Vous pouvez d'abord regrouper les mêmes éléments et les compter, ce qui donne un tableau comme celui-ci:
const counts = new Map;
for(const value of [1, 1, 1, 2, 3, 3, 4, 4])
counts.set(value, (counts.get(value) || 0) + 1);
const result = [];
for(let combo = 0; combo < counts.size; combo++) {
const subResult = [];
const combos = [...counts];
for(let i = 0; i <= combo; i++) combos[i][0] -= 1;
subResult.push(combos.slice(0, combo).map(([_, value]) => value);
while(combos.some(([count]) => count > 0)) {
subResult.push(combos.filter(([count]) => count > 0).map(([_, value] => value));
}
result.push(subResult);
}
(1 est dupliqué deux fois, 3 et 4 une fois)
Maintenant vous pouvez commencer et retirer les quatre premiers éléments, puis les 3 de la deuxième ligne et ensuite celui de la dernière ligne, ce qui donne
[[1, 2, 3], [1, 3, 4], [1, 4]]
Maintenant, pour obtenir le combo suivant, retirez simplement 3 de la première ligne et laissez les autres valeurs remonter:
1 | | 3 | 4 1 | | | 4
maintenant à nouveau retirez les lignes, et vous obtenez
[[1, 2, 3, 4], [1, 3, 4], [1]]
Maintenant, répétez ce modèle avec la première ligne (prenez 2, 1) et ainsi de suite, répétez également cela avec les lignes, alors vous devriez obtenir le résultat que vous voulez obtenir.
1 | 2 | 3 | 4 1 | | 3 | 4 1
Implémentation d'un algorithme à partir de zéro qui:
.as-console-wrapper { top: 0; max-height: 100% !important; }
const decrementKey = (o, k) => o[k]--;
const isEmpty = (o) => Object.keys(o).length === 0;
const removeKeys = (o) => Object.keys(o).forEach(k => { if (o[k] < 1) delete o[k]; });
const frequencyMap = (a) => a.reduce((r, v) => Object.assign(r, { [v] : (r[v] || 0) + 1 }), {});
const cloneMap = (o) => Object.keys(o).reduce((r, k) => Object.assign(r, { [k] : o[k] }), {});
let myArray = ["A", "A", "B", "B", "C", "C", "D", "E"];
let groups = solve(myArray);
console.log(groups.map(g => g.map(a => a.join('')).join(' | ')).join('\n'));
function solve(arr) {
let freq = frequencyMap(arr), results = [];
for (let max = Object.keys(freq).length; max > 1; max--) {
let result = [], clone = cloneMap(freq);
while (!isEmpty(clone)) {
result.push(Object.keys(clone).reduce((res, key, index) => {
if (index < max) {
decrementKey(clone, key);
res.push(key);
}
return res;
}, []));
removeKeys(clone);
}
if (result.length > 0) results.push(result);
}
return results;
}
Semble en manquer un certain nombre. En voici une: A | A | B | B | C | C | D | E
@ גלעדברקן C'est parce que je me suis arrêté court ... max> 1 au lieu de max> 0 . Je ne pensais pas que les éléments individuels étaient voulus.
même avec ce remplacement, il manque encore des lots, par ex. AB | AB | CD | C | E
@WalterTross J'ai essayé votre algorithme avec un cas de 23 éléments, et ci-dessous se trouve la sortie: ABCDE | ABCDE | ABCDE | ABCDE | ABD ABCD | ABCD | ABCD | ABCD | ABDE | E | E | E ABC | ABC | ABC | ABC | ABD | DE | DE | DE | DE AB | AB | AB | AB | AB | CD | CD | CD | CD | DE | E | E | E A | A | A | A | A | B | B | B | B | B | C | C | C | C | D | D | D | D | D | E | E | E | E mais j'ai remarqué qu'un résultat important est ignoré. Entre la 1ère et la 2ème ligne, il devrait y avoir une ligne telle que ABCDE | ABCDE | ABCDE | ABCD | ABDE Savez-vous pourquoi cela pourrait arriver?
@Yossarian Je n'ai écrit aucun algorithme, peut-être que vous vous adressiez à M. Polywhirl. Votre commentaire n'est pas clair du tout, et de toute façon, l'algorithme de M. Polywhirl, tel qu'il est maintenant, lorsqu'il est exécuté sur les données de votre question, produit 4 lignes alors qu'il devrait y en avoir 37 ou 315, selon l'interprétation.
Oui, désolé je voulais dire @ Mr.Poliwhirl
J'obtiens 315 combinaisons. Est-ce correct? :)
Voici une récursivité:
function distribute(e, i, _comb){
// No more e's
if (e[1] == 0)
return [_comb];
// We're beyond the combination
if (i == -1)
return [_comb.concat([e])];
let result = [];
for (let c=1; c<=Math.min(_comb[i][1], e[1]); c++){
let comb = _comb.map(x => x.slice());
if (c == comb[i][1]){
comb[i][0] += e[0];
} else {
comb[i][1] -= c;
comb.push([comb[i][0] + e[0], c]);
}
result = result.concat(distribute([e[0], e[1] - c], i - 1, comb));
}
let comb = _comb.map(x => x.slice());
return result.concat(distribute(e, i - 1, comb));
}
function f(arr){
function g(i){
if (i == 0)
return [[arr[0]]];
const combs = g(i - 1);
let result = [];
for (let comb of combs)
result = result.concat(
distribute(arr[i], comb.length - 1, comb));
return result;
}
return g(arr.length - 1);
}
function show(arr){
const rs = f(arr);
const set = new Set();
for (let r of rs){
const _r = JSON.stringify(r);
if (set.has(_r))
console.log('Duplicate: ' + _r);
set.add(_r);
}
let str = '';
for (let r of set)
str += '\n' + r
str += '\n\n';
console.log(JSON.stringify(arr));
console.log(set.size + ' combinations:');
console.log(str);
}
show([['A', 2], ['B', 2], ['C', 2], ['D', 1], ['E', 1]]);
Donc, d'après ce que j'ai compris, la méthode show est juste là pour sortir le tableau. Est-il possible de sortir toutes les combinaisons dans un tableau à deux dimensions, où chaque ligne est une combinaison de sous-ensembles du tableau d'origine?
@Yossarian la fonction f est celle qui renvoie la solution. Chaque élément d'un résultat est sous la forme ["set", N] , qui nous indique qu'il y a N instances de l'ensemble set dans cette combinaison (c'est-à-dire, ["ABD", 2] signifierait [A, B, D], [A, B, D] ). Pouvez-vous créer une fonction pour convertir le résultat dans la forme souhaitée, en développant le set (indice: méthode JavaScript String split ) et en le dupliquant N fois? (sinon, je peux l'ajouter un peu plus tard.)
@Yossarian J'ai ajouté une fonction appelée allPartitions qui effectue la conversion, au lien suivant: repl.it/@gl_dbrqn/IllegalComposedBracket J'espère que cela vous aidera!
Je vous remercie! Cela fonctionne presque parfaitement maintenant! J'ai juste une question cependant, j'essaie de faire en sorte qu'au lieu d'avoir [['A', 'AB', 'BC'], ['A', 'ABC', 'B'] , je veux l'avoir sous la forme [['A', ['A', 'B'], ['B', 'C']], ['A', ['A' , 'B', 'C'], 'B'] de sorte que lorsque j'utilise non pas des lettres mais des chaînes arbitraires comme éléments du tableau d'entrée, je pourrai toujours les voir et les compter. Comment puis-je atteindre cet objectif?
@Yossarian Je ne suis pas sûr de ce que tu veux dire. Pouvez-vous s'il vous plaît fournir un exemple clair de l'entrée souhaitée et de la sortie souhaitée?
Bien sûr, par exemple lorsque je saisis cette [["pomme", 1], ["orange", 2]] la sortie est: [[['A', 'p', 'p', 'l', 'e', 'O', 'r', 'a', 'n', 'g', 'e'], ['O', 'r', 'a', 'n', 'g', 'e']], [['A', 'p', 'p', 'l', 'e'], ['O', 'r', 'a', 'n', 'g', 'e'], ['O', 'r', 'a', 'n', 'g', 'e']]] Mais la sortie souhaitée serait `` [[[Pomme, Orange], [Orange]], [[Pomme], [Orange], [Orange]]]
@Yossarian ah, je vois ce que tu veux dire, le code actuel suppose que les éléments de l'entrée sont des chaînes de caractères uniques. Je suis absent d'un ordinateur pour le moment, mais je ferai un changement plus tard pour accepter une entrée plus générale.
@Yossarian en passant, je pense que votre demande est plus une demande de codage qu'une demande d'algorithme. Je pense qu'il serait raisonnable de demander à vous de trouver un moyen d'utiliser l'implémentation actuelle - par exemple, avec un peu de compétences JavaScript, vous pouvez créer une carte qui mappe «A» à «Apple» et "B" à "Orange", puis exécutez l'implémentation actuelle et mappez les résultats à ce que vous voulez (dans ce cas "Apple" et "Orange"). Ce genre de défi serait une bonne et j'espère une expérience d'apprentissage pas trop difficile pour vous. Qu'est-ce que tu penses?
Bien sûr, je vais essayer cela tout de suite et voyons comment cela se passe, merci pour toute l'aide!
@Yossarian pas de problème, merci pour une question intéressante. (À propos, par paresse, la façon dont je mettrais en œuvre l'acceptation de l'entrée plus générale serait d'utiliser un type de carte similaire :)
@Yossarian J'ai ajouté l'idée de mappage à la fonction allPartitions ici: repl.it/@ gl_dbrqn / IllegalComposedBracket passer des chaînes plus longues ou juste des éléments arbitraires devrait fonctionner maintenant (voir l'exemple à la fin). Veuillez me faire savoir si vous rencontrez des problèmes.
Ce n'est pas un problème JS autant qu'un problème mathématique. Essayez-le, au moins une première tentative, puis nous pourrons vous aider
Cela pourrait vous aider .
Je dirais que l'obtention de l'ensemble des éléments distincts est une bonne première étape; Vous devez maintenant compter le nombre de fois où chacun de ces éléments apparaît dans l'original, puis commencer à remplir les tableaux avec ces éléments distincts.
Le troisième exemple de combinaison n'est pas unique. Voir Rechercher toutes les combinaisons de valeurs de tableau JavaScript
Pouvez-vous clarifier pourquoi
[a, b, c]apparaît deux fois dans votre exemple de combinaisons.Bien sûr, j'ai peut-être mal formulé la question. Ce que je veux réaliser, c'est créer des sous-ensembles où chaque élément n'est répété qu'une seule fois. Ces sous-ensembles doivent correspondre à l'ensemble complet. J'ai déjà vérifié les liens mentionnés dans les commentaires, mais c'étaient des exemples différents.
Sont
[A, B, C] [A, B, C] [D, E]et[A, B, C] [D, E] [A, B, C]combinaisons distinctes? Que diriez-vous de[A, B, C] [A, B, C] [D, E]et[A, B, C] [C, A, B] [E, D ]? Les ensembles de singleton sont-ils autorisés (par exemple,[A] [A] [B] [B] [C] [C] [D] [E])?Veuillez préciser si vous avez besoin de la dernière solution mentionnée par @DavidEisenstat. Sinon, quels sont les critères pour éliminer certaines de ces possibilités? Je peux voir qu'il ne s'agit pas simplement d'une quantité limitée d'ensembles de couverture, car vos exemples donnés incluent 3 ensembles lorsqu'un minimum de 2 est possible.
La réponse @Mr. Poliwhirl produit le résultat souhaité. Ainsi, les combinaisons mentionnées par David Eisenstat ne sont pas des combinaisons distinctes.
[A, B] [A, B, C] [C, D, E]semble une combinaison parfaitement légitime selon votre question, mais elle n'est pas produite par la solution de @Mr. Polywhirl. Si c'est légitime, la réponse de @Mr. Polywhirl a tort. Si ce n'est pas le cas, vous devez expliquer pourquoi et modifier votre question.Je ne sais pas pourquoi vous pensez que la réponse de M. Polywhirl produit ce que vous semblez demander. Pouvez-vous expliquer? (Si je suis correctement, ma réponse semble montrer 315 façons différentes de partitionner le multiset avec chaque partie ayant des éléments distincts.)
Hé, @ גלעדברקן alors j'ai jeté un coup d'oeil à nouveau et en fait les 315 possibilités semblent être la bonne réponse. J'ai essayé l'algorithme de M. Poltwhirl dans mon code et pour mes besoins, il sert bien parce que lorsque les combinaisons deviennent comme
[AB] [A] [B] [C] ...et ainsi de suite, cela ne produit pas le résultat souhaité, je peux donc ignorer ces possibilités en toute sécurité. Le contexte plus large n'est pas nécessaire pour expliquer pour le moment je pense, mais pour ce que j'ai demandé ci-dessus, votre réponse est la plus précise pour le moment :)pour récapituler: 315 possibilités est la bonne réponse, sauf que, pour votre application, vous rejetteriez celles qui contiennent des ensembles d'un seul élément, comme
[A], même s'il n'y en a qu'un, ce qui nous laisse 37 possibilités. Est-ce que je l'ai bien compris?@WalterTross Oui. J'essaie d'optimiser quelque chose, et le meilleur résultat provient d'éléments distincts et groupés. Donc, dans notre exemple, notre tableau a 8 éléments, et les groupes les plus optimaux pourraient être 5-3 ou 4-4 ou 3-3-2 et ainsi de suite. La seule partie du problème que j'ai eue était de diviser le tableau en groupes, c'est pourquoi je n'ai écrit que sur cette partie et non sur tout le problème. Mais d'après ce que j'ai appris depuis hier, j'essaierai d'être beaucoup plus clair la prochaine fois que je demanderai quelque chose, désolé pour les confusions.
@WalterTross J'ai un pour les partitions personnalisées , aussi :) Mais il ne conserve pas de pièces avec des éléments distincts. Je suppose que la prochaine chose à faire serait de combiner les deux.
@Yossarian J'ai pris la liberté d'éditer le titre de la question pour qu'il soit plus descriptif. J'espère que ça va. Vous êtes libre de le changer, bien sûr. (Et demander à un autre, peut-être, sur les partitions personnalisées (plutôt que toutes) où chaque partie a des éléments distincts :)