Создание всех комбинаций массива

Я генерирую все комбинации массива, поэтому, например, ["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"));
56 голосов | спросил Incognito 19 MonEurope/Moscow2011-12-19T21:34:08+04:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2011 21:34:08 +0400 2011, 21:34:08

8 ответов


44

Рекурсивное решение, первоначально увиденное здесь , но измененное в соответствии с вашими требованиями (и посмотрите немного больше 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")

Вывод:

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

Что касается имени : не называйте его permutations; перестановка - это расположение всех исходных элементов (из которых должно быть n! total). Другими словами, он уже имеет точный смысл; не излишне перегружайте его. Почему бы просто не назвать его комбинациями combinations?

ответил Wayne Burkett 20 TueEurope/Moscow2011-12-20T20:46:09+04:00Europe/Moscow12bEurope/MoscowTue, 20 Dec 2011 20:46:09 +0400 2011, 20:46:09
23

Вы можете сделать это рекурсивно:

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"]
ответил Guffa 21 WedEurope/Moscow2011-12-21T16:38:51+04:00Europe/Moscow12bEurope/MoscowWed, 21 Dec 2011 16:38:51 +0400 2011, 16:38:51
11

Я предпочитаю ваш подход намного лучше, чем рекурсивный подход, особенно когда обрабатываются большие списки.

Некоторые примечания:

  • Мне нравится имя powerSet согласно @ 200_success
  • Вам не нужно проверять combination.length !== 0, если вы начинаете с i=1
  • Если вы вызываете функцию permutations, то вы не должны вызывать список, который вы создаете combinations, что запутывает
  • Можно кэшировать list.length, что является общей оптимизацией

С фигурными фигурными скобками вы можете:

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

без них это может выглядеть так:

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;
}
ответил konijn 21 Jpm1000000pmTue, 21 Jan 2014 20:00:08 +040014 2014, 20:00:08
9

Альтернативой является создание trie, а затем переход в trie для генерации комбинации. Есть две рекурсивные функции, и я приурочен это примерно на порядок медленнее, чем ваша итеративная версия, но я думал, что вы можете найти это интересным, тем не менее. (Как только 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']);

P.S. Ваша функция permutations выводит массив массивов, а не массив строк, подобных вашему примеру, в верхней части вашего вопроса. Я выводил массив строк с помощью моей функции combinations.

ответил FizzyTea 20 TueEurope/Moscow2011-12-20T05:26:25+04:00Europe/Moscow12bEurope/MoscowTue, 20 Dec 2011 05:26:25 +0400 2011, 05:26:25
5

Более быстрый способ сделать Math.pow( 2, x ), если x является целым числом, является 1 << x.

Хорошим именем для функции может быть также «array_permutator».

ответил Mike Nakis 20 TueEurope/Moscow2011-12-20T00:04:43+04:00Europe/Moscow12bEurope/MoscowTue, 20 Dec 2011 00:04:43 +0400 2011, 00:04:43
4

В этом случае нерекурсивное решение легче понять, ИМХО:

 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];
    // …
}

â € | или мы просто создаем статическую копию результатов и перебираем их.

ответил Mathias Bynens 9 FebruaryEurope/MoscowbThu, 09 Feb 2017 10:52:09 +0300000000amThu, 09 Feb 2017 10:52:09 +030017 2017, 10:52:09
3

У меня есть два решения для этого: один из двоичных и один рекурсивный;

Двоичный файл будет выглядеть следующим образом:

 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"])));
ответил Redu 25 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSun, 25 Sep 2016 20:41:38 +0300 2016, 20:41:38
0

Попробуйте этот простой.

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

Это 8 возможных значений. Тот же метод используется здесь, но для 1 здесь характер и для 0 ничего. Таким образом, число возможных комбинаций равно (2 ^ n) -1.

ответил kruttinangopal 1 PMpWed, 01 Apr 2015 20:14:05 +030014Wednesday 2015, 20:14:05

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132