-
-
Save til/28340bb6c8a4c9a18288 to your computer and use it in GitHub Desktop.
require 'rspec' | |
require 'set' | |
class Traverser | |
attr_reader :elements, :satisfied | |
def initialize(elements, satisfied:) | |
@elements = elements | |
@satisfied = satisfied | |
end | |
# [: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) | |
combination.map {|e| elements[e] } | |
end | |
# compute the next combination | |
def next_combination(combo) | |
# A combination containing only the last element is the last combination | |
raise StopIteration if combo == last_element_combo | |
# 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 next_branch(combo) | |
highest = combo.max | |
combo = combo - [highest] | |
combo + [highest + 1] | |
end | |
def last_element | |
elements.length - 1 | |
end | |
def last_element_combo | |
@last_element_combo ||= Set.new([last_element]) | |
end | |
def include_last_element?(combo) | |
combo.max == last_element | |
end | |
def all_elements?(combo) | |
combo.length == elements.length | |
end | |
def traverse(&block) | |
return to_enum(__method__) unless block_given? | |
combo = combination_to_index_set(elements.take(1), elements) | |
loop do | |
combination = index_set_to_combination(combo) | |
yield combination | |
sat = satisfied.call(combination) | |
break if !sat && all_elements?(combo) | |
if sat && !include_last_element?(combo) | |
combo = next_branch(combo) | |
else | |
combo = next_combination(combo) | |
end | |
end | |
rescue StopIteration | |
end | |
end | |
describe Traverser do | |
subject { ->(b) { traverser.traverse(&b) } } | |
let(:traverser) { described_class.new(elements, satisfied: satisfied) } | |
let(:elements) { [:a, :b, :c, :d] } | |
let(:satisfied) { -> (c) { false } } | |
let(:tree) do | |
[ | |
[: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], | |
] | |
end | |
context 'when full length satisfies but nothing else' do | |
let(:satisfied) { -> (c) { c == [:a, :b, :c, :d] } } | |
it 'tests branches below, depth first' do | |
expect(subject).to yield_successive_args(*tree) | |
end | |
end | |
context 'when first element satisfies' do | |
let(:satisfied) { -> (c) { c == [:a] } } | |
it 'skips branch below' do | |
expect(subject).to yield_successive_args( | |
[:a], | |
[:b], | |
[:b, :c], | |
[:b, :c, :d], | |
[:b, :d], | |
[:c], | |
[:c, :d], | |
[:d], | |
) | |
end | |
end | |
context 'when first elements satisfy' do | |
let(:satisfied) { -> (c) { c == [:a, :b] } } | |
it 'skips branch below satisfying combo' do | |
expect(subject).to yield_successive_args( | |
[:a], | |
[:a, :b], | |
[:a, :c], | |
[:a, :c, :d], | |
[:a, :d], | |
[:b], | |
[:b, :c], | |
[:b, :c, :d], | |
[:b, :d], | |
[:c], | |
[:c, :d], | |
[:d], | |
) | |
end | |
end | |
context 'when nothing satisfies' do | |
let(:satisfied) { -> (_) { false } } | |
it 'stops after full length' do | |
expect(subject).to yield_successive_args( | |
[:a], | |
[:a, :b], | |
[:a, :b, :c], | |
[:a, :b, :c, :d], | |
) | |
end | |
end | |
end |
What's it for btw?
Hi @kaoskorobase, sorry I didn't see your comment earlier, I thought that I'd get a github notification about it because I starred the gist.
Your recursive solution looks great! And the pruning works exactly as expected. I need some more time to fully dig through how the solution works though ...
It is for an optimization problem in a project that I am currently working on, where the behavior of the elements for the predicate is cumulative - if [:a, :b] is true then all [:a, :b] + * are true too and can therefore be skipped. Not sure how to exactly describe this, it sounds to me like something that one would learn in CS ...
Hi @til, yes, probably there's a related search algorithm. I just took the example output and tried to encode the regularities.
Hey, I'm not a Ruby expert, so the code is quite ugly, but I think the below does what you want. You probably want to transform
traverse
to iterator style instead of constructing the result list explicitly.