-
-
Save plexus/3b703fa11de3df9e068b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Given an ordered list of elements, how can the possible combinations | |
# of those elements (of all lengths, order does not matter, no | |
# repetition) be traversed in the sequence shown below? Either | |
# iterative or recursive, but it needs to be in such a way that the | |
# computation of certain branches can be skipped based on a condition | |
# computed from the combination. E.g. when it reaches [:a, :b], it | |
# should be possible to say: if check?([:a, :b]) then skip everything | |
# until [:a, :b, :d] and continue with [:a, :c]. | |
# | |
# In the concrete problem behind this, the list of elements is a lot | |
# longer (up to hundreds), making a brute force loop over all | |
# combinations impossible. However the combinations are cumulative - | |
# once a custom check method returns true for a certain combination, | |
# the combinations which only add elements can be skipped. And they | |
# can be sorted by likeliness to satisfy the check, so I am hoping | |
# that this approach can minimize the number of combinations needed to | |
# traverse to find an optimal combination. | |
elements = [:a, :b, :c, :d] | |
require 'set' | |
# [:a, :d] => Set{0,3} | |
def combination_to_index_set(combination, elements) | |
Set.new(combination.map {|e| elements.index(e) }) | |
end | |
# Set{0,3} => [:a, :d] | |
def index_set_to_combination(combination, elements) | |
combination.map {|e| elements[e] } | |
end | |
# compute the next combination | |
def next_combination(combo, elements) | |
last_element = elements.length - 1 | |
# A combination containing only the last element is the last combination | |
raise StopIteration if combo == Set.new([last_element]) | |
# If there is an element with a higher index that's missing we simply add that element | |
return combo + [combo.max + 1] if combo.max < last_element | |
# We have a combo that includes the final element, we need to backtrack | |
highest = combo.max | |
combo = combo - [highest] | |
second_highest = combo.max | |
combo - [second_highest] + [second_highest + 1] | |
end | |
def traverse(elements, &block) | |
return to_enum(__method__) unless block_given? | |
combo = combination_to_index_set(elements.take(1), elements) | |
loop do | |
cmd, skip_to = yield index_set_to_combination(combo, elements) | |
combo = combination_to_index_set(skip_to, elements) if cmd == :skip | |
combo = next_combination(combo, elements) | |
end | |
rescue StopIteration | |
end | |
# This code produces the right sequence, but it has to compute | |
# everything beforehand, so it does not allow to skip from within: | |
# | |
# 1.upto(elements.length).map { |i| elements.combination(i).to_a }.flatten(1).sort.each { |c| yield c } | |
sequence = [] | |
traverse(elements) do |c| | |
sequence << c | |
[:skip, [:a, :d]] if c == [:a, :b, :c, :d] | |
end | |
sequence == [ | |
[:a], | |
[:a, :b], | |
[:a, :b, :c], | |
[:a, :b, :c, :d], | |
[:a, :b, :d], | |
[:a, :c], | |
[:a, :c, :d], | |
[:a, :d], | |
[:b], | |
[:b, :c], | |
[:b, :c, :d], | |
[:b, :d], | |
[:c], | |
[:c, :d], | |
[:d], | |
] || (require 'pp'; pp(sequence); fail) | |
# ~> -:90:in `<main>': unhandled exception | |
# >> [[:a], | |
# >> [:a, :b], | |
# >> [:a, :b, :c], | |
# >> [:a, :b, :c, :d], | |
# >> [:b], | |
# >> [:b, :c], | |
# >> [:b, :c, :d], | |
# >> [:b, :d], | |
# >> [:c], | |
# >> [:c, :d], | |
# >> [:d]] |
pushed a new version that includes skipping part of the list
Very nice. Not sure if the block can know where to skip_to
in my situation, will have to write a few specs for it first to try it out.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@til could be made more clear or more efficient but the basic concept should work. Since you only need to know a ginven combination plus the total collection to get the next combination, it's easy to skip parts