從兩組不同

Question

子集位口罩我有兩套 -

設置1 - {I1，I2，I3 ... IN1}

設置2 - {K1，K2，K3 ... KN2}

對於任何一組n項，我可以使用位掩碼0-2^n -1表示所有可能的子集。 同樣如何表示 -

set1和set2的所有可能的子集，其中至少1項來自不同的集合。

例如
{I1，I2，K1}是有效

但{I1，I2} - 無效的，因爲它沒有從SET2項。

我想產生兩件事情 - 一個方程的

1. 類，可以給我所有子集的計數，就像我們有2項單n項^ N子集。

2. 位編碼/掩碼使用我可以代表以上類型的子集。

Answer 1

如果我們引入一些額外的興趣集，這將更容易。我們稱之爲兩個輸入集合S1和S2;我們將定義集合L，C和R（用於左，中，右）。把這些看作是維恩圖。因此，定義L = S1 \ S2，S1中完全不在S2中的元素; C = S1∩S2，S1和S2中的元素，以及R = S2 \ S1。我們還分別爲這些集合的大小編寫l，c和r。

現在我們準備回答問題1：S1∪S2有多少個子集有一個來自S1的元素並且有一個來自S2的元素？有兩種情況需要考慮：或者我們有一個C中有一個元素的子集（它滿足「S1中的一個元素」和「S2中的一個元素」子句），或者我們在C中沒有元素，並且至少有一個每個都來自L和R.在第一種情況下，有C（2^c-1）個非空子集和餘數的2 ^（l + r）個子集，所以有（2^c-1） * 2 ^（l + r）在這種情況下設置。在第二種情況下，存在2^1 - 1個L的非空子集和2^r - 1個R的非空子集，因此存在（2^1 - 1）*（2^r - 1）個子集在這種情況下。將這兩種情況相加，我們總共有滿足條件的2 ^（c + l + r） - 2^l - 2^r個子集。

如果您有非空子集的奇特表示，這也立即建議用於存儲這些子集的數據結構：您所處位置的單個位標記，以及子集和非空子集的適當表示在每種情況下。

但我可能只是使用一個大小爲c + l + r的單一位掩碼，即使存在一些「無效」位掩碼：它非常緊湊，很容易檢查合法性，並且在位掩碼上有許多便宜的操作。