Generate All "Unique" Subsets of a Set (Not a Powerset)

Generate all unique subsets of a set (not a powerset)

It sounds like what you are looking for are the partitions of a set/array.

One way of doing this is recursively:

• a 1 element array [x] has exactly one partition
• if x is an array of the form x = [head] + tail, then the partitions of x are generated by taking each partition of tail and adding head to each possible. For example if we were generating the partitions of [3,2,1] then from the partition [[2,1]] of [2,1] we can either add 3 to to [2,1] or as a separate element, which gives us 2 partitions [[3,2,1] or [[2,1], [3]] of the 5 that [1,2,3] has

A ruby implementation looks a little like

def partitions(x)
  if x.length == 1
   [[x]]
  else
    head, tail = x[0], x[1, x.length-1]
    partitions(tail).inject([]) do |result, tail_partition|
      result + partitions_by_adding_element(tail_partition, head)
    end
  end
end

def partitions_by_adding_element(partition, element)
  (0..partition.length).collect do |index_to_add_at|
    new_partition = partition.dup
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element]
    new_partition
  end
end

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.

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

Creating all subsets recursively without using array

Recursive algorithms are very memory intensive. Here algorithm for n <= 31

#include <iostream>

void bin(unsigned bit, unsigned k, unsigned max_bits) {
    if (bit == max_bits) {
        std::cout << "{";
        bin(bit - 1, k, max_bits);
    }
    else {
        if ((k & (1u << bit)) != 0) {
            std::cout << (max_bits - bit) << " ";
        }
        if (bit != 0) {
            bin(bit - 1, k, max_bits);
        }
        else {
            std::cout << "}" << std::endl;
        }
    }
}

void print(unsigned k, unsigned n, unsigned max_bits) {
    bin(max_bits, k, max_bits);
    if (k != 0) {
        print(k - 1, n, max_bits);
    }
}

int main()
{
    unsigned n;
    std::cin >> n;
    print((1u << n) - 1u, 1u<<n, n);
    return 0;
}

First recursion print enumerates k from 2^n-1 to 0, second recursion bin enumerates all bits of k and print non-zero bits. For example, max_bits = 5 and k = 19 is 10011b = 16 + 2 + 1 = 2^4 + 2^1 + 2^0, bits 4,1,0 interoperate as set {5-4,5-1,5-0} => {1,4,5}

Leetcode 78: Subsets confused why duplicate subsets are generated

No need to have the second recursive call, the working solution is:

def subsets(nums: List[int]) -> List[List[int]]:
    subsets = []
    expected_subsets = 2 ** len(nums)

    def generate_subset(subset, nums):
        # base case , gone too far
        if len(subsets) >= expected_subsets:
            return
        if len(subsets) < expected_subsets:
            subsets.append(subset)
        for i in range(len(nums)):
            generate_subset(subset + [nums[i]], nums[i+1:])

    generate_subset([], nums)
    return subsets

print(subsets([1, 2, 3]))

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

Try to manually go through recursion calls and you understand why the previous version didn't work, took me a while. On that recursive call, you get current and recursively process the rest.

---

This is an example of explicit pick/don't pick approach:

def subsets(nums: List[int]) -> List[List[int]]:
    result = []

    def powerset(alist, index, curr):
        if index == len(alist):
            result.append(curr)
            return

        powerset(alist, index + 1, curr + [alist[index]])  
        powerset(alist, index + 1, curr)

    powerset(nums, 0, [])
    return result

How do you calculate the total number of all possible unique subsets from a set with repeats?

Take the product of all the (frequencies + 1).

For example, in {A,B,B}, the answer is (1+1) [the number of As] * (2+1) [the number of Bs] = 6.

In the second example, count(A) = 2 and count(B) = 2. Thus the answer is (2+1) * (2+1) = 9.

The reason this works is that you can define any subset as a vector of counts - for {A,B,B}, the subsets can be described as {A=0,B=0}, {A=0,B=1}, {0,2}, {1,0}, {1,1}, {1,2}.

For each number in counts[] there are (frequencies of that object + 1) possible values. (0..frequencies)

Therefore, the total number of possiblities is the product of all (frequencies+1).

The "all unique" case can also be explained this way - there is one occurence of each object, so the answer is (1+1)^|S| = 2^|S|.

create a list of all the subsets of a given list in python 3.x

You can use itertools.combinations to get the combinations:

>>> import itertools
>>> xs = [1, 2, 3]

>>> itertools.combinations(xs, 2)  # returns an iterator
<itertools.combinations object at 0x7f88f838ff48>
>>> list(itertools.combinations(xs, 2))  # yields 2-length subsequences
[(1, 2), (1, 3), (2, 3)]

>>> for i in range(0, len(xs) + 1):  # to get all lengths: 0 to 3
...     for subset in itertools.combinations(xs, i):
...         print(list(subset))
... 
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

combining with list comprehension, you will get what you want:

>>> [list(subset) for i in range(0, len(xs) + 1)
                  for subset in itertools.combinations(xs, i)]
[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Generate a powerset of a set without keeping a stack in Erlang or Ruby

Edit: Added the enumerator (as @Jörg W Mittag) if no block is given.

class Array
  def powerset
    return to_enum(:powerset) unless block_given?
    1.upto(self.size) do |n|
      self.combination(n).each{|i| yield i}
    end
  end
end
# demo
['a', 'b', 'c'].powerset{|item| p item} # items are generated one at a time
ps = [1, 2, 3, 4].powerset # no block, so you'll get an enumerator 
10.times.map{ ps.next } # 10.times without a block is also an enumerator

Output

["a"]
["b"]
["c"]
["a", "b"]
["a", "c"]
["b", "c"]
["a", "b", "c"]
[[1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Get all possible subsets - preserving order

I've already answered this question for Python, so I quickly ported my solution over to Ruby:

def spannings(lst)
  return enum_for(:spannings, lst) unless block_given?

  yield [lst]
  (1...lst.size).each do |i|
    spannings(lst[i..-1]) do |rest|
      yield [lst[0,i]] + rest
    end
  end
end

p spannings([1,2,3,4]).to_a

See my other answer for a complete explanation of how and why this works.

---

Related Topics