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

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#combination`and`Array#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]
[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, 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], , [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`

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

Tags:

Updated: