[Ruby] Enumerate a subset of the array given in Ruby (+α)

3 minute read

When I was solving the problem of competitive programming, sometimes I needed to create and handle the state of each case rather than just counting the number of cases. In Ruby, Array#combinationandArray#repeated_permutation are available, but when I want something else, I can’t assemble it and take time.

So I also practice and create the method I wanted at that time.

subset

Sometimes you want to cover patterns that include/do not include ** for each element, such as when you want to solve brute force. If the number is 2 ** ary.size.

Use ### Array#combination The number of elements can range from 0 to ary.size, so you can list the combinations for each. It’s fast and easy because **most of the processing is left to Ruby’s internal implementation.

each_subset.rb


def each_subset(ary, &block)
0.upto(ary.size) {|n| ary.combination(n, &block)}
end

if $0 == __FILE__
each_subset([*0..2]) {|subset| p subset}
end

output


[]
[0]
[1]
[2]
[0, 1]
[0, 2]
[1, 2]
[0, 1, 2]

use binary notation

Let’s make the 1 0 in the binary notation of the order of enumeration k (starting from 0) correspond to the inclusion/exclusion of each element as it is.

It’s like this if you do it honestly. Ruby gets the value of the bit at the i bit with Integer#[] it can.

each_subset.rb


def each_subset(ary, &block)
(1 << ary.size).times do |k|
subset = ary.select.with_index {|_, i| k[i] == 1}
block.call(subset)
end
end

if $0 == __FILE__
each_subset([*0..2]) {|subset| p subset}
end

output


[]
[0]
[1]
[0, 1]
[2]
[0, 2]
[1, 2]
[0, 1, 2]

Since the leading element 0 of ary is associated with the least significant bit (=even and odd), the presence/absence is switched every time, while the trailing element 2 is associated with the most significant bit, so it is fixed only in the second half. Is appearing.

As you can see, the implementation is a fixed number of double loops, and the time complexity is O(2N N). From 2N, N is not a big deal, so there should be no problem in practical use (the number of elements is about 16). If anything, I’m more concerned about just evaluating with #select.


Try O(2N). Implement it by recursion and drop it into the process when there is one less ary.

  • Since the objects are reused by making heavy use of destructive methods, they are protected by Array#dup for safety. If you remove all this, it will be more than twice as fast.

each_subset.rb


def each_subset(ary, selected = [], &block)
if ary.empty?
block.call(selected.dup) # Duplicate because array is the same object is too dangerous
return
end

ary = ary.dup # Duplicate the input array without breaking it

elem = ary.pop
not include each_subset(ary, selected, &block) # elem
selected.unshift(elem)
each_subset(ary, selected, &block) contains # elem
selected.shift
# ary << elem # Not needed if duplicated

return # Returns nil for the moment
end

if $0 == __FILE__
each_subset([*0..2]) {|subset| p subset}
end

<!–


Non-recursive version, and internally record all patterns in an array before executing (because it is easy).

each_subset.rb


def each_subset(ary, &block)
subsets = [[]]

ary.each do |elem|
subsets.concat(subsets.map {|ss| [*ss, elem] })
end

return subsets.each(&block)
end

if $0 == __FILE__
each_subset([*0..2]) {|subset| p subset}
end
  • ->

Split

For ary = [0, 1, 2, 3, 4], we want to make, for example, [[0, 1], [2], [3, 4]].

From a different point of view, it means “put/not put a delimiter between each element of an array”, so the number of cases is 2 ** (ary.size-1). Since it is a mystery what should be returned when it is an empty array, I will make it a convenient form for implementation.

This is also implemented recursively. If you extract some groups from ary, you can make a group with the remaining ones.

each_split.rb


def each_split(ary, selected = [], &block)
if ary.empty?
block.call(selected.map(&:dup)) # Duplicate because array is the same object is too dangerous
return
end

Operate to keep #ary == part1 + part2
part1 = []
part2 = ary.dup # Duplicate the input array without breaking it

selected << part1
until part2.empty?
part1 << part2.shift # Move split position to the right
each_split(part2, selected, &block)
end
selected.pop

# ary.replace(part1) # Not needed if duplicated

return # Returns nil for the moment
end

if $0 == __FILE__
each_split([*0..4]) {|sp| p sp}
end

output


[[0], [1], [2], [3], [4]]
[[0], [1], [2], [3, 4]]
[[0], [1], [2, 3], [4]]
[[0], [1], [2, 3, 4]]
[[0], [1, 2], [3], [4]]
[[0], [1, 2], [3, 4]]
[[0], [1, 2, 3], [4]]
[[0], [1, 2, 3, 4]]
[[0, 1], [2], [3], [4]]
[[0, 1], [2], [3, 4]]
[[0, 1], [2, 3], [4]]
[[0, 1], [2, 3, 4]]
[[0, 1, 2], [3], [4]]
[[0, 1, 2], [3, 4]]
[[0, 1, 2, 3], [4]]
[[0, 1, 2, 3, 4]]

Tags:

Updated: