Javaはコレクション内のすべてのサブセットの詳細を取得します

この記事ではJavaでセット内のすべてのサブセットを取得する方法を主に紹介します。非常に優れた参考値です。

面接には筆記試験の質問があります。

セットを入力し、このセットのすべてのサブセットを出力します。たとえば、「1、2、4」と入力します。出力結果は次のようになります。

[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]

知っておくべきこと: 空のセットは、任意のセットのサブセットです。適切なサブセットは、サブセット; 空でない適切なサブセットは、サブセットが含まれていないことを意味します セットと空のセット

問題解決のアイデア:

この質問は、「ビットごとの対応法」を使用して計算できます

たとえば、セット A ={a,b,c} は、各サブセット内の任意の要素に対して、存在するか存在しません。 サブセットへのマッピング:

(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->(c)
(0,0,0)->@(@表示空集)

上記のルールを遵守してください。これはコンピューターのデータ保存方法に似ているため、整数をセットにマッピングできます... 000 ~ 111... 111 (はいを意味し、いいえを意味し、 (逆も同様))、整数値を徐々に増やすことによって、すべての数値を調べることができます。つまり、セットの対応するサブセットを取得できます。

主なテストは、変位操作と論理的思考能力です。具体的なコードは次のとおりです (本機で認証されており、絶対に信頼できます):

import java.util.ArrayList;
import java.util.Scanner;
import org.apache.commons.collections.CollectionUtils;
/**
 * 输入一个集合，输出这个集合的所有子集
 * @author liangyongxing
 * @time 2017-02-06
 */
public class SubListExport {
 public static void main(String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  System.out.println("请输入一串整数并在输入时用英文逗号隔开：");
  String inputString = new Scanner(System.in).next().toString();
  if (inputString != null && !inputString.isEmpty()) {
   String[] strArray = inputString.split(",");
   for (String str : strArray) {
    list.add(Integer.parseInt(str));
   }
   ArrayList<ArrayList<Integer>> allsubsets = getSubsets(list); 
   for(ArrayList<Integer> subList : allsubsets) {
    System.out.println(subList);
   }
  }
 }
 public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> subList) {
  ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>();
  int max = 1 << subList.size();
  for(int loop = 0; loop < max; loop++) {
   int index = 0;
   int temp = loop;
   ArrayList<Integer> currentCharList = new ArrayList<Integer>();
   while(temp > 0) {
    if((temp & 1) > 0) {
     currentCharList.add(subList.get(index));
    }
    temp>>=1;
    index++;
   }42    allsubsets.add(currentCharList);44   }
  return allsubsets;
 }
}

注: 2017-02-08 10:01:32 上記。コードには特定の抜け穴があり、入力に繰り返しの数値がある場合、結果は繰り返しのサブセット出力になり、サブセットを計算するときに重複を排除するために HashSet を追加する必要があります。最終的な印刷結果はセットから取得できます。 具体的な変更内容は以下の図の通りです:

1. main 関数が印刷する HashSet 型に変更します。 2. 関数部分で、カプセル化リストを変更し、リストを set に変更する必要があります。

これで変更は完了し、テストの実行結果は次のようになります:

コードは、時間計算量が O(n*log2n)

であることを示します。

以上がJavaはコレクション内のすべてのサブセットの詳細を取得しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。