One-liner Algorithm to Combine Arrays into Arrays of All Possible Value Combinations?

Question

Not quite sure I have the question fully formed, but what I'm trying to do is basically this:

# where the indices correspond to attributes fore example:
# [type, status]
x = %w(a b)
y = %w(c d)
combine(x, y) #=> [["a", "b"], ["a", "d"], ["c", "a"], ["c", "b"]]

The order of the array is always the same, so the reverse of each, such as [b, a], are not included in the result.

What is this called and what's an efficient way to implement this?

I see Array#permutation, but that's not quite it...

This would hopefully work for any number of arrays and values: combine(*arrays)

Thanks!

Update

Here's a better example of what I'm looking for:

This (x | y).combination(x.length).to_a produces the following:

x = ["front_door", "open"]
y = ["back_door", "closed"]
(x | y).combination(x.length).to_a
=> [["front_door", "open"], ["front_door", "back_door"], ["front_door", "closed"], ["open", "back_door"], ["open", "closed"], ["back_door", "closed"]]

The actual result I'm looking for is this:

=> [["front_door", "open"], ["front_door", "closed"], ["back_door", "open"], ["back_door", "closed"]]

Or if it were a longer array:

x = ["house", "front_door", "open"]
y = ["building", "back_door", "closed"]
compute(x, y)
=> ["house", "front_door", "open"], ["house", "back_door", "open"], ["house", "front_door", "closed"], ["house", "back_door", "closed"], ["building", "front_door", "open"], ["building", "back_door", "open"], ["building", "front_door", "closed"], ["building", "back_door", "closed"]

Any ideas?

I guess in the first example ["c", "a"] should look ["c", "d"] — tokland
– tokland, Commented Jan 23, 2011 at 0:25

adamax · Accepted Answer · 2011-01-22 22:46:49Z

5


x.zip(y).reduce(:product).map(&:flatten)

And for several arrays:


x.zip(y,z,w).reduce(:product).map(&:flatten)

answered Jan 22, 2011 at 22:46

adamax

3,8952 gold badges21 silver badges21 bronze badges

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

2 Comments

Lance Pollard Over a year ago

what if the arrays were instead organized like this: ["house", "building"], ["front_door", "back_door"], ["open", "closed"], how would you get the same result?

adamax Over a year ago

@vlatropos [["house", "building"], ["front_door", "back_door"], ["open", "closed"]].reduce(:product).map(&:flatten). (The zip in the answer transforms the original representation into this one.)

JRL · Accepted Answer · 2011-01-22 22:23:59Z

3

(x | y ).combination(x.length).to_a

edited Jan 22, 2011 at 22:23

answered Jan 22, 2011 at 22:14

JRL

78.2k18 gold badges103 silver badges146 bronze badges

1 Comment

Lance Pollard Over a year ago

this is really cool, but I guess my question wasn't quite right... updated the question.

tokland · Accepted Answer · 2011-01-23 10:26:28Z

0

def combine(*arrays)
  head, *tail = arrays.transpose
  head.product(*tail)
end

combine(x, y)
combine(x, y, z, ...)

Side note digression: this is one of the scenarios in which you get the point that functional languages make about functions being the important stuff. The fact that you have to call an object's method in OOP forces you -in this case- to contrivedly get their head/tail. When you have product as a function, for example in Python, you don't have this kind of problems:

itertools.product(*zip(*arrays))

edited Jan 23, 2011 at 10:26

answered Jan 22, 2011 at 23:37

tokland

68.2k13 gold badges151 silver badges174 bronze badges

3 Comments

Mark Thomas Over a year ago

Doesn't x.zip(y).reduce(:product) do the same thing as your Python example?

tokland Over a year ago

@Mark Thomas. The zip+reduce generates an extra level of nesting (that's why adamax's solution has to flatten afterwards). Moreover, it's very inefficient, Array#product supports arbitrary number of arguments, why don't use it instead of reducing/injecting?

tokland Over a year ago

But my point was that conceptually these kind of operations do not fit nicely into the OOP paradigm. You see this also when transposing; in Python you simply write "zip(*list_of_lists)" but in Ruby they had to create Array#transpose (otherwise you'd have to manually get its head/tail, like I did above: head, *tail = array_of_arrays; head.zip(*tail), and be careful that head is not nil!). That's because conceptually the zip operation takes a group of arrays, not an an array zipped with-the-rest-of-arrays. Hey, that's not a rant, I love Ruby!, just a digression, like I said :-)

Collectives™ on Stack Overflow

One-liner Algorithm to Combine Arrays into Arrays of All Possible Value Combinations?

3 Answers 3

2 Comments

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related