0

Java プログラミングの課題について助けを求めています。リンクされたリストを使用して、そのパワー セットを出力する必要があります。たとえば、セット {1,2,3} は {{},{1}{1,2}{1,3}{1,2,3}{2}{2,3}{3} を出力する必要があります}。ベキ集合の要素数は 2^n です。これは、HeadNode.PrintPowerSet(); を呼び出して行う必要があります。
ここで、HeadNode はリンク リストの最初の要素です。私はいくつかのことを試しましたが、何もうまくいきません。それを行う最善の方法は、最後のセンチネルに到達するまでメソッドを再帰的に呼び出してから、残っている要素を追加して逆方向に作業することだと思います。申し訳ありませんが、これ以上コードやアイデアを投稿することはできません。前もって感謝します。

編集: これは非動作コードです。セット {{1,2,3}{2,3}{3}} を返します

public RSet powerSet() 
{
    if (this == EMPTY_SET)
        return EMPTY_SET;

    RSet q = new RSet();
    if (q != EMPTY_SET)
        q.next = next.powerSet();
    q = new RSet(this, n, q.next);

    return q;
}

EMPTY_SET はエンド センチネルです。手書きで書いてみました。助かりますが、まだ手に入りません。また、このクラス RSet は、本質的に単なるリンク リスト ノードです。

4

1 に答える 1

1

0 から 2^n - 1 までのすべての数値を反復するだけです。それぞれがベキ集合の要素を定義します。

リストは、セットの固定インデックスを定義します。番号ごとに、新しいセットを作成します。バイナリ形式の数値を考慮して、インデックス i のビットが 1 の場合は元のセットのインデックス i の項目をセットに追加し、それ以外の場合は追加しません。

次に、数値ごとに、ベキ集合の要素である集合があります。

int n = list.size();

Set<Set<T>> powerSet = new HashSet<Set<T>>();

for( long i = 0; i < (1 << n - 1); i++) {
    Set<T> element = new HashSet<T>();
    for( int j = 0; j < n; j++ )
        if( (i >> j) % 2 == 1 ) element.add(list.get(j));
    powerSet.add(element); 
}

return powerSet;
于 2013-02-11T18:29:40.147 に答える