Skip to content

Instantly share code, notes, and snippets.

@til

til/combination_problem.rb

Last active August 29, 2015 14:03
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save til/28340bb6c8a4c9a18288 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save til/28340bb6c8a4c9a18288 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
combination_problem.rb
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
@kaoskorobase
Copy link

kaoskorobase commented Jul 11, 2014

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.

elements = [:a, :b, :c, :d]

def traverse_(xs, pred, is)
  ys = []
  for i in is
    ys << xs[i]
  end
  if pred.call(ys)
    ys = []
  else
    ys = [ys]
  end
  is_ = is.clone
  if ys.empty? || is.last == (xs.size - 1)
    is_.pop
    if is_.empty? then
      return ys
    end
    is_[is_.size-1] += 1
  else
    is_ << is_.last + 1
  end
  ys + traverse_(xs, pred, is_)
end

def traverse(xs, pred)
  xs.empty? ? [] : traverse_(xs, pred, [0])
end

puts "Everything"
traverse(elements, lambda {|x| false }).each { |x| puts x.inspect }
puts "Pruning [:a,:b,:c]"
traverse(elements, lambda {|x| x == [:a,:b,:c] }).each { |x| puts x.inspect }
puts "Pruning [:d]"
traverse(elements, lambda {|x| x == [:d] }).each { |x| puts x.inspect }

@kaoskorobase
Copy link

kaoskorobase commented Jul 11, 2014

What's it for btw?

@til
Copy link
Author

til commented Jul 11, 2014

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 ...

@kaoskorobase
Copy link

kaoskorobase commented Jul 11, 2014

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