Comment trouver le nombre de sous-ensembles non vides en JavaScript

Étant donné un élément d'une séquence, qui est constitué de nombres ou de caractères et peut avoir des valeurs répétées, comment trouver le nombre de sous-ensembles non vides ?

Par exemple, il y a la séquence {1, 2, 3, 4}, et ses sous-ensembles non vides incluent :

{ {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}}etc. 15 éléments, et l'ensemble vide n'est pas inclus dans les statistiques.

Un autre exemple est la séquence {a, b, c, d, d>, qui contient des valeurs répétées, mais parce que l'ensemble n'est pas répétable, Son sous-ensemble non vide comprend donc :

{{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}}, également 15 éléments, le d répété a été supprimé.

La méthode de sous-ensemble traditionnelle peut ne pas être utile dans ce problème, en raison des exigences de performances, la longueur de la séquence peut atteindre 50 ou même plus, si vous utilisez la récursion, cela prendra trop de temps.

Heureusement, nous n'avons pas besoin de demander le contenu spécifique du sous-ensemble, seulement le numéro, nous pouvons donc utiliser une formule.

Si un ensemble (notez pas une séquence) a N éléments, alors il a 2 Nsous-ensemble de puissance. Ce sous-ensemble contient l'ensemble vide et lui-même, donc si vous voulez un sous-ensemble non vide, vous pouvez utiliser 2^N - 1 pour calculer.

Bon, ici, ce problème peut être divisé en 2 étapes :

1. Dédupliquer la séquence

2. Utilisez la formule pour calculer le nombre de sous-ensembles non vides

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!