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]));
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 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;
}
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
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]);
}
how to find possible subsets of a given array?
The table is entirely unnecessary.
One idea is to imagine a bit wise representation of each weekday, whereby:
Monday = 1
Tuesday = 2
Wednesday = 4
Thursday = 8
Etc
Every combination of days can then be represented by a single number from 1 to 127.
See Working with bitcode for a fuller explanation
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]]
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.
Related Topics
How to Get a JSON String from Url
Adding Distance to a Gps Coordinate
Request Exceeds the Configured Maxquerystringlength When Using [Authorize]
Order of Serialized Fields Using JSON.Net
How to De-Elevate Privileges for a Child Process
System.Text.JSON: How to Specify a Custom Name for an Enum Value
How to Use Assert to Verify That an Exception Has Been Thrown
Implement Validation for Wpf Textboxes
Copy Constructor Versus Clone()
How to Convert JavaScript Date Object to Ticks
How Does Hashset Compare Elements for Equality
Convert Variable to Type Only Known at Run-Time