生成数字数组中的有效数字组合 [英] Generate valid combinations of numbers in array of digits

问题描述

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

I’m trying to generate all valid combinations of numbers from an array of digits. Let’s assume we have the following:

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

我们需要输出以下内容：

We need to output something like this:

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，依此类推。

An invalid number would be 91, 497, 72 and so on.

我尝试过此操作，但对结果不满意：

I tried this but I’m not satisfied with the result:

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; }

有什么想法吗？

推荐答案

此代码满足您的要求：

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]
]

---

假设，预期结果不取决于顺序，空格表示二进制模式：

---

Assuming, the expected result does not depend on order, the spaces represent a binary pattern:

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

---

我们可以使用带有计数器的这种模式我们转换为二进制字符串。我们还用 0 填充该字符串，因此它始终保持4位数字长：

---

We can utilize this pattern with a counter that we convert to a binary string. We also pad that string with 0 so it always remains 4 digits long:

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

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

For n digits in arr, there are exactly 2^{n - 1} combinations, so we use:

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

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

This is an object that has a length property of 2^{arr.length - 1}.

我们将这两个元素合并为 Array.from 接受两个参数的调用：

We combine both those things into an Array.from call which accepts two arguments:

• 要变成数组的对象


• 一个函数用于映射每个插槽

将具有 length 属性的对象转换为数组表示我们创建的数组长度为 许多插槽。

Turning an object with a length property into an array means that we create an array with length many slots.

映射功能接受插槽的索引作为第二个参数。我们仅使用索引作为二进制数的计数器。

The mapping function accepts the index of a slot as the second parameter. We only use the index — as a counter for our binary number.

因此，最后是整个表达式：

So, finally this whole expression:

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"
]

---

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

---

We need to further map this to the final result:

.map((binary) => …)

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

For each array element, binary is one of the binary strings from the array above.

为了转弯将 0110 转换为 12,9,47 ，我们需要 map 超过 arr 。 arr 中的每个数字 num 后应跟， 位置，当 binary 为 1 时为位置：

In order to turn e.g. "0110" into something like "12,9,47", we need to map over arr as well. Every digit num from arr should be followed by , at position, iff binary is 1 at position:

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

表达式（Number（binary [position]）？，：）在指定的位置计算 binary 位置为数字。如果它是 truthy ，即除 0 以外的其他值，则计算为， ，如果 falsy ，即 0 ，其结果为 。

The expression (Number(binary[position]) ? "," : "") evaluates binary at the specified position as a number. If it’s truthy, i.e. anything but 0, it evaluates to ",", if it’s falsy, i.e. 0, it evaluates to "".

所以中间数组看起来像 [ 1， 2，， 9，， 4， 7] 。所有这些都被合并到 12,9,47 。

So an intermediate array would look like ["1", "2,", "9,", "4", "7"]. All of this is joined together to "12,9,47".

然后是 JSON.parse（ [ + … +]）它将被视为并解析为数组，因此变成 [12，9，47] 。由于这些步骤适用于每个二进制字符串，因此您将得到最终结果。

Then, with JSON.parse("[" + … + "]") it’s being treated and parsed as an array, so it turns into [12, 9, 47]. Since these steps are applied for each binary string, you’ll end up with the final result.

• 2 **（arr.length-1）可以替换为 Math.pow（2，arr.length-1）如果不支持ECMAScript 7。


• {length：2 **（arr.length-1）} 可以替换为 new Array（2 **（arr.length-1））。


• （ Number（binary [position]）？，：）可以替换为 [，，] [Number（binary [position]）] 。在这种情况下，评估的数字将用作临时数组的索引。

• 2 ** (arr.length - 1) can be replaced by Math.pow(2, arr.length - 1) if ECMAScript 7 is not supported.
• {length: 2 ** (arr.length - 1)} can be replaced by new Array(2 ** (arr.length - 1)).
• (Number(binary[position]) ? "," : "") can be replaced by ["", ","][Number(binary[position])]. In this case the evaluated number will be used as an index for a temporary array.

这篇关于生成数字数组中的有效数字组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！