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

   #include<iostream>
   #include<cstdio>
   #include<vector>
   using namespace std;
   vector<int> v;
   vector<vector<int> > result;

  void subset(int arr[],int k,int n,int idx){
  if(idx==n)
 return;

if(k==1){
    for(int i=idx;i<n;i++)
     {
        v.push_back(arr[i]);
        result.push_back(v);
        v.pop_back();
     }
}

 for(int j=idx;j<n;j++) {
  v.push_back(arr[j]);
  subset(arr,k-1,n,j+1);
  v.pop_back();
  }
 }

int main(){
int arr[] = {1,2,3,4,5,6,7};
int k = 4;
int n =sizeof(arr)/sizeof(arr[0]);
subset(arr,k,n,0);

for(int i = 0;i<result.size();i++)
 { 
  for(int j = 0;j<result[i].size();j++)
   {
     cout << result[i][j] << " ";
   }
   cout << endl;
 }
}

Answer 2

JavaScript implementation:

var subsetArray = (function() {
  return {
    getResult: getResult
  }

  function getResult(array, n) {

    function isBigEnough(value) {
      return value.length === n;
    }

    var ps = [
      []
    ];
    for (var i = 0; i < array.length; i++) {
      for (var j = 0, len = ps.length; j < len; j++) {
        ps.push(ps[j].concat(array[i]));
      }
    }
    return ps.filter(isBigEnough);
  }
})();



 var arr = [1, 2, 3, 4,5,6,7,8,9];
 console.log(subsetArray.getResult(arr,2));

Answer 3

This is an implemation in F#:

// allSubsets: int -> int -> Set<Set<int>>
let rec allSubsets n k =
    match n, k with
    | _, 0 -> Set.empty.Add(Set.empty)
    | 0, _ -> Set.empty
    | n, k -> Set.union (Set.map (fun s -> Set.add n s) (allSubsets (n-1) (k-1)))
                        (allSubsets (n-1) k)

You can try it in the F# REPL:

> allSubsets 3 2;;

val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [2; 3]]

> allSubsets 4 2;;

val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [1; 4]; set [2; 3]; set [2; 4]; set [3; 4]]

This Java class implements the same algorithm:

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

public class AllSubsets {

    public static Set<Set<Integer>> allSubsets(int setSize, int subsetSize) {
        if (subsetSize == 0) {
            HashSet<Set<Integer>> result = new HashSet<>();
            result.add(new HashSet<>());
            return result;
        }
        if (setSize == 0) {
            return new HashSet<>();
        }
        Set<Set<Integer>> sets1 = allSubsets((setSize - 1), (subsetSize - 1));
        for (Set<Integer> set : sets1) {
            set.add(setSize);
        }
        Set<Set<Integer>> sets2 = allSubsets((setSize - 1), subsetSize);
        sets1.addAll(sets2);
        return sets1;
    }
}

If you do not like F# or Java then visit this website. It lists solutions to your particular problem in various programming languages:

http://rosettacode.org/wiki/Combinations

Answer 4

Here is an iterative version in python. Essence of it is increment_counters() function which returns all possible combinations. We know it needs to be called C(n,r) times.

def nchooser(n,r):
    """Calculate the n choose r manual way"""
    import math
    f = math.factorial
    return f(n) / f(n-r) / f(r)

def increment_counters(rc,r,n):
    """This is the essense of the algorithm. It generates all possible indexes.
    Ex: for n = 4, r = 2, rc will have values (0,1),(0,2),(0,3),(1,2),(1,3),(2,3).
    You may have better understanding if you print all possible 35 values for
    n = 7, r = 3."""

    rc[r-1] += 1     # first increment the least significant counter
    if rc[r-1] < n:  # if it does not overflow, return
        return

    # overflow at the last counter may cause some of previous counters to overflow
    # find where it stops (ex: in n=7,r=3 case, 1,2,3 will follow 0,5,6)
    for i in range(r-2,-1,-1): # from r-2 to 0 inclusive
        if rc[i] < i+n-r:
            break
    # we found that rc[i] will not overflow. So, increment it and reset the
    # counters right to it. 
    rc[i] += 1
    for j in range(i+1,r):
        rc[j] = rc[j-1] + 1

def combinations(lst, r):
    """Return all different sub-lists of size r"""
    n = len(lst)
    rc = [ i for i in range(r) ]  # initialize counters
    res = []
    for i in range(nchooser(n,r)): # increment the counters max possible times 
        res.append(tuple(map(lambda k: lst[k],rc)))
        increment_counters(rc,r,n)

    return res

Answer 5

Use a bit vector representation of the set, and use an algorithm similar to what std::next_permutation does on 0000.1111 (n-k zeroes, k ones). Each permutation corresponds to a subset of size k.

Answer 6

Please check my solution:-

private static void printPermutations(List<Integer> list, int subSetSize) {
    List<Integer> prefixList = new ArrayList<Integer>();
    printPermutations(prefixList, list, subSetSize);
}

private static void printPermutations(List<Integer> prefixList, List<Integer> list, int subSetSize) {
    if (prefixList.size() == subSetSize) {
        System.out.println(prefixList);
    } else {
        for (int i = 0; i < list.size(); i++) {
            Integer removed = list.remove(i);
            prefixList.add(removed);
            printPermutations(prefixList, list, subSetSize);
            prefixList.remove(removed);
            list.add(i, removed);
        }
    }
}

This is similar to String permutations:-

private static void printPermutations(String str) {
    printAllPermutations("", str);
}

private static void printAllPermutations(String prefix, String restOfTheString) {
    int len = restOfTheString.length();
    System.out.println(prefix);
    for (int i = 0; i < len; i++) {
        printAllPermutations(prefix + restOfTheString.charAt(i), restOfTheString.substring(0, i) + restOfTheString.substring(i + 1, len));
    }
}