打印列表的所有可能的子集
我有一个元素列表 (1, 2, 3),我需要获取该列表的超集(幂集)(不重复元素)。所以基本上我需要创建一个列表列表,如下所示:
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
实现此目的的最佳方法是什么(在这种情况下简单性>效率,列表不会很大)?最好使用 Java,但任何语言的解决方案都会有用。
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}
{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.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(8)
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);
}
}
基于 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;
}
在给定的解决方案中,我们迭代每个索引并包括当前元素和所有其他元素。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if(nums == null || nums.length ==0){
return ans;
}
Arrays.sort(nums);
List<Integer> subset = new ArrayList<>();
allSubset(nums, ans , subset , 0);
return ans;
}
private void allSubset(int[] nums,List<List<Integer>> ans ,List<Integer> subset , int idx){
ans.add(new ArrayList<>(subset));
for(int i = idx; i < nums.length; i++){
subset.add(nums[i]);
allSubset(nums, ans , subset , i+1);
subset.remove(subset.size() - 1);
}
}
}
我注意到答案集中在字符串列表上。
因此,我决定分享更通用的答案。
希望它会有所帮助。
(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;
}
这是一个简单的函数,可用于创建由给定数组或列表的所有可能子集的数字生成的所有可能数字的列表。
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());
}
Peter Minchev 的解决方案经过修改,可以通过 BigInteger 处理更大的列表
public static List<List<Integer>> getAllSubsets(List<Integer> input) {
BigInteger allMasks = BigInteger.ONE.shiftLeft(input.size());
List<List<Integer>> output = new ArrayList<>();
for(BigInteger i=BigInteger.ZERO;allMasks.subtract(i).compareTo(BigInteger.ZERO)>0; i=i.add(BigInteger.ONE)) {
List<Integer> subList = new ArrayList<Integer>();
for(int j=0;j<input.size();j++) {
if(i.and(BigInteger.valueOf(1<<j)).compareTo(BigInteger.ZERO) > 0) {
subList.add(input.get(j));
}
}
System.out.println(subList);
output.add(subList);
}
return output;
}
/*---USING JAVA COLLECTIONS---*/
/*---O(n^3) Time complexity, Simple---*/
int[] arr = new int[]{1,2,3,4,5};
//Convert the array to ArrayList
List<Integer> arrList = new ArrayList<>();
for(int i=0;i<arr.length;i++)
arrList.add(arr[i]);
List<List<Integer>> twoD_List = new ArrayList<>();
int k=1; /*-- k is used for toIndex in sublist() method---*/
while(k != arr.length+1) /*--- arr.length + 1 = toIndex for the last element---*/
{
for(int j=0;j<=arr.length-k;j++)
{
twoD_List.add(arrList.subList(j, j+k));/*--- fromIndex(j) - toIndex(j+k)...notice that j varies till (arr.length - k), while k is constant for the whole loop...k gets incremented after all the operations in this for loop---*/
}
k++; /*--- increment k for extending sublist(basically concept the toIndex)---*/
}
//printing all sublists
for(List<Integer> list : twoD_List) System.out.println(list);
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
使用位掩码:
以下是所有位掩码:
您知道在二进制中,第一位是最右边的。
Use bitmasks:
Here are all bitmasks:
You know in binary the first bit is the rightmost.