So ermitteln Sie die Anzahl nicht leerer Teilmengen in JavaScript

Wie kann man bei einem gegebenen Element einer Sequenz, die aus Zahlen oder Zeichen besteht und wiederholte Werte haben kann, die Anzahl der nicht leeren Teilmengen ermitteln?

Zum Beispiel gibt es die Sequenz {1, 2, 3, 4} und ihre nicht leeren Teilmengen umfassen:

{ {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4},{3,4 }, {1 ,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}usw. 15 Artikel, und das leere Set ist nicht in der Statistik enthalten.

Ein weiteres Beispiel ist die Sequenz {a, b, c, d, d}, die wiederholte Werte enthält, dies jedoch aufgrund der Menge nicht der Fall ist wiederholbar, daher umfasst seine nicht leere Teilmenge:

{{a}, {b}, {c}, {d}, {a,b}, {a,c}, {a ,d }, {b,c}, {b,d},{c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c ,d }, {a,b,c,d}}, außerdem 15 Elemente, die wiederholt d haben entfernt worden.

Die herkömmliche Teilmengenmethode ist bei diesem Problem möglicherweise nicht nützlich, da die Länge der Sequenz aufgrund der Leistungsanforderungen 50 oder sogar mehr erreichen kann Verwenden Sie Rekursion, es wird zu lange dauern.

Glücklicherweise müssen wir nicht nach dem spezifischen Inhalt der Teilmenge fragen, sondern nur nach der Zahl, sodass wir eine Formel verwenden können.

Wenn eine Menge (nicht eine Folge) N Elemente hat, dann hat sie 2 NLeistungsteilmenge. Diese Teilmenge enthält die leere Menge und sich selbst. Wenn Sie also eine nicht leere Teilmenge wünschen, können Sie 2^N verwenden - 1 zum Berechnen.

Okay, hier kann dieses Problem in 2Schritte unterteilt werden:

1. Deduplizieren Sie die Sequenz

2. Verwenden Sie die Formel, um die Anzahl der nicht leeren Teilmengen zu berechnen

function estSubsets(arr) {
    var hash = {};
    for(var i=0;i<arr.length;i++){
        hash[arr[i]] = null;
    }
    arr = Object.keys(hash);
    return Math.pow(2,arr.length) - 1;
}

Das obige ist der detaillierte Inhalt vonSo ermitteln Sie die Anzahl nicht leerer Teilmengen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!