Javascript - 在单个数组中生成所有元素组合(成对)

IT技术 javascript arrays algorithm combinations
2021-01-19 15:54:46

我已经看到了几个关于如何生成数组中元素的所有可能组合的类似问题。但是我很难弄清楚如何编写只输出组合的算法任何建议将不胜感激!

从以下数组开始(有 N 个元素):

var array = ["apple", "banana", "lemon", "mango"];

并得到以下结果:

var result = [
   "apple banana"
   "apple lemon"
   "apple mango"
   "banana lemon"
   "banana mango"
   "lemon mango"
];

我正在尝试以下方法,但这会导致所有可能的组合,而只是组合对。

var letters = splSentences;
var combi = [];
var temp= "";
var letLen = Math.pow(2, letters.length);

for (var i = 0; i < letLen ; i++){
    temp= "";
    for (var j=0;j<letters.length;j++) {
        if ((i & Math.pow(2,j))){ 
            temp += letters[j]+ " "
        }
    }
    if (temp !== "") {
        combi.push(temp);
    }
}
6个回答

以下是一些函数式编程解决方案:

使用 EcmaScript2019 的flatMap

var array = ["apple", "banana", "lemon", "mango"];

var result = array.flatMap(
    (v, i) => array.slice(i+1).map( w => v + ' ' + w )
);

console.log(result);

在引入flatMap(我在 2017 年的回答)之前,您会为了reduce[].concat(...)为了展平数组:

var array = ["apple", "banana", "lemon", "mango"];

var result = array.reduce( (acc, v, i) =>
    acc.concat(array.slice(i+1).map( w => v + ' ' + w )),
[]);

console.log(result);

或者:

var array = ["apple", "banana", "lemon", "mango"];

var result = [].concat(...array.map( 
    (v, i) => array.slice(i+1).map( w => v + ' ' + w ))
);

console.log(result);

添加一些扩展运算符以获得更多美感,而不是concat(). :D
2021-03-24 15:54:46
flatMap()为了没有子集的嵌套数组,最好使用第二个答案编写result = [...array.flatMap((v1,i) => array.slice(i+1).map(v2 => v1+' '+v1))]
2021-03-30 15:54:46
感谢您的评论,@Phrogz。我更新了我的答案。当我在 2017 年写这个答案时,flatMap还没有广泛使用。注意:这里不需要传播 的结果flatMap
2021-04-11 15:54:46

一种简单的方法是对数组执行双循环,在其中跳过i第二个循环中的第一个元素。

let array = ["apple", "banana", "lemon", "mango"];
let results = [];

// Since you only want pairs, there's no reason
// to iterate over the last element directly
for (let i = 0; i < array.length - 1; i++) {
  // This is where you'll capture that last value
  for (let j = i + 1; j < array.length; j++) {
    results.push(`${array[i]} ${array[j]}`);
  }
}

console.log(results);

用 ES5 重写:

var array = ["apple", "banana", "lemon", "mango"];
var results = [];

// Since you only want pairs, there's no reason
// to iterate over the last element directly
for (var i = 0; i < array.length - 1; i++) {
  // This is where you'll capture that last value
  for (var j = i + 1; j < array.length; j++) {
    results.push(array[i] + ' ' + array[j]);
  }
}

console.log(results);

尽管方案已经找到,我张贴在这里一般情况下找到所有组合大小的算法nm (m>n)元素。在您的情况下,我们有n=2m=4

const result = [];
result.length = 2; //n=2

function combine(input, len, start) {
  if(len === 0) {
    console.log( result.join(" ") ); //process here the result
    return;
  }
  for (let i = start; i <= input.length - len; i++) {
    result[result.length - len] = input[i];
    combine(input, len-1, i+1 );
  }
}

const array = ["apple", "banana", "lemon", "mango"];    
combine( array, result.length, 0);

result.length = 2对眼睛来说太苛刻了。同样遗憾的是该功能不是“自包含”(纯功能......)。
2021-04-01 15:54:46
你能提到这个算法的时间复杂度吗?
2021-04-05 15:54:46

就我而言,我想根据数组的大小范围获得如下组合:

function getCombinations(valuesArray: String[])
{

var combi = [];
var temp = [];
var slent = Math.pow(2, valuesArray.length);

for (var i = 0; i < slent; i++)
{
    temp = [];
    for (var j = 0; j < valuesArray.length; j++)
    {
        if ((i & Math.pow(2, j)))
        {
            temp.push(valuesArray[j]);
        }
    }
    if (temp.length > 0)
    {
        combi.push(temp);
    }
}

combi.sort((a, b) => a.length - b.length);
console.log(combi.join("\n"));
return combi;
}

例子:

// variable "results" stores an array with arrays string type
let results = getCombinations(['apple', 'banana', 'lemon', ',mango']);

控制台输出:

在此处输入图片说明

该函数基于以下文档的逻辑,更多信息请参见以下参考:https : //www.w3resource.com/javascript-exercises/javascript-function-exercise-3.php

if ((i & Math.pow(2, j)))

第一个值的每一位都与第二个值进行比较,如果匹配则视为有效,否则返回零且不满足条件。

在此处输入图片说明

嘿,请你解释一下,这段代码是做什么的? if ((i & Math.pow(2, j)))
2021-03-17 15:54:46
请考虑添加一些关于您的代码如何实现结果的注释,以便其他人更容易理解
2021-03-24 15:54:46
你能解释一下这部分代码在做什么吗? if ((i & Math.pow(2, j))) { temp.push(valuesArray[j]); }
2021-03-25 15:54:46
如果你喜欢单线,你可以试试这个Codepenconst combinations = (arr) => [...Array(2 ** arr.length - 1).keys()].map((n) => ((n + 1) >>> 0).toString(2).split("").reverse().map((n, i) => (+n ? arr[i] : false)).filter(Boolean)).sort((a, b) => (a.length > b.length ? 1 : -1)); console.log(combinations(["apple", "banana", "lemon", "mango"]));
2021-04-08 15:54:46
谢谢!对于你的建议
2021-04-12 15:54:46

我最终为这个问题写了一个通用的解决方案,它在功能上等同于nhnghia 的答案,但我在这里分享它,因为我认为它更容易阅读/遵循,并且也充满了描述算法的评论。


/**
 * Generate all combinations of an array.
 * @param {Array} sourceArray - Array of input elements.
 * @param {number} comboLength - Desired length of combinations.
 * @return {Array} Array of combination arrays.
 */
function generateCombinations(sourceArray, comboLength) {
  const sourceLength = sourceArray.length;
  if (comboLength > sourceLength) return [];

  const combos = []; // Stores valid combinations as they are generated.

  // Accepts a partial combination, an index into sourceArray, 
  // and the number of elements required to be added to create a full-length combination.
  // Called recursively to build combinations, adding subsequent elements at each call depth.
  const makeNextCombos = (workingCombo, currentIndex, remainingCount) => {
    const oneAwayFromComboLength = remainingCount == 1;

    // For each element that remaines to be added to the working combination.
    for (let sourceIndex = currentIndex; sourceIndex < sourceLength; sourceIndex++) {
      // Get next (possibly partial) combination.
      const next = [ ...workingCombo, sourceArray[sourceIndex] ];

      if (oneAwayFromComboLength) {
        // Combo of right length found, save it.
        combos.push(next);
      }
      else {
        // Otherwise go deeper to add more elements to the current partial combination.
        makeNextCombos(next, sourceIndex + 1, remainingCount - 1);
      }
        }
  }

  makeNextCombos([], 0, comboLength);
  return combos;
}

工作算法得到了广泛的解释,并具有非常明确的命名约定。
2021-03-17 15:54:46