# Build array of possible combinations

**URL:** <https://www.ruby-forum.com/t/build-array-of-possible-combinations/49670>\
**Category:** Ruby\
**Created:** [December 7, 2005, 1:55pm UTC](https://www.ruby-forum.com/t/build-array-of-possible-combinations/49670 "2005-12-07T13:55:21Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![thoepfner](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c37758/32.png) [@thoepfner](https://www.ruby-forum.com/u/thoepfner)\
**Post date:** [December 7, 2005, 1:55pm UTC](https://www.ruby-forum.com/t/build-array-of-possible-combinations/49670/1 "2005-12-07T13:55:21Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![thoepfner](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c37758/32.png) [@thoepfner](https://www.ruby-forum.com/u/thoepfner)\
**Post date:** [December 7, 2005, 9:45pm UTC](https://www.ruby-forum.com/t/build-array-of-possible-combinations/49670/2 "2005-12-07T21:45:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![thoepfner](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c37758/32.png) [@thoepfner](https://www.ruby-forum.com/u/thoepfner)\
**Post date:** [December 7, 2005, 11:53pm UTC](https://www.ruby-forum.com/t/build-array-of-possible-combinations/49670/3 "2005-12-07T23:53:24Z")

</div>

Hi Timo,

On 12/7/05, Timo H. [removed\_email\_address@domain.invalid](mailto: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

---

<div class="post-metadata">

**Author:** ![thoepfner](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c37758/32.png) [@thoepfner](https://www.ruby-forum.com/u/thoepfner)\
**Post date:** [December 9, 2005, 7:39pm UTC](https://www.ruby-forum.com/t/build-array-of-possible-combinations/49670/4 "2005-12-09T19:39:58Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![thoepfner](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/c37758/32.png) [@thoepfner](https://www.ruby-forum.com/u/thoepfner)\
**Post date:** [December 9, 2005, 3:43pm UTC](https://www.ruby-forum.com/t/build-array-of-possible-combinations/49670/5 "2005-12-09T15:43:57Z")

</div>

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](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.codepedia.com/1/Art_Expressions_p1)

# [http://www.faqts.com/knowledge\_base/view.phtml/aid/26081/fid/585](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.: