java 打印列表的所有可能子集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7206442/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Printing all possible subsets of a list
提问by Steve
I have a List of elements (1, 2, 3), and I need to get the superset (powerset) of that list (without repeating elements). So basically I need to create a List of Lists that looks like:
我有一个元素列表（1、2、3），我需要获取该列表的超集（powerset）（没有重复元素）。所以基本上我需要创建一个列表列表，如下所示：
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
What is the best (simplicity > efficiency in this case, the list won't be huge) way to implement this? Preferably in Java, but a solution in any language would be useful.
实现这一点的最佳方式是什么（在这种情况下，简单性 > 效率，列表不会很大）？最好使用 Java，但任何语言的解决方案都会很有用。
回答by Petar Minchev
Use bitmasks:
使用位掩码：
int allMasks = (1 << N);
for (int i = 1; i < allMasks; i++)
{
for (int j = 0; j < N; j++)
if ((i & (1 << j)) > 0) //The j-th element is used
System.out.print((j + 1) + " ");
System.out.println();
}
Here are all bitmasks:
以下是所有位掩码：
1 = 001 = {1}
2 = 010 = {2}
3 = 011 = {1, 2}
4 = 100 = {3}
5 = 101 = {1, 3}
6 = 110 = {2, 3}
7 = 111 = {1, 2, 3}
You know in binary the first bit is the rightmost.
你知道在二进制中，第一位是最右边的。
回答by Shraddha Gupta
import java.io.*;
import java.util.*;
class subsets
{
static String list[];
public static void process(int n)
{
int i,j,k;
String s="";
displaySubset(s);
for(i=0;i<n;i++)
{
for(j=0;j<n-i;j++)
{
k=j+i;
for(int m=j;m<=k;m++)
{
s=s+m;
}
displaySubset(s);
s="";
}
}
}
public static void displaySubset(String s)
{
String set="";
for(int i=0;i<s.length();i++)
{
String m=""+s.charAt(i);
int num=Integer.parseInt(m);
if(i==s.length()-1)
set=set+list[num];
else
set=set+list[num]+",";
}
set="{"+set+"}";
System.out.println(set);
}
public static void main()
{
Scanner sc=new Scanner(System.in);
System.out.println("Input ur list");
String slist=sc.nextLine();
int len=slist.length();
slist=slist.substring(1,len-1);
StringTokenizer st=new StringTokenizer(slist,",");
int n=st.countTokens();
list=new String[n];
for(int i=0;i<n;i++)
{
list[i]=st.nextToken();
}
process(n);
}
}
回答by Nati Dykstein
A java solution based on Petar Minchev solution -
基于Petar Minchev解决方案的java解决方案-
public static List<List<Integer>> getAllSubsets(List<Integer> input) {
int allMasks = 1 << input.size();
List<List<Integer>> output = new ArrayList<List<Integer>>();
for(int i=0;i<allMasks;i++) {
List<Integer> sub = new ArrayList<Integer>();
for(int j=0;j<input.size();j++) {
if((i & (1 << j)) > 0) {
sub.add(input.get(j));
}
}
output.add(sub);
}
return output;
}
回答by Itamar_laufer
I've noticed that answers are focused on the String list. Consequently, I decided to share more generic answer. Hope it'll be fouund helpful. (Soultion is based on another solutions I found, I combined it to a generic algorithem.)
我注意到答案集中在字符串列表上。因此，我决定分享更通用的答案。希望它会被发现有帮助。（Soultion 基于我发现的另一个解决方案，我将它组合到一个通用算法中。）
/**
* metod returns all the sublists of a given list
* the method assumes all object are different
* no matter the type of the list (generics)
* @param list the list to return all the sublist of
* @param <T>
* @return list of the different sublists that can be made from the list object
*/
public static <T> List<List<T>>getAllSubLists(List<T>list)
{
List<T>subList;
List<List<T>>res = new ArrayList<>();
List<List<Integer>> indexes = allSubListIndexes(list.size());
for(List<Integer> subListIndexes:indexes)
{
subList=new ArrayList<>();
for(int index:subListIndexes)
subList.add(list.get(index));
res.add(subList);
}
return res;
}
/**
* method returns list of list of integers representing the indexes of all the sublists in a N size list
* @param n the size of the list
* @return list of list of integers of indexes of the sublist
*/
public static List<List<Integer>> allSubListIndexes(int n) {
List<List<Integer>> res = new ArrayList<>();
int allMasks = (1 << n);
for (int i = 1; i < allMasks; i++)
{
res.add(new ArrayList<>());
for (int j = 0; j < n; j++)
if ((i & (1 << j)) > 0)
res.get(i-1).add(j);
}
return res;
}
回答by DEVas
This is the simple function can be used to create a list of all the possible numbers generated by digits of all possible subsets of the given array or list.
这是一个简单的函数，可用于创建由给定数组或列表的所有可能子集的数字生成的所有可能数字的列表。
void SubsetNumbers(int[] arr){
int len=arr.length;
List<Integer> list=new ArrayList<Integer>();
List<Integer> list1=new ArrayList<Integer>();
for(int n:arr){
if(list.size()!=0){
for(int a:list){
list1.add(a*10+n);
}
list1.add(n);
list.addAll(list1);
list1.clear();
}else{
list.add(n);
}
}
System.out.println(list.toString());
}
