Enumerate subsets of arrays given in Ruby (+ α)

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.

Subset

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.

Use ʻArray # combination`

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]

Use binary notation

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

-->

Split

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

Enumerate subsets of arrays given in Ruby (+ α)
[Ruby] The role of subscripts in learning elements in arrays
Summary of hashes and symbols in Ruby
[Ruby] Classification and usage of loops in Ruby
[Ruby] Behavior of evaluation of conditional expression in while
Recommendation of Service class in Ruby on Rails
[Understanding] Differences between hashes and arrays in Ruby
Method name of method chain in Java Builder + α
Basics of Ruby
About Ruby arrays
Heavy in Ruby! ??
Get the URL of the HTTP redirect destination in Ruby
Handling of date and time in Ruby. Use Date and Time properly.