そのため、セットのパワーセットをその要素ごとに一意の番号 (インデックス) にマップし、この番号をマップまたはリスト内の一意でない値に関連付けたいという状況があります。すべてのサブセットを明示的に保存する必要はなく、それらに関連付けられた一意の番号のみを保存するために、これが必要です。サブセットの要素から数値を一意に生成する線形時間 (できれば、必要に応じてより高い次数の多項式を使用できると思います) アルゴリズムが存在する場合、それは素晴らしいことです。直感的には、サブセットの要素に対していくつかの加算関数または畳み込み関数を使用して、そのようなアルゴリズムが存在する可能性があると思います。
U = {1,2,3,...,n}形式的に言えば、すべてのサブセットが必要なユニバースがあります。2^nそのようなサブセットがあります。fサブセットXから数値へyの関数マッピングがありますf(X)=y。y一意でない番号です。
Xここで、プログラムで、あるサブセット値から別のサブセットY値に移動できるようにする必要がありY = X - {k}ますk ϵ X。Yしたがって、その要素からの一意の識別子を計算できるアルゴリズムがあれば、検索が必要な格納されたサブセットのリストを検索する代わりに、kの (残りの) 要素を削除して使用するだけで済みます。 XAND を各サブセットを格納するためのメモリ コストと比較します。
では、そのようなアルゴリズムが存在するかどうかを知っている人はいますか?