Build array of possible combinations


#1

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


#2

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.


#3

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


#4

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


#5

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/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 V.: