Find all subsets of length k in an array

Question

Given a set {1,2,3,4,5...n} of n elements, we need to find all subsets of length k .

For example, if n = 4 and k = 2, the output would be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

I am not even able to figure out how to start. We don't have to use the inbuilt library functions like next_permutation etc.

Need the algorithm and implementation in either C/C++ or Java.

Answer 1

This is python. Sorry for the spanish ;)

from pprint import pprint
conjunto = [1,2,3,4, 5,6,7,8,9,10]
k = 3
lista = []
iteraciones = [0]
def subconjuntos(l, k):
    if k == len(l):
        if not l in lista:
            lista.append(l)
        return
    for i in l:
        aux = l[:]
        aux.remove(i)
        result = subconjuntos(aux, k)
        iteraciones[0] += 1
        if not result in lista and result:
            lista.append( result)

subconjuntos(conjunto, k)
print (lista)
print ('cant iteraciones: ' + str(iteraciones[0]))

Answer 2

Here is a Java version of what I think Simple is talking about, using a binary representation of all sets in the power set. It's similar to how Abhiroop Sarkar did it, but I think a boolean array makes more sense than a string when you are just representing binary values.

private ArrayList<ArrayList<Object>> getSubsets(int m, Object[] objects){
    // m = size of subset, objects = superset of objects
    ArrayList<ArrayList<Object>> subsets = new ArrayList<>();
    ArrayList<Integer> pot = new ArrayList<>();
    int n = objects.length;
    int p = 1;
    if(m==0)
        return subsets;
    for(int i=0; i<=n; i++){
        pot.add(p);
        p*=2;
    }
    for(int i=1; i<p; i++){
        boolean[] binArray = new boolean[n];
        Arrays.fill(binArray, false);
        int y = i;
        int sum = 0;
        for(int j = n-1; j>=0; j--){
            int currentPot = pot.get(j);
            if(y >= currentPot){
                binArray[j] = true;
                y -= currentPot;
                sum++;
            }
            if(y<=0)
                break;
        }
        if(sum==m){
            ArrayList<Object> subsubset = new ArrayList<>();
            for(int j=0; j < n; j++){
                if(binArray[j]){
                    subsubset.add(objects[j]);
                }
            }
            subsets.add(subsubset);
        }
    }

    return subsets;
}

Answer 3

If you are looking for Iterator pattern answer then here you go.

public static <T> Iterable<List<T>> getList(final Iterable<? extends T> list) {

    List<List<T>> listOfList = new ArrayList<>();

    for (T t: list)
        listOfList.add(Collections.singletonList(t));

    return listOfList;
}
public static <T> Iterable<List<T>> getIterable(final Iterable<? extends T> list, final int size) {

    final List<T> vals = new ArrayList<>();
    int numElements = 0;
    for (T t : list) {
        vals.add(t);
        numElements++;
    }

    if (size == 1) {
        return getList(vals);
    }
    if (size == numElements) {
        return Collections.singletonList(vals);
    }

    return new Iterable<List<T>>() {

        @Override
        public Iterator<List<T>> iterator() {
            return new Iterator<List<T>>() {

                int currPos = 0;                    
                Iterator<List<T>> nextIterator = getIterable(
                    vals.subList(this.currPos + 1, vals.size()), size - 1).iterator();

                @Override
                public boolean hasNext() {
                    if ((this.currPos < vals.size()-2) && (this.currPos+size < vals.size()))
                        return true;
                    return false;
                }

                @Override
                public List<T> next() {
                    if (!nextIterator.hasNext()) {
                        this.currPos++;
                        nextIterator = getIterable(vals.subList(this.currPos+1, vals.size()), size-1).iterator();
                    }
                    final List<T> ret = new ArrayList<>(nextIterator.next());
                    ret.add(0, vals.get(this.currPos));
                    return ret;
                }
            };
        }
    };
}

Answer 4

Check out my solution

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


 public class Subset_K {
public static void main(String[]args)
{
    Set<String> x;
    int n=4;
    int k=2;
    int arr[]={1,2,3,4};
    StringBuilder sb=new StringBuilder();
    for(int i=1;i<=(n-k);i++)
        sb.append("0");
    for(int i=1;i<=k;i++)
        sb.append("1");
    String bin=sb.toString();
    x=generatePerm(bin);
    Set<ArrayList <Integer>> outer=new HashSet<ArrayList <Integer>>();
    for(String s:x){
        int dec=Integer.parseInt(s,2);
        ArrayList<Integer> inner=new ArrayList<Integer>();
        for(int j=0;j<n;j++){
            if((dec&(1<<j))>0)
                inner.add(arr[j]);
        }
        outer.add(inner);
    }
    for(ArrayList<?> z:outer){
        System.out.println(z);
    }
}

    public static Set<String> generatePerm(String input)
{
    Set<String> set = new HashSet<String>();
    if (input == "")
        return set;

    Character a = input.charAt(0);

    if (input.length() > 1)
    {
        input = input.substring(1);

        Set<String> permSet = generatePerm(input);

        for (String x : permSet)
        {
            for (int i = 0; i <= x.length(); i++)
            {
                set.add(x.substring(0, i) + a + x.substring(i));
            }
        }
    }
    else
    {
        set.add(a + "");
    }
    return set;
}
}

I am working on a 4 element set for test purpose and using k=2. What I try to do is initially generate a binary string where k bits are set and n-k bits are not set. Now using this string I find all the possible permutations of this string. And then using these permutations I output the respective element in the set. Would be great if someone could tell me about the complexity of this problem.

Answer 5

Recursion is your friend for this task.

For each element - "guess" if it is in the current subset, and recursively invoke with the guess and a smaller superset you can select from. Doing so for both the "yes" and "no" guesses - will result in all possible subsets.
Restraining yourself to a certain length can be easily done in a stop clause.

Java code:

private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
    //successful stop clause
    if (current.size() == k) {
        solution.add(new HashSet<>(current));
        return;
    }
    //unseccessful stop clause
    if (idx == superSet.size()) return;
    Integer x = superSet.get(idx);
    current.add(x);
    //"guess" x is in the subset
    getSubsets(superSet, k, idx+1, current, solution);
    current.remove(x);
    //"guess" x is not in the subset
    getSubsets(superSet, k, idx+1, current, solution);
}

public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
    List<Set<Integer>> res = new ArrayList<>();
    getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
    return res;
}

Invoking with:

List<Integer> superSet = new ArrayList<>();
superSet.add(1);
superSet.add(2);
superSet.add(3);
superSet.add(4);
System.out.println(getSubsets(superSet,2));

Will yield:

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