javascript - Get all (number of) combinations of an array - Stack Overflow

admin管理员组

文章数量:1024679

I have been trying to acplish this since yesterday, though no luck yet. I have found solutions where there always is a slight difference in what I want to acplish.

I am trying to get all possible binations, slightly like this: bination_k, but I also want the same items to pair up with itself, so given the following:

input [1, 4, 5] and 2 (number of binations) should return:

[1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

input [1, 4, 5] and 3 should return:

[1, 1, 1], [1, 1, 4], [1, 1, 5], [1, 4, 4], [1, 4, 5], [4, 4, 4], [4, 4, 5], [5, 5, 5], [5, 5, 4], [5, 5, 1] (The order is not important).

I have been adjusting bination_k, it got me far enough that it worked with 2 but it didn't work when I provided 3 as a parameter.

const binations = getAllCombinations([1, 4, 5], 2);
// binations = [1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

Any tips are wele!

I have been trying to acplish this since yesterday, though no luck yet. I have found solutions where there always is a slight difference in what I want to acplish.

I am trying to get all possible binations, slightly like this: bination_k, but I also want the same items to pair up with itself, so given the following:

input [1, 4, 5] and 2 (number of binations) should return:

[1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

input [1, 4, 5] and 3 should return:

[1, 1, 1], [1, 1, 4], [1, 1, 5], [1, 4, 4], [1, 4, 5], [4, 4, 4], [4, 4, 5], [5, 5, 5], [5, 5, 4], [5, 5, 1] (The order is not important).

I have been adjusting bination_k, it got me far enough that it worked with 2 but it didn't work when I provided 3 as a parameter.

const binations = getAllCombinations([1, 4, 5], 2);
// binations = [1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

Any tips are wele!

• javascript
• arrays

Share Improve this question Follow edited May 13, 2021 at 10:26 AbsoluteBeginner 2,26333 gold badges1414 silver badges2424 bronze badges asked May 13, 2021 at 6:18 CemCem 5144 bronze badges 5

• Can you post what you have done to achieve with 2? – Yadab Commented May 13, 2021 at 6:35
• 1 Why is [1, 5, 5] not in your expected output? – Nick Commented May 13, 2021 at 6:39
• Yes, I have done several things but the simplest and the shortest way to achieve this was to change line 121 to tailbs = k_binations(set.slice(i), k - 1); @ bination_k – Cem Commented May 13, 2021 at 6:41
• 1 @Nick I see that I have missed that one, woops! I have edited my initial post and added that item in the expected list. – Cem Commented May 13, 2021 at 6:43
• Here is a dynamical programming solution with no recursion. Recursion in JS might result call stack overflow problems after a certain range. – Redu Commented May 13, 2021 at 8:21

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 5

The problem is monly referred to as k-binations with repetitions.

Here's a solution that relies on recursion to get the desired result:

const binations = (array, r) => {
  const result = [];
  const fn = (array, selected, c, r, start, end) => {
    if (c == r) {
      result.push([...selected]);
      return;
    }
    
    for (let i = start; i <= end; i++) {
      selected[c] = array[i];
      fn(array, selected, c + 1, r, i, end);
    }
  }
  
  fn(array, [], 0, r, 0, array.length - 1);
  return result;
}

console.log(binations([1, 4, 5], 3));

A modified version of the code you provided:

function getAllCombinations(arr, n) {
  if (n <= 0) return [];
  if (n === 1) return [...arr];

  return arr.reduce((acc, cur, i) => {
    const head = arr.slice(i, i + 1);
    const binations = getAllCombinations(arr.slice(i), n - 1)
      .map(x => head.concat(x));
    return [...acc, ...binations];
  }, []);
}

console.log(getAllCombinations([1, 4, 5], 2).join('|'));
console.log(getAllCombinations([1, 4, 5], 3).join('|'));

I have been trying to acplish this since yesterday, though no luck yet. I have found solutions where there always is a slight difference in what I want to acplish.

I am trying to get all possible binations, slightly like this: bination_k, but I also want the same items to pair up with itself, so given the following:

input [1, 4, 5] and 2 (number of binations) should return:

[1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

input [1, 4, 5] and 3 should return:

[1, 1, 1], [1, 1, 4], [1, 1, 5], [1, 4, 4], [1, 4, 5], [4, 4, 4], [4, 4, 5], [5, 5, 5], [5, 5, 4], [5, 5, 1] (The order is not important).

I have been adjusting bination_k, it got me far enough that it worked with 2 but it didn't work when I provided 3 as a parameter.

const binations = getAllCombinations([1, 4, 5], 2);
// binations = [1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

Any tips are wele!

I have been trying to acplish this since yesterday, though no luck yet. I have found solutions where there always is a slight difference in what I want to acplish.

I am trying to get all possible binations, slightly like this: bination_k, but I also want the same items to pair up with itself, so given the following:

input [1, 4, 5] and 2 (number of binations) should return:

[1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

input [1, 4, 5] and 3 should return:

[1, 1, 1], [1, 1, 4], [1, 1, 5], [1, 4, 4], [1, 4, 5], [4, 4, 4], [4, 4, 5], [5, 5, 5], [5, 5, 4], [5, 5, 1] (The order is not important).

I have been adjusting bination_k, it got me far enough that it worked with 2 but it didn't work when I provided 3 as a parameter.

const binations = getAllCombinations([1, 4, 5], 2);
// binations = [1, 1], [1, 4], [1, 5], [4, 4], [4, 5], [5, 5]

Any tips are wele!

• javascript
• arrays

Share Improve this question Follow edited May 13, 2021 at 10:26 AbsoluteBeginner 2,26333 gold badges1414 silver badges2424 bronze badges asked May 13, 2021 at 6:18 CemCem 5144 bronze badges 5

• Can you post what you have done to achieve with 2? – Yadab Commented May 13, 2021 at 6:35
• 1 Why is [1, 5, 5] not in your expected output? – Nick Commented May 13, 2021 at 6:39
• Yes, I have done several things but the simplest and the shortest way to achieve this was to change line 121 to tailbs = k_binations(set.slice(i), k - 1); @ bination_k – Cem Commented May 13, 2021 at 6:41
• 1 @Nick I see that I have missed that one, woops! I have edited my initial post and added that item in the expected list. – Cem Commented May 13, 2021 at 6:43
• Here is a dynamical programming solution with no recursion. Recursion in JS might result call stack overflow problems after a certain range. – Redu Commented May 13, 2021 at 8:21

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 5

The problem is monly referred to as k-binations with repetitions.

Here's a solution that relies on recursion to get the desired result:

const binations = (array, r) => {
  const result = [];
  const fn = (array, selected, c, r, start, end) => {
    if (c == r) {
      result.push([...selected]);
      return;
    }
    
    for (let i = start; i <= end; i++) {
      selected[c] = array[i];
      fn(array, selected, c + 1, r, i, end);
    }
  }
  
  fn(array, [], 0, r, 0, array.length - 1);
  return result;
}

console.log(binations([1, 4, 5], 3));

A modified version of the code you provided:

function getAllCombinations(arr, n) {
  if (n <= 0) return [];
  if (n === 1) return [...arr];

  return arr.reduce((acc, cur, i) => {
    const head = arr.slice(i, i + 1);
    const binations = getAllCombinations(arr.slice(i), n - 1)
      .map(x => head.concat(x));
    return [...acc, ...binations];
  }, []);
}

console.log(getAllCombinations([1, 4, 5], 2).join('|'));
console.log(getAllCombinations([1, 4, 5], 3).join('|'));

本文标签： javascriptGet all (number of) combinations of an arrayStack Overflow