Generieren aller Kombinationen eines Arrays

90987
Incognito

Ich generiere alle Kombinationen eines Arrays, also beispielsweise ["a", "b", "c", "d"]:

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

Hier ist der Code, den ich geschrieben habe, um diese Aufgabe zu erledigen.

Was ich gerne wissen würde, ist, wenn es einen besseren Weg gibt, da das zweimalige Durchlaufen des Arrays sich anfühlt, als würde ich betrügen, oder die Komplexität des Codes ist viel rechenintensiver, als es sein muss.

Der Name einer Funktion, die ein Array verwendet und die Kombinationen zurückgibt, wie könnte dies heißen? Kombinator scheint unangemessen.

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"));
Antworten
61

9 Antworten auf die Frage

48
Wayne Burkett

Eine rekursive Lösung, die ursprünglich hier zu sehen war, aber an Ihre Anforderungen angepasst wurde (und ein bisschen mehr JavaScript-y sieht):

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, []);
}

Prüfung:

combinations("abcd")

Ausgabe:

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

Bezüglich des Namens : Nenne ihn nicht permutations; Eine Permutation ist eine Anordnung aller ursprünglichen Elemente (von denen es n!insgesamt sein sollte). Mit anderen Worten, es hat bereits eine genaue Bedeutung; Überladen Sie es nicht unnötig. Warum nennst combinationsdu es nicht einfach ?

Stolperte hier zurück und habe keine Ahnung, warum ich ursprünglich nicht darauf hingewiesen hatte, dass "Kombination" auch eine vorhandene mathematische Definition hat http://en.wikipedia.org/wiki/Combination Wayne Burkett vor 6 Jahren 0
"Alle möglichen Kombinationen" können auch als "Power Set" bezeichnet werden. 200_success vor 6 Jahren 5
Bei näherer Betrachtung sollte ein [Power Set] (http://en.wikipedia.org/wiki/Power_set) die leere Zeichenfolge enthalten. Ich bin mir nicht sicher, was ich als Power-Set ohne die leere Zeichenfolge bezeichnen soll. 200_success vor 6 Jahren 3
Ich versuche, meine Bibliothek von Babel zu erstellen, und das war praktisch xD Kyle vor 4 Jahren 1
Anstelle von "Power Set" (was sich auf Mengen bezieht, ohne auf Ordnung zu achten), wäre ein noch besserer Name ["Untersequenzen"] (https://en.wikipedia.org/wiki/Subsequence) (obwohl dies technisch gesehen das beinhaltet leere Sequenz auch). Bergi vor 3 Jahren 0
24
Guffa

Sie können es rekursiv tun:

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

Verwendungszweck:

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

Ergebnis:

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

Ich bevorzuge Ihren Ansatz viel besser als einen rekursiven Ansatz, insbesondere wenn größere Listen verarbeitet werden.

Einige Notizen:

  • Ich mag den Namen powerSetwie in @ 200_success
  • Sie müssen nicht prüfen, combination.length !== 0ob Sie mit beginneni=1
  • Wenn Sie die Funktion aufrufen permutations, sollten Sie die von Ihnen erstellte Liste nicht aufrufen combinations, das ist verwirrend
  • Sie könnten zwischenspeichern list.length, das ist eine übliche Optimierung

Mit geschweiften Klammern können Sie dann Folgendes haben:

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

Ohne sie könnte es so aussehen:

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;
}
Die erste Version ist ausgezeichnet. Der zweite ist bei weitem nicht so gut. 200_success vor 6 Jahren 1
Die 2. Version ist zu Golfisch, aber ich bin süchtig danach, Curlys fallen zu lassen. konijn vor 6 Jahren 3
Ich mag diese Antwort. Wenn ich versuchen würde, mich zu verbessern (was nicht erforderlich ist), würde ich sagen: 1. Ich würde anstelle von `set`` powerSet` oder zumindest etwas mit weniger überlasteter Bedeutung verwenden. 2. Ich würde die zweite verschachtelte Schleife vermeiden, da die meisten inneren Schleifen nicht verwendet werden. Ich denke, das Memoization wäre dafür gut (https://jsfiddle.net/ynotravid/kkwfnpu7/20/). Ynot vor einem Jahr 0
9
FizzyTea

Eine Alternative ist, einen Trie zu bauen und dann den Trie zu laufen, um die Kombinationen zu erzeugen. Es gibt zwei rekursive Funktionen, und ich habe es ungefähr eine Größenordnung langsamer als Ihre iterative Version festgelegt, aber ich dachte, Sie könnten es trotzdem interessant finden. (Sobald JS die Rückrufoptimierung erhält, laufen einige rekursive Ansätze schneller.)

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: Ihre permutationsFunktion gibt ein Array von Arrays aus, kein Array von Strings wie in Ihrem Beispiel oben in Ihrer Frage. Ich habe mit meiner combinationsFunktion ein Array von Strings ausgegeben .

5
Mike Nakis

Ein viel schnellerer Weg, Math.pow( 2, x )wenn x eine ganze Zahl ist 1 << x.

Ein guter Name für die Funktion könnte auch 'array_permutator' sein.

Mein Hauptanliegen ist diese Doppelschleife mit der `if`-Prüfung. Incognito vor 8 Jahren 0
Ja ich verstehe das. Ich kann mir keine Idee für die Beseitigung der geschachtelten Schleife vorstellen. Warten Sie also ab, ob jemand an etwas denkt. Mike Nakis vor 8 Jahren 0
5
Mathias Bynens

In diesem Fall ist eine nicht rekursive Lösung einfacher zu verstehen, IMHO:

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

Da resultsder Loop-Körper innerhalb des Schleifenkörpers erweitert wird, können wir ihn nicht mit iterieren. for-ofDies würde auch die neu hinzugefügten Elemente iterieren, was zu einer unendlichen Schleife führt. Wir wollen nur die Elemente durchlaufen, resultsdie sich zu Beginn der Schleife befinden, dh Indizes 0bis results.length - 1. Also zwischenspeichern wir das Original entweder lengthin einer Variablen und verwenden das, dh

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

â € ¦ oder wir erstellen einfach eine statische Kopie der Ergebnisse und iterieren darüber.

3
Redu

Ich habe zwei Lösungen dafür, eine binär und eine rekursiv;

Die binäre wäre wie folgt;

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

Und das Rekursive ist wie folgt;

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

0
kruttinangopal

Versuchen Sie es mit diesem einfachen.

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

Die Arbeitsmethode ist so einfach. Was würden Sie tun, wenn Sie alle Binärzahlen für eine bestimmte Bitlänge finden müssen? Ja die 8 4 2 1-Methode. wenn die Bitlänge 3 ist, sind mögliche Zahlen möglich

4 2 1

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

Dies sind die 8 möglichen Werte. Die gleiche Methode wird hier verwendet, aber für 1 ist hier ein Zeichen und für 0 nichts. Die Anzahl möglicher Kombinationen ist also (2 ^ n) -1.

Willkommen bei CodeReview. Da es sich bei Ihrem Code um etwas mehr als einen Code-Dump handelt, geben Sie bitte an, warum das OP Ihren Vorschlag annehmen sollte / was es von dem unterscheidet, was er bereits tut. Legato vor 5 Jahren 2
0
ndp

Ich denke, in dieser Sammlung von Antworten fehlt die traditionelle rekursive Lösung, die die Eleganz eines rekursiven Algorithmus unterstreicht:

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

oder genauer gesagt, aber vielleicht schwerer zu folgen:

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

fügt die leere Zeichenfolge in die Antwort ein:

subSeq('abcd')
=> ["abc", "abcd", "ab", "abd", "ac", "acd", "a", "ad", "bc", "bcd", "b", "bd", "c", "cd", "", "d"]