1
votes

Rechercher une combinaison de sous-ensembles dans un tableau

J'ai des difficultés avec ce problème particulier.

On m'a demandé de trouver une combinaison de sous-ensembles qui ont strictement un élément de moins que le tableau d'entrée. Par exemple à partir du tableau:

var num = [1,2,3,4,5];
var n = num.length;
var i, j;

for(i = 0; i < n; i++){
    for(j = i + 1; j < n; j++){
        console.log(num[i] + ", " +  num[j]);
    }
}

Trouvez ces combinaisons:

[2,4]
[2,6]
[4,6]

et de ce tableau:

var num = [2,4,6]

Trouvez ces combinaisons:

[1,2,3,4]
[2,3,4,5]
[1,2,4,5]
[1,2,3,5]
[1,3,4,5]

J'ai déjà essayé ce code mais il n'est pas dynamique car je dois imprimer tous les index du tableau: p>

var num = [1,2,3,4,5]

Existe-t-il un moyen de le faire? Merci d'avance.

javascript arrays combinations

5 commentaires

Votre question n'est pas bien définie, voulez-vous trouver tous les sous-ensembles qui ont strictement un élément de moins que le tableau d'entrée?

Y a-t-il déjà des doublons dans le tableau et si oui, comment cela devrait-il être géré?

@UriGoren Oui, merci pour la correction, j'ai déjà révisé la question

@ScottSauyet Oui, le premier ensemble contient [2,3,4,5], déjà répertorié dans la question

@MarkSchultheiss la combinaison unique est uniquement limitée à l'index particulier du tableau. La valeur pourrait être dupliquée pour cette question.

3 Réponses :

2
votes

Vous pouvez faire quelque chose comme:

Bouclez le tableau et supprimez-en un à chaque fois

// Function to return an array except the given one
Array.prototype.except = function(val) {
    return this.filter(function(x) { return x !== val; });        
}; 


// For array of 5
var array1 = [1,2,3,4,5]
var result1 = []

array1.forEach(function(val){
  result1.push(array1.except(val))
});

console.log('For Array of 5')
console.log(result1)


// For array of 3

var num = [2,4,6]
var num_result = []
num.forEach(function(val){
  num_result.push(num.except(val))
});
console.log('For Array of 3')
console.log(num_result)

0 commentaires

4
votes

Vous pouvez prendre un générateur et prendre un seul élément ou le résultat.

.as-console-wrapper { max-height: 100% !important; top: 0; }

function* getCombinations(array) {
    var l = array.length;
    while (l--) yield array.filter((_, i) => i !== l);
}

console.log([...getCombinations([1, 2, 3, 4, 5], 4)].map(a => a.join(' ')));
console.log([...getCombinations([2, 4, 6], 2)].map(a => a.join(' ')));

Pour supprimer un seul élément, vous pouvez filtrer le tableau.

.as-console-wrapper { max-height: 100% !important; top: 0; }

function* getCombinations(array, length, left = []) {
    var i = 0;
    if (!length) yield left;
    while (i < array.length) {
        yield* getCombinations(array.slice(i + 1), length - 1, [...left, array[i]]);
        i++;
    }
}

console.log([...getCombinations([1, 2, 3, 4, 5], 4)].map(a => a.join(' ')));
console.log([...getCombinations([2, 4, 6], 2)].map(a => a.join(' ')));
console.log([...getCombinations([1, 2, 3, 4, 5], 3)].map(a => a.join(' ')));  // not asked

0 commentaires

7
votes

Puisque vous supprimez juste un élément pour chaque résultat, vous aurez un résultat pour chaque élément de votre liste d'origine. Vous pouvez simplement map () et slice():

const remove = (num) => num.map((_, i, arr) => [...arr.slice(0, i), ...arr.slice(i+1)])

console.log(remove([1,2,3,4,5]))
console.log(remove([2, 4, 6]))

4 commentaires

Qu'en est-il d'avoir un tableau de cinq éléments et un jeu de résultats avec trois éléments?

@NinaScholz - cela ne correspondrait pas au problème qui dit spécifiquement, "des sous-ensembles qui ont strictement un élément de moins que le tableau d'entrée."

@NinaScholz - oui, le titre est un peu trompeur.

@MarkMeyer Mes excuses pour l'ambiguïté du titre du fil, déjà édité. J'espère que cela aide.Merci également pour la solution.