（Java）bit演算による部分集合探索を特定の条件に従って行わせたい

前提・実現したいこと

数列の部分集合を探索するプログラムを作成しています．
bit演算による全探索の方法は理解できるのですが，
特定の条件を満たした部分集合（例えば，0が含まれている部分集合のみ）を探索する方法が思いつきません．

現状のコード

https://www.geeksforgeeks.org/java-program-to-print-all-unique-subsets-in-an-array-of-subsets-using-bit-manipulation/
を参考に，全探索プログラムを作成しました．

//Importing input output classes
import java.io.*;
//Importing utility classes
import java.util.*;

//Main class
class GFG {

	// Method 1
	static List<List<Integer> > subsets(int[] nums)
	{

		// Creating List class object
		// Declaring. object of integer List
		List<List<Integer> > output = new ArrayList<>();

		int n = nums.length;

		// Increase the size by using left shift (1 * 2^n)
		int size = 1 << n;

		for (int i = 0; i < size; i++) {
			List<Integer> curr = new ArrayList<>();
			for (int j = 0; j < n; j++) {

				// right shift i and j i.e. i/2^j
				if (((i >> j) & 1) == 1) {

					// Add it to subset
					curr.add(nums[j]);
				}
			}

			// Adding the subset
			output.add(curr);
		}
		return output;
	}

	// Method 2
	// Main driver method
	public static void main(String[] args)
	{

		// Custom input array
		int Nodenum = 3;
		
		int[] arr = new int[Nodenum];

		for (int i = 0; i < Nodenum; i++) {
			arr[i] = i;
		}

		// Calling method 1 in main() method
		List<List<Integer> > output = subsets(arr);

		// Print all unique subsets in an array
		System.out.println(output);
	}
}

これを実行すると以下が出力されます

[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]

どのように改良したいか

現在，都合上以下のことができるようコードを改良したいと考えております．
・0が含まれている部分集合のみを探索したい＝0は固定したい
・0の固定に伴い，探索の計算量を減らしたい
＝if文で0が含まれているかを逐一検証するのではなく，0が含まれている部分集合のみに限定して探索を行い，計算量を減らしたい．

つまり，上記のコードを改良し，以上の点を守ったうえで，以下のような出力をさせたいのです．

[[0], [0, 1], [0, 2], [0, 1, 2]]

しかし，どのようにコードを改良すべきか見当がつかず，検索しても中々ヒットしなかったので困っております．

もしよろしければ，
どのように改良すればよいかをご教示いただいてもよろしいでしょうか？
何卒よろしくお願いいたします．

補足情報（FW/ツールのバージョンなど）

開発言語：Java

行動規範の内容に同意します

回答2件

ベストアンサー

数字の順番やリスト中に複数の0があったときの区別をケアしなくて良いのであれば、
以下のアプローチはどうでしょうか。

リストに含まれる0の数をカウントする
0を除いたリストを作成する
元々の全探索プログラムで部分集合をつくる
output.add(curr)する際に、currに0を1個足したもの、2個足したもの、…全ての0を足したものを全て追加する。

投稿2021/11/04 10:27

退会済みユーザー

総合スコア0

guratan

2021/11/05 06:01

ご回答いただきありがとうございます．ご教示いただいた方法を試した結果，想定していた出力を得ることができました．アプローチに関して詳細にアドバイスしていただき，誠にありがとうございました．

行動規範の内容に同意します

つまり、bit全探索において、特定の条件( 質問では「"0"を含む集合」 )のときだけですよね?
それなら普通にやればよさそうですが。

まず、質問者さんは質問にある内容を、『手作業で』やると考えた場合、どのようにしますか?

私なら、「0が一個でも出た時点でtrueと見なす」ですね。それは違う言い方にすると、『1個でも0が出ればいい』ですね。

ということは、「フラグが立っているかどうか」(質問にあるコードだと((i >> j) & 1) == 1)のところで、「値が0かどうか」も条件に含めればいいはずです。

0のとき、bool flag を trueにして、そのifの外側の『条件に一致するか』のところで、「flagがtrueなら0を含んでいるとみなす」的な感じにすればいいかと。

(ここにあった文は質問にある条件を無視していたため伏せる)

[追記1]

基本的にbit全探索の流れは、

1. 要素の個数分(配列の要素数とか)以下をループする
    1.1. (1)で生成したビット列を一つずつ見ていき、以下を繰り返す
        1.1.1. ビットが立っているのなら
            1.1.1.1. 追加等の処理
        1.1.2. (1.1.1.1)で追加したデータが条件を満たしているか
             1.1.2.1. カウントアップ等の処理

のような感じになっていますね。この(1.1.1.1) のところぐらいで、「値が0なら→計上する」的な感じにすればいいかと。
そうすれば、(1.1.2.1)で「0が含まれているのなら」を省く事ができるはずです。
(それにどの道 (1.1.1)では n 回ループし、値を見れるはずなので)

投稿2021/11/04 10:17

編集2021/11/04 10:26

BeatStar

総合スコア4962

dodox86

2021/11/04 10:21

> それか、単純に「条件に一致するかどうか」の部分で「0があるかどうか調べる」的な処理を入れてもいいですね。とありますが、質問文中の改良の条件に > ・0の固定に伴い，探索の計算量を減らしたい＝if文で0が含まれているかを逐一検証するのではなく，0が含まれている部分集合のみに限定して探索を行い，計算量を減らしたい．が提示されています。それは考慮済みのご回答でしょうか。