logo标签列表

在JS中寻找两个数组的所有排列组合

javascriptalgorithm
10

我正在尝试查找像这样的2个数组的每个排列：

// input
lowerWords = ['one', 'two', 'three' ] 
upperWords = [ 'ONE', 'TWO', 'THREE' ]

// output
keywords = {
  'one two three': true,
  'ONE two three': true,
  'ONE TWO three': true,
  'ONE TWO THREE': true,
  'ONE two THREE': true,
  'one TWO three': true,
  'one two THREE': true,
  'one TWO THREE': true,
}

它应该可以处理超过3个项，两个数组的长度始终相同。这是我的代码：

const keywords = {}
const lowerWords = ['one', 'two', 'three' ] 
const upperWords = [ 'ONE', 'TWO', 'THREE' ]
const wordCount = lowerWords.length

let currentWord = 0
let currentWords = [...upperWords]
while (currentWord < wordCount) {
  currentWords[currentWord] = lowerWords[currentWord]
  let keyword = currentWords.join(' ')
  keywords[keyword] = true
  currentWord++
}

currentWord = 0
currentWords = [...lowerWords]
while (currentWord < wordCount) {
  currentWords[currentWord] = upperWords[currentWord]
  let keyword = currentWords.join(' ')
  keywords[keyword] = true
  currentWord++
}

ONE TWO THREE: true
ONE TWO three: true
ONE two three: true
one TWO THREE: true
one two THREE: true
one two three: true
在您期望的答案中第3个和第9个是重复的。 - JackOfAshes - Mohit Gawande
@Tigger 不是，那些是2的组合，我需要每个项目的排列。 - Dave
@JackOfAshes-MohitGawande 是的，那是一个错误。 - Dave
你不是在寻找排列（它们与顺序有关），而是在寻找[one, ONE]、[two, TWO]和[three, THREE]的笛卡尔积。你可以通过转置输入来获得这些。 - Bergi
@Bergi 我不确定你的建议是否适用于任意输入（请参见我在Nina Scholz答案下的评论）。 - גלעד ברקן
6个回答
11

你可以对数组进行转置，得到一组对，然后获取所有对的组合。

const
    transpose = array => array.reduce((r, a) => a.map((v, i) => [...(r[i] || []), v]), []),
    combinations = array => array.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));

var lowerWords = ['one', 'two', 'three'],
    upperWords = ['ONE', 'TWO', 'THREE'],
    pairs = transpose([lowerWords, upperWords]),
    result = combinations(pairs);
    
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

（这个函数在处理 transpose([['ONE','TWO','THREE'],['one','two'], [1,2,3,4]]) 这种情况时会失败，与我的实现相比。） - גלעד ברקן
3
transpose 转置相同长度的数组。 - Nina Scholz
@גלעדברקן 不过，无论如何，从那个输入中得到什么输出并不清楚。 - Bergi
@Bergi 我实现了这样一个清晰度。 - גלעד ברקן
@גלעדברקן 嗯，使用转置的输入格式这样做确实没有意义。如果想要那种输出结果，应该只需调用 cartesian([['one', 'ONE', 1], ['two','TWO', 2], ['three', 3], [4]]) 即可。 - Bergi
1

我想试一试。我使用二进制获取可能的组合，因为这个问题需要一个基于2的解决方案：

const low = ["one", "two", "three"];
const up = ["ONE", "TWO", "THREE"];

const words = [low, up]
const len = words[0].length


function getCombinations(noOfArrays, len) {
  var temp, newCombo, combos = [];
  for (var i = 0; i < (noOfArrays ** len); i++) {
    temp = new Array(len).fill(0)
    newCombo = i.toString(noOfArrays).split('');
    newCombo.forEach((el, i) => temp[temp.length - newCombo.length + i] = +el);
    combos.push(temp);
  }
  return combos;
}

function setCombinations(combos) {
  return combos.map(combo => combo.map((el, i) => words[el][i]))
}


var combos = getCombinations(words.length, len)
combos = setCombinations(combos)


console.log(combos)

循环的解释：
1. temp = new Array(len).fill(0)
2. newCombo = i.toString(2).split("");
3. newCombo.forEach((el, i) => temp[temp.length - newCombo.length + i] = +el);
  1. 创建临时数组[0,0,0]
  2. 获取循环次数(i)并将其转换为二进制，例如:
1 -> 1
2 -> 10
3 -> 11
4 -> 100
etc...

然后将二进制拆分成数组100 -> [1,0,0]。

  1. 然后将每个元素推入新数组中。这会导致将1和2元素数组(10 -> [1,0])推到数组的末尾时出现问题。我使用temp.length - newCombo.length + i来解决这个问题。

该函数然后返回：

[ 0, 0, 0 ]
[ 0, 0, 1 ]
[ 0, 1, 0 ]
[ 0, 1, 1 ]
[ 1, 0, 0 ]
[ 1, 0, 1 ]
[ 1, 1, 0 ]
[ 1, 1, 1 ]

然后，我可以映射每个组合，并根据值获取每个数组并通过循环索引获取单词（'one'或'ONE'）。
请注意，此代码适用于超过一个数组的情况，只要这些数组的长度相同。
嗨，我已将此问题标记为“收藏”，以便稍后回来提供答案。我的答案与你的非常相似（我是独立想出来的，我发誓：））。我还添加了一个通用版本。希望你不介意。 - adiga
@adiga 没问题，英雄所见略同 :p 我喜欢这种方法，因为它非常可扩展，只需更改要将索引转换为的基数以及用户提供的数组数量即可。我也没有想到使用padStart，做得好！ - Kobe
1
你需要得到总共 2 ^ 3 种组合。如果你从这两个数组中创建一个二维矩阵，下表表示应该从哪一行取出项目。
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

如果您分析组合的索引，每个索引都是一个二进制数，从0到2 ^ 3，带有前导零。
所以，您可以：
  • 循环从0到8
  • 使用{{link1：toString（2）}}创建二进制数
  • 使用{{link2：padStart}}添加前导零
  • split每个数字以获取数组
  • 从matrix [digit-from-binary] [position-of-each-split]中获取每个项目
  • {{link3：join}}使用' '分隔符连接项目数组以获取key
  • 将键添加到输出对象
工作示例： 

function getAllCombinations(matrix) {
  const combinations = 2 ** 3,
        output = {};
  
  for(let i = 0; i < combinations; i++) {
      const key = i.toString(2)
                    .padStart(3, 0)
                    .split('')
                    .map((n, j) => matrix[n][j])
                    .join(" ")
                    
      output[key] = true;
  }
  
  return output
}

console.log(getAllCombinations([['one', 'two', 'three' ],[ 'ONE', 'TWO', 'THREE' ]]))

你可以将此推广到 m x n 矩阵。不需要将每个转换为二进制数，而是需要将其转换为 base-m 并使用 padStart 扩展到长度 n。 

function getAllCombinations(matrix) {
  const rows = matrix.length,
        columns = matrix[0].length,
        combinations = rows ** columns;

  return Array.from({ length: combinations },
    (_, i) => i.toString(rows)
                .padStart(columns, 0)
                .split('')
                .map((n, j) => matrix[n][j])
  )
}

console.log(JSON.stringify(
    getAllCombinations( [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ) // 3 x 3 matrix
));

console.log(JSON.stringify(
    getAllCombinations( [[1, 2], [3, 4], [5, 6], [7, 8]] ) // 4 x 2 matrix
));
.as-console-wrapper { max-height: 100% !important; top: 0; }

0

以下代码应该适用于您，它采用了递归的方法：

const lowerWords = ['one', 'two', 'three']
const upperWords = ['ONE', 'TWO', 'THREE']

let result = {};

function getCombinations(index, caseType, arr) {
  if (index == 3) {
    arr[index] = (caseType == 'lower' ? lowerWords : upperWords)[index];
    result[arr.join(' ')] = true
    return
  }
  arr[index] = (caseType == 'lower' ? lowerWords : upperWords)[index];
  getCombinations(index + 1, 'lower', arr);
  getCombinations(index + 1, 'upper', arr);
}
getCombinations(0, 'lower', [])
getCombinations(0, 'upper', [])

console.log('resultresult', result)

0

这是一个基于我的其他答案的通用版本，可以处理具有不同长度的变量数量输入数组：

const g = (arrs, i=0, comb=[]) =>
  !arrs.some(arr => i < arr.length)
  ? [comb]
  : arrs.reduce((acc, arr) => 
      i >= arr.length ? acc :
      acc.concat(g(arrs, i + 1, comb.slice().concat(arr[i])))
    , [])
    

// Example output
let input = [['ONE','TWO','THREE'], ['one','two'], [1,2,3,4]]

let str = ''
for (let line of g(input))
  str += JSON.stringify(line) + '\n'
console.log(str)

0
我们可以直接枚举它们。以下是一种算法：
If we've reached the end of
the list, return the combination
the current recursion branch is
building.

Otherwise, create a new branch
that picks the next item from B,
while the current branch picks
the next item from A.

JavaScript代码：

function f(A, B, i=0, comb=[]){
  return i == A.length
         ? [comb]
         : f(A, B, i + 1, comb.concat(A[i])).concat(
           f(A, B, i + 1, comb.slice().concat(B[i])))
}

console.log(JSON.stringify(f(['one','two','three'], ['ONE','TWO','THREE'])))

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接