javascript - 在数字数组中生成有效的数字组合

Question

我正在尝试从数字数组中生成所有有效的数字组合。假设我们有以下内容:

let arr = [1, 2, 9, 4, 7];

我们需要输出这样的东西:

1 2 9 4 7
1 2 9 47
1 2 94 7
1 2 947
1 29 4 7
1 29 47
1 294 7
1 2947
12 9 4 7
12 9 47
12 94 7
12 947
129 4 7
129 47
1294 7
12947

无效数字为 91、497、72 等等。

我试过了，但我对结果不满意:

const combination = (arr) => {

  let i, j, temp;
  let result = [];
  let arrLen = arr.length;
  let power = Math.pow;
  let combinations = power(2, arrLen);

  for (i = 0; i < combinations; i += 1) {
    temp = '';

    for (j = 0; j < arrLen; j++) {
      if ((i & power(2, j))) {
        temp += arr[j];
      }
    }
    result.push(temp);
  }
  return result;
}

const result = combination([1, 2, 9, 4, 7]);
console.log(result);

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

有什么想法吗？

Answer 1

这段代码做你想做的:

const arr = [1, 2, 9, 4, 7],
  result = Array.from({length: 2 ** (arr.length - 1)}, (_, index) => index.toString(2).padStart(arr.length - 1, "0"))
    .map((binary) => JSON.parse("[" + arr.map((num, position) => num + (Number(binary[position]) ? "," : "")).join("") + "]"));

console.log(result);

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

结果是:

[
  [12947],
  [1294, 7],
  [129, 47],
  [129, 4, 7],
  [12, 947],
  [12, 94, 7],
  [12, 9, 47],
  [12, 9, 4, 7],
  [1, 2947],
  [1, 294, 7],
  [1, 29, 47],
  [1, 29, 4, 7],
  [1, 2, 947],
  [1, 2, 94, 7],
  [1, 2, 9, 47],
  [1, 2, 9, 4, 7]
]

---

假设，预期结果不依赖于顺序，空格代表二进制模式:

12947     => 0000
1294 7    => 0001
129 47    => 0010
…
1 29 47   => 1010
…
1 2 9 4 7 => 1111

---

我们可以将此模式与我们转换为二进制字符串的计数器一起使用。我们还用 0 填充该字符串，因此它始终保持 4 位长:

index.toString(2).padStart(arr.length - 1, "0")

对于 arr 中的 n 个数字，恰好有 2^{n - 1} 种组合，因此我们使用:

{length: 2 ** (arr.length - 1)}

这是一个 length 属性为 2^{arr.length - 1} 的对象。

我们将这些东西组合成一个 Array.from接受两个参数的调用:

• 一个对象变成一个数组
• 映射每个插槽的函数

将具有 length 属性的对象转换为数组意味着我们创建一个具有 length 多个槽的数组。

映射函数接受槽的索引作为第二个参数。我们只使用索引 —— 作为我们二进制数的计数器。

所以，最后整个表达式:

Array.from({length: 2 ** (arr.length - 1)}, (_, index) => index.toString(2).padStart(arr.length - 1, "0"))

评估为以下数组:

[
  "0000",
  "0001",
  "0010",
  "0011",
  "0100",
  "0101",
  "0110",
  "0111",
  "1000",
  "1001",
  "1010",
  "1011",
  "1100",
  "1101",
  "1110",
  "1111"
]

---

我们需要进一步将其映射到最终结果:

.map((binary) => …)

对于每个数组元素，binary 是上述数组中的二进制字符串之一。

为了转向，例如"0110" 变成类似 "12,9,47" 的东西，我们还需要 map over arr . arr 中的每个数字 num 都应在 position 后跟 ,，iff binary在位置是1:

arr.map((num, position) => num + (Number(binary[position]) ? "," : "")).join("")

表达式 (Number(binary[position]) ? ",": "") 将指定位置的 binary 计算为数字。如果它是 truthy，即除 0 之外的任何值，它的计算结果为 ","，如果它是 falsy，即 0，它的计算结果为 ""。

因此中间数组看起来像 ["1", "2,", "9,", "4", "7"]。所有这些都连接到 "12,9,47"。

然后，使用 JSON.parse("["+ … + "]") 它被当作一个数组来处理和解析，所以它变成了 [12, 9, 47]。由于这些步骤适用于每个二进制字符串，因此您最终会得到最终结果。

---

如果不支持 ECMAScript 7，
• 2 ** (arr.length - 1) 可以替换为 Math.pow(2, arr.length - 1)。
• {length: 2 ** (arr.length - 1)}可以替换为new Array(2 ** (arr.length - 1))。
• (Number(binary[position]) ? ",": "") 可以替换为 ["", ","][Number(binary[position])] 。在这种情况下，评估的数字将用作临时数组的索引。