Find All Possible Subset Combos in an Array

Find all possible subset combos in an array?

After stealing this JavaScript combination generator, I added a parameter to supply the minimum length resulting in,

var combine = function(a, min) {
    var fn = function(n, src, got, all) {
        if (n == 0) {
            if (got.length > 0) {
                all[all.length] = got;
            }
            return;
        }
        for (var j = 0; j < src.length; j++) {
            fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
        }
        return;
    }
    var all = [];
    for (var i = min; i < a.length; i++) {
        fn(i, a, [], all);
    }
    all.push(a);
    return all;
}

To use, supply an array, and the minimum subset length desired,

var subsets = combine([1, 2, 3], 2);

Output is,

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

All possible combinations and subsets of an array in java

You should apply 2 steps:

1. You need to find all subsets of the given input. This set of subsets is called the Power Set.
2. For each element of this power set (that is, for each subset), you need all Permutations.

This implementation uses some utility classes from a combinatorics project. The output also contains the empty set {} and is not ordered by the size, but this may easily be done as a postprocessing step.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class AllCombinations {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1,2,4,5);

        PowerSetIterable<Integer> powerSet = 
            new PowerSetIterable<Integer>(list);
        for (List<Integer> subset : powerSet)
        {
            PermutationIterable<Integer> permutations = 
                new PermutationIterable<Integer>(subset);
            for (List<Integer> permutation : permutations) {
                System.out.println(permutation);
            }
        }

    }
}

//From https://github.com/javagl/Combinatorics
class PowerSetIterable<T> implements Iterable<List<T>> {
    private final List<T> input;
    private final int numElements;
    public PowerSetIterable(List<T> input) {
        this.input = input;
        numElements = 1 << input.size();
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {
            private int current = 0;

            @Override
            public boolean hasNext() {
                return current < numElements;
            }

            @Override
            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException("No more elements");
                }
                List<T> element = new ArrayList<T>();
                for (int i = 0; i < input.size(); i++) {
                    long b = 1 << i;
                    if ((current & b) != 0) {
                        element.add(input.get(i));
                    }
                }
                current++;
                return element;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException(
                        "May not remove elements from a power set");
            }
        };
    }
}
//From https://github.com/javagl/Combinatorics
class PermutationIterable<T> implements Iterable<List<T>> {
    public static int factorial(int n) {
        int f = 1;
        for (int i = 2; i <= n; i++) {
            f = f * i;
        }
        return f;
    }
    private final List<T> input;
    private final int numPermutations;
    public PermutationIterable(List<T> input) {
        this.input = input;
        numPermutations = factorial(input.size());
    }

    @Override
    public Iterator<List<T>> iterator() {
        if (input.size() == 0) {
            return Collections.<List<T>> singletonList(
                    Collections.<T> emptyList()).iterator();
        }
        return new Iterator<List<T>>() {
            private int current = 0;

            @Override
            public boolean hasNext() {
                return current < numPermutations;
            }

            @Override
            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException("No more elements");
                }
                // Adapted from http://en.wikipedia.org/wiki/Permutation
                List<T> result = new ArrayList<T>(input);
                int factorial = numPermutations / input.size();
                for (int i = 0; i < result.size() - 1; i++) {
                    int tempIndex = (current / factorial) % (result.size() - i);
                    T temp = result.get(i + tempIndex);
                    for (int j = i + tempIndex; j > i; j--) {
                        result.set(j, result.get(j - 1));
                    }
                    result.set(i, temp);
                    factorial /= (result.size() - (i + 1));
                }
                current++;
                return result;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException(
                        "May not remove elements from a permutation");
            }
        };
    }
}

How to find all subsets of a set in JavaScript? (Powerset of array)

Here is one more very elegant solution with no loops or recursion, only using the map and reduce array native functions.

const getAllSubsets =       theArray => theArray.reduce(        (subsets, value) => subsets.concat(         subsets.map(set => [value,...set])        ),        [[]]      );
console.log(getAllSubsets([1,2,3]));

How to find all subsets of a set in JavaScript? (Powerset of array)

Here is one more very elegant solution with no loops or recursion, only using the map and reduce array native functions.

const getAllSubsets =       theArray => theArray.reduce(        (subsets, value) => subsets.concat(         subsets.map(set => [value,...set])        ),        [[]]      );
console.log(getAllSubsets([1,2,3]));

Given an array, how to generate all combinations of subset size k?

A recursive solution to find k-subset permutations (in pseudo-code):

kSubsetPermutations(partial, set, k) {
    for (each element in set) {
        if (k equals 1) {
            store partial + element
        }
        else {
            make copy of set
            remove element from copy of set
            recurse with (partial + element, copy of set, k - 1)
        }
    }
}

Here's a run-through for an example:

input: [a,b,c,d,e]

k: 3

partial = [], set = [a,b,c,d,e], k = 3
    partial = [a], set = [b,c,d,e], k = 2
        partial = [a,b], set = [c,d,e], k = 1 -> [a,b,c], [a,b,d], [a,b,e]
        partial = [a,c], set = [b,d,e], k = 1 -> [a,c,b], [a,c,d], [a,c,e]
        partial = [a,d], set = [b,c,e], k = 1 -> [a,d,b], [a,d,c], [a,d,e]
        partial = [a,e], set = [b,c,d], k = 1 -> [a,e,b], [a,e,c], [a,e,d]
    partial = [b], set = [a,c,d,e], k = 2
        partial = [b,a], set = [c,d,e], k = 1 -> [b,a,c], [b,a,d], [b,a,e]
        partial = [b,c], set = [a,d,e], k = 1 -> [b,c,a], [b,c,d], [b,c,e]
        partial = [b,d], set = [a,c,e], k = 1 -> [b,d,a], [b,d,c], [b,d,e]
        partial = [b,e], set = [a,c,d], k = 1 -> [b,e,a], [b,e,c], [b,e,d]
    partial = [c], set = [a,b,d,e], k = 2
        partial = [c,a], set = [b,d,e], k = 1 -> [c,a,b], [c,a,d], [c,a,e]
        partial = [c,b], set = [a,d,e], k = 1 -> [c,b,a], [c,b,d], [c,b,e]
        partial = [c,d], set = [a,b,e], k = 1 -> [c,d,a], [c,d,b], [c,d,e]
        partial = [c,e], set = [a,b,d], k = 1 -> [c,e,a], [c,e,b], [c,e,d]
    partial = [d], set = [a,b,c,e], k = 2
        partial = [d,a], set = [b,c,e], k = 1 -> [d,a,b], [d,a,c], [d,a,e]
        partial = [d,b], set = [a,c,e], k = 1 -> [d,b,a], [d,b,c], [d,b,e]
        partial = [d,c], set = [a,b,e], k = 1 -> [d,c,a], [d,c,b], [d,c,e]
        partial = [d,e], set = [a,b,c], k = 1 -> [d,e,a], [d,e,b], [d,e,c]
    partial = [e], set = [a,b,c,d], k = 2
        partial = [e,a], set = [b,c,d], k = 1 -> [e,a,b], [e,a,c], [e,a,d]
        partial = [e,b], set = [a,c,d], k = 1 -> [e,b,a], [e,b,c], [e,b,d]
        partial = [e,c], set = [a,b,d], k = 1 -> [e,c,a], [e,c,b], [e,c,d]
        partial = [e,d], set = [a,b,c], k = 1 -> [e,d,a], [e,d,b], [e,d,c]

function kSubsetPermutations(set, k, partial) {    if (!partial) partial = [];                 // set default value on first call    for (var element in set) {        if (k > 1) {            var set_copy = set.slice();         // slice() creates copy of array            set_copy.splice(element, 1);        // splice() removes element from array            kSubsetPermutations(set_copy, k - 1, partial.concat([set[element]]));        }                                       // a.concat(b) appends b to copy of a        else document.write("[" + partial.concat([set[element]]) + "] ");    }}kSubsetPermutations([1,2,3,4,5], 3);

Creating all possible subset of k and m combinations of n items in C

It's more trickier than I primarly thinked.

Okay, so lets say you have "n" uniq element.
The total amout of uniq possibility is "n!" (so for 5 element, you have 120 possibility).

Let's say you want to make "group" of "k" number.

So if n = 5 and k = 2, you end up with your example :

{0, 1}, {2, 3}, {4}.

Now, that's where the fun begin :
In order to know if the current proposition is not a duplicate, you can discard every proposition for which the first number in every complete group is not sorted.

for example :

{0, 1}, {2, 3}, {4}.

here, 1 and 3 are useless because that not the first value of a complete group, and 4 is part of an incomplete group.
So what is interesting is

{0, ?}, {2, ?}, {?}.

Is 0, 2 sorted ? Yes, so you can keep this proposition.
That means that if you have

{2, 3}, {0, 1}, {4}.

It's no good, because

{2, ?}, {0, ?}, {?}.

2, 0 is not sorted.

---

If you have n = 6 and k = 2, then is

{0, 2}, {3, 4}, {1, 5}

valid ? No, because 0 3 1 is not sorted.
And you can see that

{0, 2}, {1, 5} , {3, 4}

is the valid sorted proposition.

---

Now, is there a possibility to calculate how many valid proposition we will have if we know n and k ?

Yes.

Maybe.
I think ...
I will update if I can found something.

Edit :

Aaaaaannnd, here an implementation. A little fun to do ...
It based on the previous algorithm, so of course if my algorithm is false, then this code is false.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 5
#define K 2

void Comb_Display(int proposition[N])
{
    printf("{");
    for (int i = 0; i < N; ++i) {
        if (i && i % K == 0) {
            printf("} {");
        }
        printf("%d%s", proposition[i], (i && (i + 1) % K == 0) || i + 1 >= N ? "" : ", ");
    }
    printf("}\n");
}

bool Comb_Valid(int proposition[N])
{
    int nbGroup = N / K;

    if (nbGroup == 1) {
        return (true);
    }
    for (int i = 0; i < nbGroup; i += K) {
        if (proposition[i] > proposition[i + K]) {
            return (false);
        }
    }
    return (true);
}

void Comb_MakeMagicPlease(int numberAvailable[N], int proposition[N], int ind)
{
    // We are at the end of the array, so we have a proposition
  if (ind >= N) {
    printf("%s : ", Comb_Valid(proposition) ? "OK" : "  "); // O = Valide, ' ' = invalide
    Comb_Display(proposition);
    return;
  }

  // We scan "numberAvailable" in order to find the first number available
  for (int i = 0; i < N; i++) {
    if (numberAvailable[i] != -1) {
        int number = numberAvailable[i];

        numberAvailable[i] = -1; // We mark the number as not available

      proposition[ind] =  number;
      Comb_MakeMagicPlease(numberAvailable, proposition, ind + 1);
      numberAvailable[i] = number; // we mark the number as available
    }
  }
}

int main(void)
{
  int numberAvailable[N];
  int proposition[N];

  for (int i = 0; i < N; ++i) {
    numberAvailable[i] = i + 1;
  }

  Comb_MakeMagicPlease(numberAvailable, proposition, 0);
  return 0;
}

---

Related Topics