# [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`

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

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

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

`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(2^{N} N). From 2^{N}, 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(2^{N}). 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`

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

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

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

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