Forum: Ruby Build array of possible combinations

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Timo H. (Guest)
on 2005-12-07 14:55
(Received via mailing list)
Hi,

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

Background: I want to build a tree structure, where constraints like
the one above are attached to the nodes. They describe, which
combinations of children are allowed and what valid combinations are
left once one or more children are already selected.
I'm already doing something like that in Java, but supply the list of
possible combinations by hand, which quickly gets annoying... The
rest is done via set operations. The actual business logic is similar
to (pseude code which looks like Ruby from a Ruby-Newbie's POV...):

set=MySet.new [["a","b"],["a","c"],["d"]]

set.remaining_choices_for [] 		--> ["a","b","c","d"]
set.remaining_choices_for ["a"] 	--> ["b","c"]
set.remaining_choices_for ["d"] 	--> []

set.complete_for? ["a"]		--> false
set.complete_for? ["a","b"]	--> true
set.complete_for? ["d"]		--> true

If you can think of a better approach, please tell...


Thanks for your help,

Timo
trashcan (Guest)
on 2005-12-07 22:45
(Received via mailing list)
Timo H. wrote:

> Hi,
>
> I'm looking for an easy way to convert a string representing a
> boolean expression like
>
> "(a and (b or c) or d"

Unpaired parentheses ! (I was a compiler in a previous life, I just
can't help ;))

>
> to an Array of Arrays (representing sets) representing all possible
> valid combinations like:
>
> [["a","b"],["a","c"],["d"]]

The question is interesting, my answer is probably a bad hack.
Say you use a regular expression to transform the string in
"exp([a.xand([b,c]),d])
Maybe it is possible. I think it is.
It seems to be a well formed Ruby expression and can be parsed by Ruby
using eval, you just have to write the xand mathod ('and' is likely to
be a reserved word in a language) end the exp method, maybe the same as
xand.
This methods can build the array you need.

Well, It is just a direction.
I thank you for this problem.
nightphotos (Guest)
on 2005-12-08 00:53
(Received via mailing list)
Hi Timo,

On 12/7/05, Timo H. <removed_email_address@domain.invalid> 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 V.
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
Timo H. (Guest)
on 2005-12-09 16:43
(Received via mailing list)
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 V.:
#   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...
#
# 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 V.:
malte__ (Guest)
on 2005-12-09 20:39
(Received via mailing list)
Timo H.:
>      assert_equal(true, set_of_sets.include?(contained_set))

Interesting:

irb> [ 'a', 'b' ].to_set.eql? [ 'a', 'b' ].to_set
     => false
irb> [ 'a', 'b' ].to_set == [ 'a', 'b' ].to_set
     => true

So Set#== and Set#eql? behave differently.

Malte
This topic is locked and can not be replied to.