Javaでのセットのべき集合の取得

投稿日: 2022-11-08 2022-11-08
タグ: Algorithms, Java Collections

1. 序章

このチュートリアルでは、Javaで特定のセットのべき集合を生成するプロセスを学習します。

簡単に言うと、サイズ n のすべてのセットには、サイズ2nのべき集合があります。さまざまなテクニックを使用して取得する方法を学習します。

2. べき集合の定義

特定のセットSのべき集合は、S自体と空のセットを含むSのすべてのサブセットのセットです。

たとえば、特定のセットの場合：

{"APPLE", "ORANGE", "MANGO"}

べき集合は次のとおりです。

{
    {},
    {"APPLE"},
    {"ORANGE"},
    {"APPLE", "ORANGE"},
    {"MANGO"},
    {"APPLE", "MANGO"},
    {"ORANGE", "MANGO"},
    {"APPLE", "ORANGE", "MANGO"}
}

サブセットのセットでもあるため、内部サブセットの順序は重要ではなく、任意の順序で表示できます。

{
    {},
    {"MANGO"},
    {"ORANGE"},
    {"ORANGE", "MANGO"},
    {"APPLE"},
    {"APPLE", "MANGO"},
    {"APPLE", "ORANGE"},
    {"APPLE", "ORANGE", "MANGO"}
}

3. Guavaライブラリ

Google Guavaライブラリには、べき集合などの便利なSetユーティリティがいくつかあります。したがって、これを使用して、指定されたセットのべき集合を取得することもできます。

@Test
public void givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets() {
    ImmutableSet<String> set = ImmutableSet.of("APPLE", "ORANGE", "MANGO");
    Set<Set<String>> powerSet = Sets.powerSet(set);
    Assertions.assertEquals((1 << set.size()), powerSet.size());
    MatcherAssert.assertThat(powerSet, Matchers.containsInAnyOrder(
      ImmutableSet.of(),
      ImmutableSet.of("APPLE"),
      ImmutableSet.of("ORANGE"),
      ImmutableSet.of("APPLE", "ORANGE"),
      ImmutableSet.of("MANGO"),
      ImmutableSet.of("APPLE", "MANGO"),
      ImmutableSet.of("ORANGE", "MANGO"),
      ImmutableSet.of("APPLE", "ORANGE", "MANGO")
   ));
}

Guava powerSet は、次のサブセットが要求されたときにサブセットが計算されて返されるように、Iteratorインターフェイスを介して内部的に動作します。したがって、スペースの複雑さは、 O（2n）ではなく O（n）に削減されます。

しかし、グアバはどのようにしてこれを達成しますか？

4. べき集合生成アプローチ

4.1. アルゴリズム

次に、この操作のアルゴリズムを作成するための可能な手順について説明します。

空集合のべき集合は{{}}であり、空集合が1つだけ含まれているため、これが最も単純なケースです。

空のセット以外のすべてのセットSについて、最初に1つの要素を抽出し、elementという名前を付けます。次に、セット subsetWithoutElement の残りの要素について、それらのべき集合を再帰的に計算し、 powerSet S ubsetWithoutElementのような名前を付けます。次に、抽出した要素を powerSet S ubsetWithoutElement のすべてのセットに追加すると、 powerSet SubsetWithElement。[X156X ]

ここで、べき集合 S は、powerSetSubsetWithoutElementとpowerSetSubsetWithElementの和集合です。

与えられたセット{“APPLE”、 “ORANGE”、”MANGO”}の再帰的べき集合スタックの例を見てみましょう。

画像の読みやすさを向上させるために、名前の短縮形を使用します。 P はべき集合関数を意味し、「A」、「O」、「M」はの短縮形です。それぞれ「APPLE」、「ORANGE」、、「MANGO」：

4.2. 実装

したがって、最初に、1つの要素を抽出して残りのサブセットを取得するためのJavaコードを記述しましょう。

T element = set.iterator().next();
Set<T> subsetWithoutElement = new HashSet<>();
for (T s : set) {
    if (!s.equals(element)) {
        subsetWithoutElement.add(s);
    }
}

次に、subsetWithoutElementのべき集合を取得します。

Set<Set<T>> powersetSubSetWithoutElement = recursivePowerSet(subsetWithoutElement);

次に、そのパワーセットを元に戻す必要があります。

Set<Set<T>> powersetSubSetWithElement = new HashSet<>();
for (Set<T> subsetWithoutElement : powerSetSubSetWithoutElement) {
    Set<T> subsetWithElement = new HashSet<>(subsetWithoutElement);
    subsetWithElement.add(element);
    powerSetSubSetWithElement.add(subsetWithElement);
}

最後に、powerSetSubSetWithoutElementとpowerSetSubSetWithElementの和集合は、指定された入力セットのべき集合です。

Set<Set<T>> powerSet = new HashSet<>();
powerSet.addAll(powerSetSubSetWithoutElement);
powerSet.addAll(powerSetSubSetWithElement);

すべてのコードスニペットをまとめると、最終的な製品を確認できます。

public Set<Set<T>> recursivePowerSet(Set<T> set) {
    if (set.isEmpty()) {
        Set<Set<T>> ret = new HashSet<>();
        ret.add(set);
        return ret;
    }

    T element = set.iterator().next();
    Set<T> subSetWithoutElement = getSubSetWithoutElement(set, element);
    Set<Set<T>> powerSetSubSetWithoutElement = recursivePowerSet(subSetWithoutElement);
    Set<Set<T>> powerSetSubSetWithElement = addElementToAll(powerSetSubSetWithoutElement, element);

    Set<Set<T>> powerSet = new HashSet<>();
    powerSet.addAll(powerSetSubSetWithoutElement);
    powerSet.addAll(powerSetSubSetWithElement);
    return powerSet;
}

4.3. ユニットテストに関する注意事項

それでは、テストしてみましょう。ここには、確認するための基準が少しあります。

まず、べき集合のサイズを確認します。サイズnのセットの場合は2nである必要があります。
次に、すべての要素は、サブセットおよび2n-1の異なるサブセットで1回だけ発生します。
最後に、すべてのサブセットが1回表示される必要があります。

これらすべての条件が満たされれば、関数が機能することを確認できます。今、私たちが使用したので設定、繰り返しがないことはすでにわかっています。その場合、べき集合のサイズとサブセット内の各要素の出現回数を確認するだけで済みます。

使用できるパワーセットのサイズを確認するには、次のようにします。

MatcherAssert.assertThat(powerSet, IsCollectionWithSize.hasSize((1 << set.size())));

また、各要素の出現回数を確認するには、次のようにします。

Map<String, Integer> counter = new HashMap<>();
for (Set<String> subset : powerSet) { 
    for (String name : subset) {
        int num = counter.getOrDefault(name, 0);
        counter.put(name, num + 1);
    }
}
counter.forEach((k, v) -> Assertions.assertEquals((1 << (set.size() - 1)), v.intValue()));

最後に、すべてを1つの単体テストにまとめることができる場合：

@Test
public void givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets() {
    Set<String> set = RandomSetOfStringGenerator.generateRandomSet();
    Set<Set<String>> powerSet = new PowerSet<String>().recursivePowerSet(set);
    MatcherAssert.assertThat(powerSet, IsCollectionWithSize.hasSize((1 << set.size())));
   
    Map<String, Integer> counter = new HashMap<>();
    for (Set<String> subset : powerSet) {
        for (String name : subset) {
            int num = counter.getOrDefault(name, 0);
            counter.put(name, num + 1);
        }
    }
    counter.forEach((k, v) -> Assertions.assertEquals((1 << (set.size() - 1)), v.intValue()));
}

5. 最適化

このセクションでは、スペースを最小限に抑え、内部操作の数を減らして、最適な方法でべき集合を計算するようにします。

5.1. データ構造

与えられたアプローチでわかるように、再帰呼び出しでは多くの減算が必要であり、これは大量の時間とメモリを消費します。

代わりに、各セットまたはサブセットを他の概念にマップして、操作の数を減らすことができます。

まず、指定されたセット S 内の各オブジェクトに、0から始まる増加する番号を割り当てる必要があります。これは、番号の順序付きリストを操作することを意味します。

たとえば、特定のセット {“ APPLE”、“ ORANGE”、“ MANG”} の場合、次のようになります。

「アップル」->0

「オレンジ」->1

「マンゴー」->2

したがって、今後は、 S のサブセットを生成する代わりに、[0、1、2]の順序付きリストに対してそれらを生成し、順序付けされると、開始インデックスによる減算をシミュレートできます。

たとえば、開始インデックスが1の場合、[1,2]のべき集合を生成することを意味します。

オブジェクトからマップされたIDを取得するため、またはその逆を行うために、マッピングの両側を保存します。この例を使用して、（ “MANGO”-> 2）と（2-> “MANGO”）の両方を保存します。数値のマッピングはゼロから開始されたため、逆マップの場合は、単純な配列を使用してそれぞれのオブジェクトを取得できます。

この関数の可能な実装の1つは次のとおりです。

private Map<T, Integer> map = new HashMap<>();
private List<T> reverseMap = new ArrayList<>();

private void initializeMap(Collection<T> collection) {
    int mapId = 0;
    for (T c : collection) {
        map.put(c, mapId++);
        reverseMap.add(c);
    }
}

ここで、サブセットを表すために、2つのよく知られたアイデアがあります。

インデックス表現
バイナリ表現

5.2. インデックス表現

各サブセットは、その値のインデックスで表されます。たとえば、指定されたset {“APPLE”、 “ORANGE”、”MANGO”}のインデックスマッピングは次のようになります。

{
   {} -> {}
   [0] -> {"APPLE"}
   [1] -> {"ORANGE"}
   [0,1] -> {"APPLE", "ORANGE"}
   [2] -> {"MANGO"}
   [0,2] -> {"APPLE", "MANGO"}
   [1,2] -> {"ORANGE", "MANGO"}
   [0,1,2] -> {"APPLE", "ORANGE", "MANGO"}
}

したがって、指定されたマッピングを使用して、インデックスのサブセットからそれぞれのセットを取得できます。

private Set<Set<T>> unMapIndex(Set<Set<Integer>> sets) {
    Set<Set<T>> ret = new HashSet<>();
    for (Set<Integer> s : sets) {
        HashSet<T> subset = new HashSet<>();
        for (Integer i : s) {
            subset.add(reverseMap.get(i));
        }
        ret.add(subset);
    }
    return ret;
}

5.3. バイナリ表現

または、バイナリを使用して各サブセットを表すことができます。実際のセットの要素がこのサブセットに存在する場合、それぞれの値は1です。それ以外の場合は0です。

果物の例では、べき集合は次のようになります。

{
    [0,0,0] -> {}
    [1,0,0] -> {"APPLE"}
    [0,1,0] -> {"ORANGE"}
    [1,1,0] -> {"APPLE", "ORANGE"}
    [0,0,1] -> {"MANGO"}
    [1,0,1] -> {"APPLE", "MANGO"}
    [0,1,1] -> {"ORANGE", "MANGO"}
    [1,1,1] -> {"APPLE", "ORANGE", "MANGO"}
}

したがって、指定されたマッピングを使用して、バイナリサブセットからそれぞれのセットを取得できます。

private Set<Set<T>> unMapBinary(Collection<List<Boolean>> sets) {
    Set<Set<T>> ret = new HashSet<>();
    for (List<Boolean> s : sets) {
        HashSet<T> subset = new HashSet<>();
        for (int i = 0; i < s.size(); i++) {
            if (s.get(i)) {
                subset.add(reverseMap.get(i));
            }
        }
        ret.add(subset);
    }
    return ret;
}

5.4. 再帰的アルゴリズムの実装

このステップでは、両方のデータ構造を使用して前のコードを実装しようとします。

これらの関数の1つを呼び出す前に、initializeMapメソッドを呼び出して順序付きリストを取得する必要があります。また、データ構造を作成した後、それぞれの unMap 関数を呼び出して、実際のオブジェクトを取得する必要があります。

public Set<Set<T>> recursivePowerSetIndexRepresentation(Collection<T> set) {
    initializeMap(set);
    Set<Set<Integer>> powerSetIndices = recursivePowerSetIndexRepresentation(0, set.size());
    return unMapIndex(powerSetIndices);
}

それでは、インデックス表現を試してみましょう。

private Set<Set<Integer>> recursivePowerSetIndexRepresentation(int idx, int n) {
    if (idx == n) {
        Set<Set<Integer>> empty = new HashSet<>();
        empty.add(new HashSet<>());
        return empty;
    }
    Set<Set<Integer>> powerSetSubset = recursivePowerSetIndexRepresentation(idx + 1, n);
    Set<Set<Integer>> powerSet = new HashSet<>(powerSetSubset);
    for (Set<Integer> s : powerSetSubset) {
        HashSet<Integer> subSetIdxInclusive = new HashSet<>(s);
        subSetIdxInclusive.add(idx);
        powerSet.add(subSetIdxInclusive);
    }
    return powerSet;
}

それでは、バイナリアプローチを見てみましょう。

private Set<List<Boolean>> recursivePowerSetBinaryRepresentation(int idx, int n) {
    if (idx == n) {
        Set<List<Boolean>> powerSetOfEmptySet = new HashSet<>();
        powerSetOfEmptySet.add(Arrays.asList(new Boolean[n]));
        return powerSetOfEmptySet;
    }
    Set<List<Boolean>> powerSetSubset = recursivePowerSetBinaryRepresentation(idx + 1, n);
    Set<List<Boolean>> powerSet = new HashSet<>();
    for (List<Boolean> s : powerSetSubset) {
        List<Boolean> subSetIdxExclusive = new ArrayList<>(s);
        subSetIdxExclusive.set(idx, false);
        powerSet.add(subSetIdxExclusive);
        List<Boolean> subSetIdxInclusive = new ArrayList<>(s);
        subSetIdxInclusive.set(idx, true);
        powerSet.add(subSetIdxInclusive);
    }
    return powerSet;
}

5.5. [0、2n）を反復処理します

これで、バイナリ表現で実行できる優れた最適化があります。これを見ると、各行が [0、2n）の数値のバイナリ形式に相当していることがわかります。

したがって、0から2nまでの数値を繰り返す場合、そのインデックスをバイナリに変換し、それを使用して各サブセットのブール表現を作成できます。

private List<List<Boolean>> iterativePowerSetByLoopOverNumbers(int n) {
    List<List<Boolean>> powerSet = new ArrayList<>();
    for (int i = 0; i < (1 << n); i++) {
        List<Boolean> subset = new ArrayList<>(n);
        for (int j = 0; j < n; j++)
            subset.add(((1 << j) & i) > 0);
        powerSet.add(subset);
    }
    return powerSet;
}

5.6. グレイコードによる微小変化サブセット

ここで、長さ nのバイナリ表現から[0、2n）の数値まで、全単射関数を定義すると、サブセットを任意の順序で生成できます。欲しい。

グレイコードは、数字のバイナリ表現を生成するために使用されるよく知られた関数であり、連続する数字のバイナリ表現は1ビットだけ異なります（最後の数字と最初の数字の違いも1つです）。

したがって、これをもう少し最適化できます。

private List<List<Boolean>> iterativePowerSetByLoopOverNumbersWithGrayCodeOrder(int n) {
    List<List<Boolean>> powerSet = new ArrayList<>();
    for (int i = 0; i < (1 << n); i++) {
        List<Boolean> subset = new ArrayList<>(n);
        for (int j = 0; j < n; j++) {
            int grayEquivalent = i ^ (i >> 1);
            subset.add(((1 << j) & grayEquivalent) > 0);
        }
        powerSet.add(subset);
    }
    return powerSet;
}

6. 遅延読み込み

O（2n）であるべき集合のスペース使用量を最小限に抑えるために、 Iterator インターフェースを利用して、すべてのサブセット、および各サブセットのすべての要素を遅延フェッチできます。

6.1. ListIterator

まず、0から2nまで反復できるようにするには、この範囲をループするが、事前に範囲全体を消費しない特別なIteratorが必要です。

この問題を解決するために、2つの変数を使用します。 1つは2nのサイズ用で、もう1つは現在のサブセットインデックス用です。 hasNext（）関数は、positionがsize ：よりも小さいことを確認します。

abstract class ListIterator<K> implements Iterator<K> {
    protected int position = 0;
    private int size;
    public ListIterator(int size) {
        this.size = size;
    }
    @Override
    public boolean hasNext() {
        return position < size;
    }
}

そして、 next（）関数は、現在の position のサブセットを返し、positionの値を1つ増やします。

@Override
public Set<E> next() {
    return new Subset<>(map, reverseMap, position++);
}

6.2. サブセット

遅延ロードSubsetを行うために、 AbstractSet を拡張するクラスを定義し、その関数の一部をオーバーライドします。

サブセットの受信マスク（または位置）の 1 であるすべてのビットをループすることにより、イテレータとAbstractSetの他のメソッド。

たとえば、 size（）は、受信側のマスク内の1の数です。

@Override
public int size() { 
    return Integer.bitCount(mask);
}

そして、 contains（）関数は、マスクのそれぞれのビットが1であるかどうかだけです。

@Override
public boolean contains(@Nullable Object o) {
    Integer index = map.get(o);
    return index != null && (mask & (1 << index)) != 0;
}

別の変数remainingSetBitsを使用して、サブセット内のそれぞれの要素を取得するたびにその変数を変更し、そのビットを0に変更します。次に、 hasNext（）は、 previousSetBits がゼロでないかどうかをチェックします（つまり、 1 の値を持つビットが少なくとも1つあります）。

@Override
public boolean hasNext() {
    return remainingSetBits != 0;
}

また、 next（）関数は、leftingSetBitsの右端の1を使用し、それを 0 に変換して、それぞれの要素：

@Override
public E next() {
    int index = Integer.numberOfTrailingZeros(remainingSetBits);
    if (index == 32) {
        throw new NoSuchElementException();
    }
    remainingSetBits &= ~(1 << index);
    return reverseMap.get(index);
}

6.3. PowerSet

遅延読み込みを行うには PowerSet クラス、拡張するクラスが必要です AbstractSet >。

size（）関数は、セットのサイズの2の累乗です。

@Override
public int size() {
    return (1 << this.set.size());
}

べき集合には入力セットのすべての可能なサブセットが含まれるため、 contains（Object o）関数は、 objectoのすべての要素がreverseMap[ X192X]（または入力セット内）：

@Override
public boolean contains(@Nullable Object obj) {
    if (obj instanceof Set) {
        Set<?> set = (Set<?>) obj;
        return reverseMap.containsAll(set);
    }
    return false;
}

このクラスで特定のオブジェクトが等しいかどうかを確認するには、入力setが特定のオブジェクトと等しいかどうかのみを確認できます。

@Override
public boolean equals(@Nullable Object obj) {
    if (obj instanceof PowerSet) {
        PowerSet<?> that = (PowerSet<?>) obj;
        return set.equals(that.set);
    }
    return super.equals(obj);
}

iterator（）関数は、すでに定義したListIteratorのインスタンスを返します。

@Override
public Iterator<Set<E>> iterator() {
    return new ListIterator<Set<E>>(this.size()) {
        @Override
        public Set<E> next() {
            return new Subset<>(map, reverseMap, position++);
        }
    };
}

Guavaライブラリはこの遅延読み込みのアイデアを使用しており、これらのPowerSetおよびSubsetはGuavaライブラリの同等の実装です。

詳細については、ソースコードおよびドキュメントを確認してください。

さらに、 PowerSet のサブセットに対して並列操作を実行する場合は、ThreadPoolのさまざまな値に対してSubsetを呼び出すことができます。

7. 概要

要約すると、最初に、べき集合とは何かを研究しました。次に、GuavaLibraryを使用して生成しました。その後、アプローチとその実装方法、およびその単体テストの作成方法を検討しました。

最後に、 Iterator インターフェースを利用して、サブセットとその内部要素の生成スペースを最適化しました。

いつものように、ソースコードはGitHubでから入手できます。

getdocs

13036