Wie finde ich alle Teilmengen einer Menge in JavaScript?

8

Ich muss alle möglichen Teilmengen eines Arrays bekommen.

Sagen Sie, ich habe das:

%Vor%

Wie bekomme ich das?

%Vor%

Ich bin an allen Teilmengen interessiert. Beziehen Sie sich für Untergruppen bestimmter Länge auf die folgenden Fragen:

  • Teilmengen der Größe n finden: 1 , < a href="https://stackoverflow.com/questions/37892738/generate-subsets-of-length-n"> 2
  • Finden von Teilmengen der Größe & gt; 1: 1
le_m 13.03.2017, 21:35
quelle

4 Antworten

10

Wir können dieses Problem für eine Teilmenge des Eingabearrays lösen, beginnend mit offset . Dann gehen wir zurück, um eine vollständige Lösung zu erhalten.

Mithilfe einer Generatorfunktion können wir Teilmengen mit einer Konstanten durchlaufen Speichernutzung:

%Vor%

Die Laufzeitkomplexität ist proportional zur Anzahl der Lösungen (2ⁿ) mal der durchschnittlichen Länge pro Lösung (n / 2) = O (n2ⁿ) .

    
le_m 13.03.2017, 21:35
quelle
5

Eine andere einfache Lösung.

%Vor% %Vor%
    
Nina Scholz 13.03.2017 21:54
quelle
5

Hier ist eine weitere sehr elegante Lösung ohne Schleifen oder Rekursion, die nur die Map verwendet und die nativen Array-Funktionen reduziert.

%Vor%
    
MennyMT 06.11.2017 23:31
quelle
3

Sie können das Powerset leicht aus einem Array generieren, indem Sie etwas wie folgt verwenden:

%Vor%

In der Hauptschleife der Funktion werden Teilmengen erstellt und dann in das Array result geschoben.

    
Angelos Chalaris 13.03.2017 21:55
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Halten Sie die gleiche Dummy-Variable in Trainings- und Testdaten