Ruby: How to create an array by combining and interleaving two other arrays

Question

Probably, to make a more general question is how to do list comprehension in Ruby.

Let's say given a number N (say N=5) I want to get an array like this:

[[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Using imperative way I can do:

  arr = []
  N = 5
  (0..N-1).each do |i|
    (i+1..N-1).each do |j|
      arr << [i, j]
    end
  end
  puts arr

Using functional way:

(0..N-1).collect{|el1| (el1+1..N-1).collect{|el2| [el1, el2]}}.flatten.each_slice(2).to_a

I don't like that the second example relies on the fact that the array is sorted in the right order. Is there a cleaner way to get the array in a functional way (without the extra flatten and slice)?

Arup Rakshit · Accepted Answer · 2014-01-29 17:51:16Z

2

I would do as below :

n = 5
a = n.times.flat_map do |i|
  [i].product (i+1..n-1).to_a
end
a # => [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

answered Jan 29, 2014 at 17:51

Arup Rakshit

119k30 gold badges270 silver badges328 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Andrei Over a year ago

Thanks, Arup! flat_map is the key here: we can also do it like: (0..N-1).flat_map{|el1| (el1+1..N-1).map{|el2| [el1, el2]}}

Andrei Over a year ago

Also the product function is very powerful when it comes to combining arrays. I used it before to get all permutations of two numbers each coming from an array. Very beautiful application here, Arup, thank you.

Cary Swoveland · Accepted Answer · 2014-02-03 04:55:45Z

1

You could do this:

Array(0...N).combination(2).to_a

which looks nice, but has the disadvantage that it generates N!/(4*(N-2)!) combinations it doesn't use.

Edit: I originally had select { |x,y| x < y } in place of to_a in the above. @Stefan pointed out that select is supurfluous. Maybe I had permutation(2) on the brain.

Here's another way, a variant of @Arup's answer:

a = Array(0...N)
a.size.times.reduce([]) { |b,_| b + [a.shift].product(a) }

edited Feb 3, 2014 at 4:55

answered Jan 29, 2014 at 18:18

Cary Swoveland

111k6 gold badges69 silver badges105 bronze badges

6 Comments

Stefan Over a year ago

Doesn't (0...5).to_a.combination(2).to_a return the same array?

Arup Rakshit Over a year ago

@Stefan make it as an answer.. Good one!

Stefan Over a year ago

To be more precise: isn't the .select { |x,y| x < y } part superfluous?

Andrei Over a year ago

Thanks, Cary. Actually the combination without select works too: Array(0...N).combination(2).to_a

Arup Rakshit Over a year ago

@CarySwoveland Array(0...N).combination(2).to_a is enough and better!

|

Gary S. Weaver · Accepted Answer · 2014-01-29 19:40:08Z

Most efficient way to do it is Stefan's, which was a comment to Cary's answer (modified to use n variable in Arup's comment to this answer), which was a modification from Cary's answer, so +1 to all those guys:

2.1.0p0 :001 > n = 5
 => 5 
2.1.0p0 :002 > a = (0...n).to_a.combination(2).to_a
 => [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Some benchmarks:

2.1.0p0 :001 > require 'benchmark'
 => true 
2.1.0p0 :002 > n = 5
 => 5 
2.1.0p0 :003 > puts Benchmark.measure { 1000000.times { a = n.times.flat_map {|i| [i].product (i+1..n-1).to_a} } }
  8.050000   0.010000   8.060000 (  8.051535)
 => nil 
2.1.0p0 :004 > puts Benchmark.measure { 1000000.times { a = n.times.flat_map {|x| (x+1..n-1).map{|y| [x,y]}} } }
  6.250000   0.000000   6.250000 (  6.249600)
 => nil
2.1.0p0 :005 > puts Benchmark.measure { 1000000.times { a = Array(0...n).combination(2).select { |x,y| x < y } } }
  5.110000   0.010000   5.120000 (  5.120506)
 => nil 
2.1.0p0 :006 > puts Benchmark.measure { 1000000.times { a = n.times.to_a.combination(2).to_a } }
  4.050000   0.000000   4.050000 (  4.045895)
 => nil 
2.1.0p0 :007 > puts Benchmark.measure { 1000000.times { a = Array(0...n).combination(2).to_a } }
  3.920000   0.000000   3.920000 (  3.928282)
 => nil 
2.1.0p0 :008 > puts Benchmark.measure { 1000000.times { a = (0...n).to_a.combination(2).to_a } }
  3.520000   0.000000   3.520000 (  3.522056)
 => nil

Arup - what you just said is faster as well- just benchmarked it and changed the answer.

Collectives™ on Stack Overflow

Ruby: How to create an array by combining and interleaving two other arrays

3 Answers 3

2 Comments

6 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

6 Comments

1 Comment

Related