Unique combination of values from arrays

ruby-talk
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!

···

--
Posted via http://www.ruby-forum.com/.

2

Milo Thurston 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?

···

--
Posted via http://www.ruby-forum.com/\.

3

Milo Thurston 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]

···

--
Posted via http://www.ruby-forum.com/\.

4

Milo Thurston 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!

one = [1,2]
two = [3,4]
three = [5,6,7]
a = [one, two, three]

def combi ary_of_ary
  ary_of_ary.inject([]){|old,lst|
    lst.inject(){|new,e| new + old.map{|c| c + [ e ] }}}
end

puts combi( a ).map{|x| x.join ','}.sort

=== output ===
1,3,5
1,3,6
1,3,7
1,4,5
1,4,6
1,4,7
2,3,5
2,3,6
2,3,7
2,4,5
2,4,6
2,4,7

···

--

5

Aldric Giacomoni 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.

···

--
Posted via http://www.ruby-forum.com/\.

6

Aldric Giacomoni wrote:

Milo Thurston 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/

···

--
Posted via http://www.ruby-forum.com/\.

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

···

--
Posted via http://www.ruby-forum.com/.

8

Milo Thurston 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, "]

···

--
Posted via http://www.ruby-forum.com/\.

9

Aldric Giacomoni 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.

···

--
Posted via http://www.ruby-forum.com/\.

10

Giampiero Zanchi 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.

···

--
Posted via http://www.ruby-forum.com/\.

11

Aldric Giacomoni wrote:

Giampiero Zanchi 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

···

--
Posted via http://www.ruby-forum.com/\.