From: Timo Hoepfner <th-dev@...>
Date: 2005-12-09T23:43:09+09:00
Subject: Re: Build array of possible combinations

Hi Wayne & Harpo,

thanks a lot for your suggestions. This is really an interesting  
solution. It took me some time to get the conversion from infix  
going. I ended up converting infix->postfix->binary tree. Code of my  
findings is below. There's certainly a lot to be improved there. Any  
obvious mistakes of a ruby-newbie in there?

While working on the code, I came across some strange behaviour of  
the Set class of the ruby standard library:

class TestSet < Test::Unit::TestCase
   def test_set
     array=[["a", "b"], ["a", "c"], ["d"]]
     array_of_sets=array.map{|an_array| an_array.to_set}
     set_of_sets=array_of_sets.to_set
     contained_set=["a","b"].to_set
     # OK
     assert_equal(true, array_of_sets.include?(contained_set))
     # fails
     assert_equal(true, set_of_sets.include?(contained_set))
   end
end

The second assertion fails. Is this intended behaviour?

Thanks again fpr your great suggestions!

Timo

# andx and orx implementation by Wayne Vucenic:
#   http://article.gmane.org/gmane.comp.lang.ruby.general/126925
#
# Helpful docs for infix/prefix/postfix/binary tree conversions
# http://www.codepedia.com/1/Art_Expressions_p1
# http://www.faqts.com/knowledge_base/view.phtml/aid/26081/fid/585
#
# Known Limitations:
# infix_to_*fix: code doesn't handle operator priorities
# postfix_to_tree: code doesn't handle unary operators
# no error handling

require 'set'

class ArrayOfCombinations
   OPERATORS=["and","or"]
   SPLIT_REGEX=/(\(|\)|and|or)/

   attr_reader :combinations

   def initialize(infix_str)
     @combinations = ArrayOfCombinations.expand infix_str
     @all_sets = @combinations.map{|an_array| an_array.to_set}
   end

   def remaining_choices_for(choices)
     choices = choices.to_set if choices.is_a?(Array)
     remaining_sets = @all_sets.find_all{|a_set|  
choices.proper_subset?(a_set)}
     remaining_sets.to_set.flatten-choices
   end

   def complete_for?(choices)
     choices = choices.to_set if choices.is_a?(Array)
     @all_sets.include? choices
   end

   def self.andx(a,b)
     ret = []
     a.each do |some_a|
       b.each do |some_b|
         ret << some_a + some_b
      end
     end
     ret
   end

   def self.orx(a,b)
     a.collect {|some_a| some_a } + b.collect {|some_b| some_b}
   end

   private

   def self.split_input(input)
     elements=input.gsub(" ","").split(SPLIT_REGEX)
     elements.delete ""
     elements
   end

   # infix_to_prefix currently not used
   def self.infix_to_prefix(infix_str)
     stack, output = [], []
     elements=split_input(infix_str)
     elements.reverse!
     elements.each do |element|
       if element==")"
         stack.push element
       elsif OPERATORS.include?(element)
         stack.push element
       elsif element=="("
         while (operator=stack.pop) != ")"
           output << operator
         end
       else
         output << element
       end
     end
     while not stack.empty?
       output << stack.pop
     end
     output.reverse!
   end

   def self.infix_to_postfix(infix_str)
     stack, output = [], []
     elements=split_input(infix_str)
     elements.each do |element|
       if element=="("
         stack.push element
       elsif OPERATORS.include?(element)
         stack.push element
       elsif element==")"
         while (operator=stack.pop) != "("
           output << operator
         end
       else
         output << element
       end
     end
     while not stack.empty?
       output << stack.pop
     end
     output
   end

   class BinTreeNode
     attr_accessor :value, :left, :right

     def initialize(value=nil, left=nil, right=nil)
       @value, @left, @right = value, left, right
     end

     def inspect
       return value+"x("+left.inspect+","+right.inspect+")" if left ! 
= nil and right != nil
       return "[['"+value+"']]"
     end
   end

   def self.postfix_to_tree(postfix_array)
     stack = []
     postfix_array.each do |element|
       if OPERATORS.include?(element)
         right, left = stack.pop, stack.pop
         stack.push BinTreeNode.new(element,left,right)
       else
         stack.push BinTreeNode.new(element,nil,nil)
       end
     end
     stack.first
   end

   def self.expand(infix_str)
     postfix=infix_to_postfix(infix_str)
     tree=postfix_to_tree(postfix)
     eval tree.inspect
   end

end

require 'test/unit'

class TestArrayOfCombinations < Test::Unit::TestCase
   def test_andx_orx
     assert_equal([[:a,:b]], ArrayOfCombinations.andx([[:a]], [[:b]]))
     assert_equal([[:a,:b,:c]], ArrayOfCombinations.andx([[:a]],  
[[:b, :c]]))
     assert_equal([[:a,:b], [:a,:c]], ArrayOfCombinations.andx 
([[:a]], [[:b], [:c]]))

     assert_equal([[:a], [:b]], ArrayOfCombinations.orx([[:a]], [[:b]]))
     assert_equal([[:a],[:b,:c]], ArrayOfCombinations.orx([[:a]],  
[[:b, :c]]))

     # Try the test case from the RubyTalk posting
     assert_equal([["a", "b"], ["a", "c"], ["d"]],
                  ArrayOfCombinations.orx(ArrayOfCombinations.andx 
([['a']],
                           ArrayOfCombinations.orx([['b']], [['c']])),
                      [['d']]))
   end

   def test_expand
     output = ArrayOfCombinations.new("(a and (b or c) ) or  
d").combinations
     assert_equal([["a", "b"], ["a", "c"], ["d"]],output)
   end

   def test_complete_for
     aoc = ArrayOfCombinations.new("(a and (b or c) ) or d")
     assert_equal(false, aoc.complete_for?([]))
     assert_equal(false, aoc.complete_for?(["a"]))
     assert_equal(true, aoc.complete_for?(["a","b"]))
     assert_equal(true, aoc.complete_for?(["d"]))
   end

   def test_remaining_choices
     input = "(a and (b or c) ) or d"
     aoc = ArrayOfCombinations.new(input)
     assert_equal(["a","b","c","d"].to_set, aoc.remaining_choices_for 
([]))
     assert_equal(["d","b","c","a"].to_set, aoc.remaining_choices_for 
([]))
     assert_equal(["b","c"].to_set, aoc.remaining_choices_for(["a"]))
     assert_equal([].to_set, aoc.remaining_choices_for(["d"]))
   end
end


Am 07.12.2005 um 23:50 schrieb Wayne Vucenic:

> Hi Timo,
>
> On 12/7/05, Timo Hoepfner <th-dev@onlinehome.de> wrote:
>> I'm looking for an easy way to convert a string representing a
>> boolean expression like
>>
>> "(a and (b or c) ) or d"
>>
>> to an Array of Arrays (representing sets) representing all possible
>> valid combinations like:
>>
>> [["a","b"],["a","c"],["d"]]
>
> First, we write a method that converts the input string from infix to
> prefix notation and that also puts [[ ]] around all the arguments (to
> simplify later processing).  I didn't actually do this step, but it  
> shouldn't be
> too hard.  So this method will convert "(a and (b or c) ) or d" into
>
> orx(andx([['a']],
>          orx([['b']], [['c']])),
>     [['d']]))
>
> I find it's best to use Test Driven Development to solve problems like
> defining orx and andx.  The resulting solution below converts the  
> above
> expression into [["a", "b"], ["a", "c"], ["d"]]
>
> Thanks for the interesting problem!
>
> Wayne
>
> ---
> Wayne Vucenic
> No Bugs Software
> "Ruby and C++ Contract Programming in Silicon Valley"
>
>
>
> def andx(a,b)
>   ret = []
>   a.each do |some_a|
>     b.each do |some_b|
>       ret << some_a + some_b
>    end
>   end
>   ret
> end
>
> def orx(a,b)
>   a.collect {|some_a| some_a } + b.collect {|some_b| some_b}
> end
>
>
> require 'test/unit'
>
> class TestArrayOfCombinations < Test::Unit::TestCase
>   def test_one
>     assert_equal([[:a,:b]], andx([[:a]], [[:b]]))
>     assert_equal([[:a,:b,:c]], andx([[:a]], [[:b, :c]]))
>     assert_equal([[:a,:b], [:a,:c]], andx([[:a]], [[:b], [:c]]))
>
>     assert_equal([[:a], [:b]], orx([[:a]], [[:b]]))
>     assert_equal([[:a],[:b,:c]], orx([[:a]], [[:b, :c]]))
>
>     # Try the test case from the RubyTalk posting
>     assert_equal([["a", "b"], ["a", "c"], ["d"]],
>                  orx(andx([['a']],
>                           orx([['b']], [['c']])),
>                      [['d']]))
>   end
> end
>