質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

Q&A

解決済

2回答

1444閲覧

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

guratan

総合スコア2

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

0グッド

0クリップ

投稿2021/11/04 09:27

編集2021/11/04 09:29

前提・実現したいこと

数列の部分集合を探索するプログラムを作成しています.
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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

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

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

投稿2021/11/04 10:27

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guratan

2021/11/05 06:01

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

0

つまり、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

総合スコア4958

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

dodox86

2021/11/04 10:21

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

2021/11/04 10:25

あ、済みません。見落としていました…
xebme

2021/11/04 22:46

forループの前にビットマスクを使うと簡単です。ビット演算の、整数 & マスク。マスクは欲しい要素番号(n-1ビット目)がオンになっていること。
guratan

2021/11/05 05:59

ご回答いただきありがとうございます. 目立たぬよう改良をの条件を書いてしまい,申し訳ございません. 追記していただいた情報によって改良案が想像しやすくなりました.
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問