生成数组的所有组合

我正在生成数组的所有组合，因此，例如，["a", "b", "c", "d"]将生成：

[
  "a",    "b",    "ab",   "c",    "ac",
  "bc",   "abc",  "d",    "ad",   "bd",
  "abd",  "cd",   "acd",  "bcd",  "abcd"
]

这是我编写的完成此任务的代码。

我想知道是否有更好的方法，因为两次遍历数组就像我在作弊一样，或者代码的复杂性在计算上比需要的要昂贵得多。。

另外，一个函数的名称，该函数需要一个数组并返回组合，这叫什么？组合器似乎不合适。

var letters = ["a", "b", "c", "d"];
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);
    }
}

console.log(combi.join("\n"));

#1 楼

递归解决方案，最初在这里看到，但已进行了修改以满足您的要求（并且看起来有点JavaScript-y）：
/>

function combinations(str) {
    var fn = function(active, rest, a) {
        if (!active && !rest)
            return;
        if (!rest) {
            a.push(active);
        } else {
            fn(active + rest[0], rest.slice(1), a);
            fn(active, rest.slice(1), a);
        }
        return a;
    }
    return fn("", str, []);
}

输出：

combinations("abcd")

关于名称：不要命名permutations;排列是所有原始元素的排列（总共应为n!）。换句话说，它已经具有精确的含义。不要不必要地使其过载。为什么不简单地将其命名为combinations？

\ $ \ begingroup \ $
跌跌撞撞回到这里，不知道为什么我最初没有指出“组合”也有一个现有的数学定义en.wikipedia.org/wiki/Combination
\ $ \ endgroup \ $
–韦恩
13年10月10日在6:41

\ $ \ begingroup \ $
“所有可能的组合”也可以称为“功率集”。
\ $ \ endgroup \ $
– 200_success
2014年1月2日在17:28

\ $ \ begingroup \ $
仔细检查后，动力装置应包括空弦。我不确定减去空字符串该怎么称呼电源。
\ $ \ endgroup \ $
– 200_success
2014年1月21日在17:24

\ $ \ begingroup \ $
我正在尝试创建我的babel库，这很方便xD
\ $ \ endgroup \ $
–凯尔
2015年10月1日，11：36

\ $ \ begingroup \ $
代替子序列（尽管从技术上讲，它也包括空序列），而不是“幂集”（约集，无需关心顺序），而是一个更好的名称。
\ $ \ endgroup \ $
–贝尔吉
16年7月31日在23:24

#2 楼

您可以递归执行：

function getCombinations(chars) {
  var result = [];
  var f = function(prefix, chars) {
    for (var i = 0; i < chars.length; i++) {
      result.push(prefix + chars[i]);
      f(prefix + chars[i], chars.slice(i + 1));
    }
  }
  f('', chars);
  return result;
}

用法：

var combinations = getCombinations(["a", "b", "c", "d"]);

结果：

["a","ab","abc","abcd","abd","ac","acd","ad","b","bc","bcd","bd","c","cd","d"]

\ $ \ begingroup \ $
...稍作调整，以返回数组集函数getCombinations（array）{var result = []; var f = function（prefix = []，array）{for（var i = 0; i \ $ \ endgroup \ $
–mc。
19年6月3日在21:01

\ $ \ begingroup \ $
最好，最易读的解决方案！
\ $ \ endgroup \ $
– karthikaruna
19年8月17日在11:59

#3 楼

我更喜欢您的方法，而不是递归方法，尤其是在处理较大的列表时。

一些注意事项： 200_success
如果您以powerSet开头，则无需检查combination.length !== 0

如果调用函数i=1，则不应调用构建的列表permutations，这令人困惑
您可以缓存combinations，这是常见的优化方法

使用花括号，您可以拥有：

function powerSet( list ){
    var set = [],
        listSize = list.length,
        combinationsCount = (1 << listSize),
        combination;

    for (var i = 1; i < combinationsCount ; i++ ){
        var combination = [];
        for (var j=0;j<listSize;j++){
            if ((i & (1 << j))){
                combination.push(list[j]);
            }
        }
        set.push(combination);
    }
    return set;
}

没有它们，它看起来像this：

function powerSet( list ){
    var set = [],
        listSize = list.length,
        combinationsCount = (1 << listSize);

    for (var i = 1; i < combinationsCount ; i++ , set.push(combination) )
        for (var j=0, combination = [];j<listSize;j++)
            if ((i & (1 << j)))
                combination.push(list[j]);
    return set;
}

\ $ \ begingroup \ $
第一个版本很棒。第二个则差强人意。
\ $ \ endgroup \ $
– 200_success
2014年1月21日在17:21

\ $ \ begingroup \ $
第二个版本太高尔夫了，但是我沉迷于掉冰壶。
\ $ \ endgroup \ $
– konijn
2014年1月21日17:39

\ $ \ begingroup \ $
我喜欢这个答案。如果我想改进（不需要），我会说：1.我将使用powerSet而不是set，或者至少使用一些不那么重载的含义。 2.我会避免使用第二个嵌套循环，因为大多数内部循环都没有使用。我认为回忆会很适合（jsfiddle.net/ynotravid/kkwfnpu7/20）。
\ $ \ endgroup \ $
–否
'18 Apr 10在23:30在

\ $ \ begingroup \ $
问题是，仅当它应该生成abcd，acbd，adbc ...等等时，才生成abcd，直到所有16个置换用尽并对3个字母和2个字母以及单字母字母进行相同的操作
\ $ \ endgroup \ $
– PirateApp
19年7月3日在12:33

#4 楼

另一种方法是先构建一个特里树，然后遍历该特里树以生成组合。有两个递归函数，并且我给它定的时间
比您的迭代版本慢大约一个数量级，
但是我想您可能仍然觉得它很有趣。（一旦JS获得
尾部调用优化，某些递归方法将运行得更快。）

var follows, combinations;

follows = function(a){
    return a.map(function(item, i){
        return [item, follows(a.slice(i+1))];
    });
};

combinations = function(a){
    var combs = function(prefix, trie, result){
        trie.forEach(function(node, i){
            result.push(prefix + node[0]);
            combs(prefix + node[0], node[1], result);
        });
        return result;
    };
    return combs('', follows(a), []);
};

combinations(['a','b','c','d']);

PS。您的permutations函数输出数组数组，而不是问题顶部的示例数组。我已经使用我的combinations函数输出了一个字符串数组。

#5 楼

在这种情况下，非递归解决方案更容易理解，恕我直言：

 const powerset = (array) => { // O(2^n)
	const results = [[]];
	for (const value of array) {
		const copy = [...results]; // See note below.
		for (const prefix of copy) {
			results.push(prefix.concat(value));
		}
	}
	return results;
};

console.log(
	powerset(['A', 'B', 'C'])
);

// [ [],
//   [ 'A' ],
//   [ 'B' ],
//   [ 'A', 'B' ],
//   [ 'C' ],
//   [ 'A', 'C' ],
//   [ 'B', 'C' ],
//   [ 'A', 'B', 'C' ] ]

由于results在循环体内扩展，我们无法使用for-of对其进行迭代-这样做也会对新添加的元素进行迭代，从而导致无限循环。我们只想在循环开始时迭代results中的元素，即索引0直到results.length - 1。因此，我们要么将原始length缓存在一个变量中，然后使用它，即

 for (let index = 0, length = results.length; index < length; index++) {
    const prefix = results[index];
    // …
}

...…或者我们只是创建结果的静态副本并对其进行迭代。

#6 楼

如果x是整数，则执行Math.pow( 2, x )的更快方法是1 << x。

该函数的好名字也可能是'array_permutator'。

\ $ \ begingroup \ $
我的主要问题是使用if-checking进行这种双重循环。
\ $ \ endgroup \ $
–隐身
2011-12-19 20:33

\ $ \ begingroup \ $
是的，我知道。我无法提出消除嵌套循环的想法。因此，请等待，看看是否有人在想什么。
\ $ \ endgroup \ $
–迈克·纳基斯（Mike Nakis）
2011年12月19日20:39

#7 楼

我对此有两种解决方案，一种是二进制的，一种是递归的；

二进制将如下；

 function getSubArrays(arr){
  var len = arr.length,
     subs = Array(Math.pow(2,len)).fill();
  return subs.map((_,i) => { var j = -1,
                                 k = i,
                               res = [];
                             while (++j < len ) {
                               k & 1 && res.push(arr[j]);
                               k = k >> 1;
                             }
                             return res;
                           }).slice(1);
}

console.log(JSON.stringify(getSubArrays(["a","b","c","d"])));

递归如下：

 function getSubArrays(arr){
  if (arr.length === 1) return [arr];
  else {
  	subarr = getSubArrays(arr.slice(1));
  	return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]);
  }
}

console.log(JSON.stringify(getSubArrays(["a","b","c","d"])));

#8 楼

在这一系列答案中，我认为我们缺少传统的递归解决方案，该解决方案强调了递归算法的优雅之处：

难以理解：

const subSeq = (s) => {
    if (s.length == 1) return ['', s] 

    // All the subSeq without the first char:
    const ss = subSeq(s.slice(1))

    // Return both those with and those without the first char
    return [...ss.map(ch => s[0] + ch), ...ss]
}

答案中包含空字符串：

const subSeq = (s) => s.length == 1 
    ? ['', s] 
    : (ss=subSeq(s.slice(1)), 
       [...ss.map(ch => s[0] + ch), ...ss])

#9 楼

试试这个简单的方法。

var input="abcde";
var len=input.length;
var str = "";
var p=Math.pow(2,len);
var twoPower;
for(i = 0; i < p; i++) 
{
    twoPower=p;
    for(j=0;j<len;j++)
    {
        twoPower=twoPower/2;
        str+= (i & twoPower ? input.charAt(j) : "");
    }
    str+="\n";
}
alert(str);

它的工作方法是如此简单。
如果必须找到给定位长的所有二进制数，该怎么办？
是8 4 2 1方法。
如果位长为3，则可能的数字是
/>
4 2 1

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0 0
1 1 1

这些是8个可能的值。
此处使用相同的方法，但1表示字符，不包含0。因此，可能的组合数量为（2 ^ n）-1。

\ $ \ begingroup \ $
欢迎使用CodeReview。由于您的代码不过是代码转储而已，因此请提供上下文，以说明OP应该接受您的建议的原因/将其与他已经做的事情区分开的地方。
\ $ \ endgroup \ $
–莱加托
2015年4月1日在17:21

编程黑洞网