How to Get All Subsets of an Array

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 get all subsets of an array?

 string[] source = new string[] { "dog", "cat", "mouse" };
 for (int i = 0; i < Math.Pow(2, source.Length); i++)
 {
     string[] combination = new string[source.Length];
     for (int j = 0; j < source.Length; j++)
     {
         if ((i & (1 << (source.Length - j - 1))) != 0)
         {
             combination[j] = source[j];
         }
    }
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]);
}

Finding all subsets of specified size

Let us call n the size of the array and k the number of elements to be out in a subarray.

Let us consider the first element A[0] of the array A.

If this element is put in the subset, the problem becomes a (n-1, k-1) similar problem.

If not, it becomes a (n-1, k) problem.

This can be simply implemented in a recursive function.

We just have to pay attention to deal with the extreme cases k == 0 or k > n.

During the process, we also have to keep trace of:

• n: the number of remaining elements of A to consider

• k: the number of elements that remain to be put in the current subset

• index: the index of the next element of A to consider

• The current_subset array that memorizes the elements already selected.

  Here is a simple code in c++ to illustrate the algorithm

Output

For 5 elements and subsets of size 3:

3 4 5
2 4 5
2 3 5
2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3

#include    <iostream>
#include    <vector>

void print (const std::vector<std::vector<int>>& subsets) {
    for (auto &v: subsets) {
        for (auto &x: v) {
            std::cout << x << " ";
        }
        std::cout << "\n";
    }
}
//  n: number of remaining elements of A to consider
//  k: number of elements that remain to be put in the current subset
//  index: index of next element of A to consider

void Get_subset_rec (std::vector<std::vector<int>>& subsets, int n, int k, int index, std::vector<int>& A, std::vector<int>& current_subset) {
    if (n < k) return;   
    if (k == 0) {
        subsets.push_back (current_subset);
        return;
    }  
    Get_subset_rec (subsets, n-1, k, index+1, A, current_subset);
    current_subset.push_back(A[index]);
    Get_subset_rec (subsets, n-1, k-1, index+1, A, current_subset);
    current_subset.pop_back();         // remove last element
    return;
}

void Get_subset (std::vector<std::vector<int>>& subsets, int subset_length, std::vector<int>& A) {
    std::vector<int> current_subset;
    Get_subset_rec (subsets, A.size(), subset_length, 0, A, current_subset);
}

int main () {
    int subset_length = 3;     // subset size
    std::vector A = {1, 2, 3, 4, 5};
    int size = A.size();
    std::vector<std::vector<int>> subsets;

    Get_subset (subsets, subset_length, A);
    std::cout << subsets.size() << "\n";
    print (subsets);
}

Live demo

Finding all subsets of an array and sum of the individual subsets to an different array in c language

I'm afraid your solution does not work: you are only summing contiguous subsets. The assignment tells you to find all subsets.

A simple way to enumerate all subsets is to iterate with a loop index from 0 to 2**n - 1 and to consider each of the low order n bits in the index to be an indicator of inclusion in the current subset. With 32 bit ints, you can use a unsigned int as an index for sets of up to 30 elements if you can allocate the output array (4GB). Larger sets would require a 64 bit index and generate a truly huge output array.

Here is the code:

#include <stdlib.h>

int *compute_subset_sums(int *a, int n) {
    int *aa = calloc(1ULL << n, sizeof(int));
    if (aa != NULL) {
        /*---------------------cut here--------------------*/
        for (size_t i = 0; (i >> n) == 0; i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if ((i >> j) & 1)
                    sum += a[j];
            }
            aa[i] = sum;
        }
        /*---------------------cut here--------------------*/
    }
    return aa;
}

How to get all subsets of a set? (powerset)

The Python itertools page has exactly a powerset recipe for this:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Output:

>>> list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

If you don't like that empty tuple at the beginning, you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination.

Generate all subset of an array bigquery

One approach to this problem is to generate all the integers between 1 and 2^ - 1. The bit pattern then represents all the combinations.

You can use bit comparisons to extract the combos:

with ar as (
       select  [1,2,3,4] as ar
      )
select n,
       (select array_agg(case when n & (1<<pos) <> 0
                              then ar.ar[offset(pos)]
                         end ignore nulls)
        from ar cross join
             unnest(generate_array(0, x.cnt - 1)) pos
       ) as combo
from ar cross join
     (select count(*) as cnt
      from ar cross join
           unnest(ar.ar) x
     ) x cross join
     unnest(generate_array(1, cast(power(2, x.cnt) - 1 as int64))) n

Find all subsets of length k in an array

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]]

Finding all subsets of a set of arrays (perl)

Check https://metacpan.org/pod/List::PowerSet

use strict;
use warnings;

use List::PowerSet 'powerset_lazy';

my @arr = (
        [1,2],
        [2,3,4],
);
my %hash;
for my $v (@arr) {
    my $ps = powerset_lazy(@$v);
    while (my $set = $ps->()) {
        my $str = join ",", @$set;
        next if $hash{$str}++;
        print "($str)\n";
    }
}

output

(1,2)
(2)
(1)
()
(2,3,4)
(3,4)
(2,4)
(4)
(2,3)
(3)

---

Related Topics