Printing all possible subsets of a list

Question

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.

Milled

You want all subsets of that list. I'd suggest recursion. However, if you are dealing with, say, more than 30-40 elements, you won't be able to deal with the HUGE (over 1TB of data) you have. What is this used for? – Priory

This data structure you're looking for is called a Powerset (the diffence being that it also contains an empty set). It's already been discussed on SO. – Absolutely

Thanks Zenzen for pointing me in the right direction...I found #1671362. – Milled

Those are not permutations, those are subsets. – Insertion

Answer 1

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.

Anodize

This is very interesting...you're obviously a lot smarter than I am though - give me some time to wrap my mind around this....is N the number of elements in the original list? And am I mapping the objects in my list to integers? – Milled

@Milled - Yes, N is the number of elements - in your example above N = 3. Think in binary - the bit is 0 if the element is not used and the bit is 1 if the element is used. For example 5 = 101 in binary. This means 1 and 3 are used. = {1, 3} – Anodize

I don't think this will work for moderately sized lists or above, the allMasks integer will overflow – Amphisbaena

@Amphisbaena - it will overflow after around 31 bits (2^31), which is the max for integer, and it is already a colossal number of 2 billion. If you need to print or iterate 2 billion numbers, there is something wrong :) – Anodize

@PetarMinchev I agree :), my only use case was a practice interview problem where I needed to return all permutations of a size 50 list (2^50 permutations, 10^15 possibilites) subject to a predicate. I modified your solution to use big integer for this purpose. The modified version would produce the correct answer in 40 years or so, but at least the interviewer could not say it was an incorrect solution. Your solution is beautiful by the way. – Amphisbaena

How does the left shift operator calculate the number of possible subsets? i.e. how does 'allMasks' know that there are eight possible subsets (when N=3)? – Immortelle

@Immortelle - Look at all binary numbers with length = N. For N = 3, we have 0 0 0, 0 0 1, 0 1 0, 0 1 1, 1 0 0, 1 0 1, 1 1 0, 1 1 1. Essentially 1 means the number at the position participates in the subset. And the number of binary numbers of length N is 2^N. The left shift operator behaves like this (1 << 0) = 1 = 1 in decimal, (1 << 1) = 10 = 2 in decimal, (1 << 2) = 100 = 4 in decimal, (1 << 3) = 1000 = 8 in decimal. It is a direct consequence of binary to decimal conversion. – Anodize

Answer 2

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);
    }
}

Leddy

The program is simple. First, we try to get all possible combinations of 1-n digit numbers till the last digit of each list of 1,2,3,....n digit number is n. And then with each combination to extract each of its character(i.e. number) and display the element of the subset stored in the cell index denoted by this character(number). – Leddy

It would be better to add the description of the code in the answer itself than in comments. Answer with code only are not considered good answer by the community in general, even the code answers properly the question. – Unstudied

Answer 3

A java solution based on Petar Minchev solution -

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;
}

Papaw

Answer 4

In the given solution we iterate over every index and include current and all further elements.

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);
            }
        }
        
}

Poker

Answer 5

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.)

/**
 * 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;
}

Noria

Answer 6

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());
}

Gondar

Answer 7

Peter Minchev's solution modified to handle larger lists through 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;
}

Amphisbaena

Answer 8

/*---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);

Nth