將多重集表示爲位序列

Question

我們可以使用位掩碼來有效地表示集合存在於有限（或至少索引）的域中，例如以表示car中的字母，我們可以將其表示爲26位集合像這樣：

abcdefghijklmnopqrstuvwxyz 
10100000000000000100000000 

但是當然這隻能代表在場，不重複 - carry例如實際上有兩個r S，而是一組不能代表。

multiset代表一個計數，而不僅僅是存在，所以我們可以計數重複，但是我不清楚這是否可以在邏輯上用一個數表示。

同事建議的一個想法是使用素數作爲我們的指數，並通過它的素因子分解來表示多重集。所以我們上面的情況會變成：

car = 2^1 * 3^0 * 5^1 * ... * 61^1 * .... 
carry = 2^1 * 3^0 * 5^1 * ... * 61^2 * ... 97^1 * 101^0 

這是一個很好的方式來表示multisets？是否有更好的這種概念的二元表示？

Answer 1

平凡：爲宇宙的每個元素使用k位而不是1位。將它們連接起來得到一個單一的數字，如果你關心它的話，但是你可以等價地把它看作一個數組（相當於bitset，一組布爾數組，也是有效和有用的）。

這可能需要更多的空間比主要因素的方法，但在光明的一面，它仍然非常節省空間，你可以測試存在（並提取計數）與數組查找和一些小提琴，而不是看up /計算相關的素數並執行整數除法。