combination_problem.rb

# 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]]

@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

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.