When I was solving a problem of competitive programming, I sometimes needed to ** create and process the state of each case ** rather than just counting the number of cases. In Ruby, [ʻArray # combination](https://docs.ruby-lang.org/ja/latest/method/Array/i/combination.html) and [ʻArray#repeated_permutation](https: // docs.ruby-lang.org/ja/latest/method/Array/i/repeated_permutation.html) etc. are prepared, but when I want other things, I can not assemble them quickly and it takes time.
So I will try to make the method I wanted at that time, also as a practice.
When you want to solve brute force, you may want to ** cover the patterns that are included / not included for each element **. The number of cases is 2 ** ary.size.
The number of elements can be from 0 to ʻary.size`, so you can list the combinations for each. It's easy and ** it's fast because most of the processing is left to the internal implementation of Ruby **.
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]
Try to make the order of enumeration 1`` 0 when the binary notation k (starting from 0) corresponds to the inclusion / exclusion of each element as it is.
If you do it obediently, it looks like this. Ruby gets the value of the ʻibit with [ʻInteger # []](https://docs.ruby-lang.org/ja/latest/method/Integer/i/=5b=5d.html) 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 first element 0 of ʻary corresponds to the least significant bit (= even and odd), the presence or absence is switched every time, while the last element 2` corresponds to the most significant bit, so it is frozen only in the latter half. It is appearing.
As you can see, the implementation is a double loop with a fixed number of times, and the time complexity is O (2 N </ sup> N). 2 From N </ sup>, 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 the fact that I'm just evaluating with #select.
Try O (2 N </ sup>) for the time being. Implement it recursively and drop it into the process when ʻary` is one less.
each_subset.rb
def each_subset(ary, selected = [], &block)
if ary.empty?
block.call(selected.dup) #Duplicate because it is too dangerous if the array is the same object
return
end
ary = ary.dup #Duplicate without breaking the input array
elem = ary.pop
each_subset(ary, selected, &block) #does not include elem
selected.unshift(elem)
each_subset(ary, selected, &block) #Including elem
selected.shift
# ary << elem #Not required if duplicated
return #Returns nil for the time being
end
if $0 == __FILE__
each_subset([*0..2]) { |subset| p subset }
end
A non-recursive version, and internally records 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
-->
For ʻary = [0, 1, 2, 3, 4] , I want to create, for example, [[0, 1], [2], [3, 4]] `.
From a different point of view, the number of cases is 2 ** (ary.size -1) because it means "insert / do not insert a delimiter between ** elements of the array **". Since it is a mystery what to return when it is an empty array, make it a convenient form for implementation.
This is also implemented recursively. If you group and extract some from ʻary`, you can make another group with the remaining ones.
each_split.rb
def each_split(ary, selected = [], &block)
if ary.empty?
block.call(selected.map(&:dup)) #Duplicate because it is too dangerous if the array is the same object
return
end
# ary == part1 +Operate to keep part2
part1 = []
part2 = ary.dup #Duplicate without breaking the input array
selected << part1
until part2.empty?
part1 << part2.shift #Shift the split position to the right
each_split(part2, selected, &block)
end
selected.pop
# ary.replace(part1) #Not required if duplicated
return #Returns nil for the time being
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]]
Recommended Posts