masques binaires pour des sous-ensembles de deux ensembles différents

Question

j'ai deux ensembles -

set1 - {i1, i2, i3 ...} IN1

set2 - {k1, k2, k3 ... kN2}

Pour un ensemble unique de n éléments, je peux représenter tous les sous-ensembles possibles en utilisant les masques de bits 0-2^n -1. De même, comment puis-je représenter -

Sous-ensemble possible de set1 et set2, où au moins 1 élément provient de l'ensemble différent.

par exemple
{i1, i2, k1} est valide

mais {i1, i2} - invalide car il n'a pas de point set2.

Je suis en train de générer deux choses -

1. Type d'une équation qui peut me donner un compte de tous les sous-ensembles, comme nous avons 2 sous-ensembles^n pour un seul n éléments fixés.

2. Codage de bits/masques à l'aide desquels je peux représenter le type de sous-ensembles ci-dessus.

Answer 1

Cela sera plus facile si nous introduisons quelques ensembles d'intérêt supplémentaires. Appelons les deux ensembles d'entrée S1 et S2; nous définirons les ensembles L, C et R (pour gauche, centre et droite). Pensez à ceux-ci comme étant le diagramme de Venn. Donc, définissons L = S1 \ S2, les éléments de S1 qui ne sont pas du tout S2; C = S1 ∩ S2, les éléments qui sont à la fois dans S1 et S2, et R = S2 \ S1. Ecrivez aussi l, c et r pour les tailles de ces ensembles, respectivement.

Maintenant, nous sommes prêts à répondre à la question 1: combien de sous-ensembles de S1 ∪ S2 ont un élément de S1 et ont un élément de S2? Il y a deux cas à considérer: soit nous avons un sous-ensemble avec un élément dans C (qui satisfait à la fois les éléments "un élément de S1" et "un élément de S2"), soit nous n'avons pas d'éléments dans C et au moins dans le premier cas, il y a (2^c - 1) sous-ensembles non vides de C, et 2^(l + r) sous-ensembles du reste, donc il y a (2^c - 1) * 2^(l + r) définit dans ce cas. Dans le second cas, il y a 2^l - 1 sous-ensembles non vides de L et 2^r - 1 sous-ensembles non vides de R, donc il y a (2^l - 1) * (2^r - 1) sous-ensembles dans ce cas. En additionnant les deux cas, nous avons un total de 2^(c + l + r) - 2^l - 2^r sous-ensembles totaux satisfaisant la condition. Si vous avez une représentation fantaisiste de sous-ensembles non vides, cela suggère aussi immédiatement une structure de données pour stocker ces éléments: une étiquette de bit unique pour laquelle vous êtes, plus les représentations appropriées des sous-ensembles et des sous-ensembles non vides dans chaque cas. Mais je n'utiliserais probablement qu'un seul bitmask de taille c + l + r, même s'il y a quelques masques bitmatiques "invalides": c'est très compact, il est facile de vérifier la validité, et il y a beaucoup d'opérations bon marché sur les bitmasks .