三种实现集合求子集合算法

 题目：给定一个集合，求该集合的所有子集合，如集合{1,2}的子集合有{}(空集是所有集合的子集),{1},{2},{1,2},共2^2个子集合，下面给出两种解法，其中第一种解法分递归与非递归实现，都用java实现。

 

【第一种解法】

    算法思想：给定一个集合，求子集合过程可分为以下两个步骤：

      （1）把集合分为两部分，第一个元素和剩余元素，如{1,2,3}分为1和{2,3}

      （2）原集合的所有子集合为剩余元素的子集合并上把第一个元素加入所有子集合，如{2,3}的子集合为{2},{3},{2,3},{},那么把第一个元素1加入这些子集合，则构成{1,2},{1,3},{1,2,3},{1},把这些集合合并起来，则原集合的所有子集合便为{2},{3},{2,3},{},{1,2},{1,3},{1,2,3},{1}，代码如下：

       

    【非递归实现】

    

package bitSet;
import java.util.ArrayList;

public class SubSet {
	public static void main(String[] args) {

		int array[] = { 1, 2, 3, 4, 5, 6 };

		ArrayList<ArrayList<Integer>> allSet = new ArrayList<ArrayList<Integer>>();

		allSet.add(new ArrayList<Integer>());

		for (int i = 0; i < array.length; i++) {

			ArrayList<ArrayList<Integer>> subSet = new ArrayList<ArrayList<Integer>>();

			for (int j = 0; j < allSet.size(); j++) {

				ArrayList<Integer> element = new ArrayList<Integer>();

				element.add(array[i]);

				element.addAll(allSet.get(j));

				subSet.add(element);

			}

			allSet.addAll(subSet);

		}

		int count = 0;
		for (int i = 0; i < allSet.size(); i++) {

			ArrayList el = allSet.get(i);

			for (int j = 0; j < el.size(); j++) {

				System.out.print(el.get(j) + " ");

			}

			count++;
			System.out.println();

		}
		System.out.println(count);
	}
}

  【递归实现】

package bitSet;

import java.util.ArrayList;

public class SubSet1 {

	static ArrayList<ArrayList<Integer>> getSubsets(int[] set, int index) {

		ArrayList<ArrayList<Integer>> allsubsets;

		if (set.length == index) {

			allsubsets = new ArrayList<ArrayList<Integer>>();

			allsubsets.add(new ArrayList<Integer>()); // Empty set

		} else {

			allsubsets = getSubsets(set, index + 1);

			int item = set[index];

			ArrayList<ArrayList<Integer>> moresubsets =

			new ArrayList<ArrayList<Integer>>();

			for (ArrayList<Integer> subset : allsubsets) {

				ArrayList<Integer> newsubset = new ArrayList<Integer>();

				newsubset.addAll(subset); //

				newsubset.add(item);

				moresubsets.add(newsubset);

			}

			allsubsets.addAll(moresubsets);

		}

		return allsubsets;
	}

	public static void main(String[] args) {
		
		int array[] = { 1, 2, 3, 4, 5, 6 };
		
		ArrayList<ArrayList<Integer>> allSet = getSubsets(array,0);

		int count = 0;
		for (int i = 0; i < allSet.size(); i++) {

			ArrayList el = allSet.get(i);

			for (int j = 0; j < el.size(); j++) {

				System.out.print(el.get(j) + " ");

			}
			count++;
			System.out.println();

		}
			System.out.println(count);
	}
}

 

【第二种解法】

    算法思想：n个元素的集合，在构造子集合过程中，每个元素有两种情况，在子集合中“存在”与“不存在”，“存在”用“1”表示，“不存在”用“0”表示，这样共有2^n种情况，即2^n个子集合。此时我们想到用长度为n的二进制数字 “1111....000...”，1表示该位置在子集合中存在，0表示该位置在子集合中不存在，让该二进制数从0 一直加到 2^n，则所有情况都会出现，代码如下

 

package bitSet;

import java.util.ArrayList;

public class SubSet3 {

	static ArrayList<ArrayList<Integer>> getSubsets(int[] set) {

		ArrayList<ArrayList<Integer>> allsubsets =

		new ArrayList<ArrayList<Integer>>();

		int max = 1 << set.length;

		for (int i = 0; i < max; i++) {

			ArrayList<Integer> subset = new ArrayList<Integer>();

			int k = i;

			int index = 0;

			while (k > 0) {

				if ((k & 1) > 0) {

					subset.add(set[index]);

				}

				k >>= 1;

				index++;

			}

			allsubsets.add(subset);

		}

		return allsubsets;
	}

	public static void main(String[] args) {

		int array[] = { 1, 2, 3, 4, 5, 6 };

		ArrayList<ArrayList<Integer>> allSet = getSubsets(array);

		int count = 0;
		for (int i = 0; i < allSet.size(); i++) {

			ArrayList el = allSet.get(i);

			for (int j = 0; j < el.size(); j++) {

				System.out.print(el.get(j) + " ");

			}
			count++;
			System.out.println();

		}
		System.out.println(count);
	}
}