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

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 }

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.