Question 51496 in Javascript Question posted in
A very good W3school tutorial can be found here.

Recursive ArrayPush in Javascript to get all combination

var Combination = [];

function Reduce(List, Target) {
        if(List.length > 1) {
            return Reduce(List.filter(word => word !== List[0]), List[1]);
        } else {
            return List[0];
        }
    }

If user input X = ["AB, "DE", "SZ", "YY"], above function have to return all possible combination like ["AB", "DE"], ["AB", "YY", "SZ"] .

I’m trying to solve it in recursive way, but stuck at pushing result to Combination.
Where do I have to change to get all possible combinations?

If my approach is wrong, thanks for the correction in advance🙏🏻

Tags:

3

Answers


  1. 0

    It looks like you’re looking for the power set of your inputs, that is, the set of all subsets of your set. For instance, the power set of [1, 2, 3] is:

    [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

    This includes the first, empty array, and every other combination of the elements. There will be 2 ^ n elements in the set, where n is the length of your original set. Note that although this is an array, it is theoretically an unordered collection.

    Here is one version of powerSet:

    const powerSet = ([x, ...xs]) =>
  x == undefined 
    ? [[]]
    : powerSet (xs) .flatMap (p => [p, [x, ...p]])


console .log (powerSet ([1, 2, 3]) .map (ss => ss.join ('/')))
console .log (powerSet (["AB", "DE", "SZ", "YY"]) .map (ss => ss.join('/')))
    .as-console-wrapper {max-height: 100% !important; top: 0}

    (We add the .join('/') just to make it easier to see on the console. The result is an array of arrays.)

    We recur on the tail of the array, keeping those values as well as the sets found by including the head of the array alongside the values of that subset.

    Login or Signup to reply.
  2. 0

    What you describe are all permutations of all subsets of an n-set.

    One way to produce those is to use a generator function:

    function* permutationsOfSubSets([first, ...rest]) {
    if (first === undefined) return yield [];
    for (const result of permutationsOfSubSets(rest)) {
        yield result; // The result without first value...
        // ...and extended with the first value injected at every possible index
        for (let injectAt = 0; injectAt <= result.length; injectAt++) {
            yield [...result.slice(0, injectAt), first, ...result.slice(injectAt)];
        }
    }
}

// Example run
const arr = ["AB", "DE", "SZ"];
// Iterate the results and print them
for (const result of permutationsOfSubSets(arr)) {
    console.log(JSON.stringify(result));
}
// If you need them as array:
const results = [...permutationsOfSubSets(arr)];
    Login or Signup to reply.
  3. 0 
    function combinations(list) {
  const results = [];
  for (const item of list) {
    const length = results.length;
    // add the combination that contains only the item
    results.push([item]);
    // for each of the previous combinations ...
    for (let i = 0; i < length; ++i) {
      // ... add a copy/version with item
      results.push([...results[i], item]);
    }
  }
  return results;
}

console.log(combinations([1, 2, 3, 4]).join("n"));
    .as-console-wrapper {
  top: 0;
  max-height: 100%!important;
}

    You could write this in a recursive manner, but it would be more complicated and would create way more throwaway arrays in the process.

    Another approach that is a bit more academic. Think numbers in binary, and each position tells if this item is included in this particular combination.
    That means for n items in the list you need to go up to combination (2 ** n)-1 which is just n ones.

    So you count up and check the bits which items of the list it contains.

    function combinations(list) {
  const length = 2 ** list.length;
  const results = [];
  // combination == 0 would be empty.
  for (let combination = 1; combination < length; ++combination) {
    results.push(list.filter((_, col) => combination & (1 << col)));
  }
  return results;
}

console.log(combinations([1, 2, 3, 4]).join("n"));
    .as-console-wrapper {
  top: 0;
  max-height: 100%!important;
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search