Last active
August 29, 2015 14:03
-
-
Save til/28340bb6c8a4c9a18288 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
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 |
Hi @til, yes, probably there's a related search algorithm. I just took the example output and tried to encode the regularities.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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 ...