Unique combination of values from arrays

Ruby
1

Here’s a problem for which I can’t see an obvious solution, and hope
someone might have some suggestions.

I have several arrays, each with a variety of text values in them. I
need to construct some strings consisting of each unique combination of
the arrays in order. Here’s a very simple example:

first_array = [‘one’,‘two’]
second_array = [‘three’,‘four’]

required output:

one,three
one,four
two,three
two,four

There are more arrays than that and more entries in each array, but
that’s the basic idea. Any advice welcome - thanks!

2

Milo T. wrote:

Here’s a problem for which I can’t see an obvious solution, and hope
someone might have some suggestions.

I have several arrays, each with a variety of text values in them. I
need to construct some strings consisting of each unique combination of
the arrays in order. Here’s a very simple example:

first_array = [‘one’,‘two’]
second_array = [‘three’,‘four’]

required output:

one,three
one,four
two,three
two,four

There are more arrays than that and more entries in each array, but
that’s the basic idea. Any advice welcome - thanks!

ar1 = [ ‘one’, ‘two’ ]
ar2 = [ ‘three’, ‘four’ ]
ar3 = [ ‘five’, ‘six’ ]

output:

one,three,five
one,three,six
one,four,five
one,four,six
two,three,five
two,three,six
two,four,five
two,four,six

Is that right?
Are your arrays organized in an array of arrays? Can they be?

3

Aldric G. wrote:

ar1 = [ ‘one’, ‘two’ ]
ar2 = [ ‘three’, ‘four’ ]
ar3 = [ ‘five’, ‘six’ ]

output:

one,three,five
one,three,six
one,four,five
one,four,six
two,three,five
two,three,six
two,four,five
two,four,six

Is that right?

Indeed it is.

Are your arrays organized in an array of arrays? Can they be?

You’re right - I could easily organise them that way.

The purpose is so that I can find all the unique combinations of
parameters for different fields in SQL queries for some data I have.

4

Milo T. wrote:

The purpose is so that I can find all the unique combinations of
parameters for different fields in SQL queries for some data I have.

Well, I shamelessly stole and adapted the code from there:

def array_permutations index, array
result = []
if index == array.size
result << “”
return result
end
array[index].each do |element|
array_permutations(index + 1, array).each do |x|
result << “#{element}, #{x}”
end
end
return result
end

It’s a bit ugly, but it’ll pretty much do what you want. Let me know if
you can come up with a better variable name than ‘x’ :wink:

irb(main):051:0> one = [‘one’, ‘two’]
=> [“one”, “two”]
irb(main):052:0> two = [‘three’, ‘four’]
=> [“three”, “four”]
irb(main):053:0> three = [‘five’, ‘six’]
=> [“five”, “six”]
irb(main):054:0> a = array_permutations 0, [one, two, three]
=> ["one, three, five, ", "one, three, six, ", "one, four, five, ",
"one, four, six, ", "two, three, five, ",
"two, three, six, ", "two, four, five, ", "two, four, six, "]

5

Aldric G. wrote:

Milo T. wrote:

Here’s a problem for which I can’t see an obvious solution, and hope
someone might have some suggestions.

I have several arrays, each with a variety of text values in them. I
need to construct some strings consisting of each unique combination of
the arrays in order. Here’s a very simple example:

And even cleaner…

http://trevoke.net/blog/2009/12/17/inter-array-permutations-in-ruby/

6

Milo T. wrote:

Here’s a problem for which I can’t see an obvious solution, and hope
someone might have some suggestions.

I have several arrays, each with a variety of text values in them. I
need to construct some strings consisting of each unique combination of
the arrays in order. Here’s a very simple example:

This is a little cleaner:

def array_permutations array, index=0
result = []
if index == array.size
result << “”
return result
end
array[index].each do |element|
array_permutations(array, index + 1).each do |x|
result << “#{element} #{x}”
end
end
result.map! { |string| string.strip }
return result
end

one = [‘one’, two’]
two = [‘three’, ‘four’]
three = [‘five’, ‘six’]
array_permutations [one, two, three]

7

one = [‘one’, ‘two’]
two = [‘three’, ‘four’]
three = [‘five’, ‘six’]
p one.product(two.product(three)).map {|x| x.flatten.join(" ")}

produces

[“one three five”, “one three six”, “one four five”, “one four six”,
“two three five”, “two three six”, “two four five”, “two four six”]

8

Aldric G. wrote:

And even cleaner…

http://trevoke.net/blog/2009/12/17/inter-array-permutations-in-ruby/

Excellent, thanks - any of these should do the trick.

9

Giampiero Z. wrote:

one = [‘one’, ‘two’]
two = [‘three’, ‘four’]
three = [‘five’, ‘six’]
p one.product(two.product(three)).map {|x| x.flatten.join(" ")}

produces

[“one three five”, “one three six”, “one four five”, “one four six”,
“two three five”, “two three six”, “two four five”, “two four six”]

That’s really cool.
So…

def fancy_array_permutation arrays
return [“”] if arrays.empty?
first = arrays.shift
return first.product( fancy_array_permutation(arrays) ).map {|x|
x.flatten.join(" ")}
end

produces

["one three five ", "one three six ", "one four five ", "one four six ",
"two three five ", "two three six ", "two four five ", "two four six "]

Blast. I did find this though:
http://snipplr.com/view/5087/arrayproduct-for-ruby-18/
Unfortunately, this method uses too much memory, storing the whole
cartesian product Array in memory even its elements are needed only one
at a time. One nicer alternative is the Cartesian module:

"The Cartesian module provide methods for the calculation of the

cartesian producted between two enumberable objects. It can also be
easily mixed in into any enumberable class, i.e. any class with
Enumerable module mixed in."

The Cartesian module is available at

http://rubyforge.org/projects/cartesian/

This being said, a quick benchmark indicates that your code indeed runs
exponentially faster than mine… As indicated, probably at the expense
of memory.

10

Aldric G. wrote:

Giampiero Z. wrote:

one = [‘one’, ‘two’]
two = [‘three’, ‘four’]
three = [‘five’, ‘six’]

Sorry for the spam, just wanted to repost the cleaner solutions:

Mine first, of course, because it is ugly:

def array_permutations array, index=0

index is 0 by default : start at the beginning, more elegant.

return array[-1] if index == array.size - 1 # Return last element if
at end.
result = []
array[index].each do |element| # For each array
array_permutations(array, index + 1).each do |x| # Permute permute
permute
result << “#{element}, #{x}”
end
end
return result
end

My adaptation of Giampiero’s solution:

def fancy_array_permutation array
return array[0] if array.size == 1
first = array.shift
return first.product( fancy_array_permutation(array) ).map {|x|
x.flatten.join(" ")}
end