2

I'm simplifying a larger complex problem with the following...

Given three arrays of integers, what's the most efficient way to return all the possible combinations of each of the elements? Note that each value from each array will always be given in the same position so [A,B,C] would be the same as [C,B,A]. My desired result is an array of arrays with each hash containing a single combination. For example:

Given:

var array1 = [1,2]
var array2 = [a,b]
var array3 = [foo,bar]

The result would be:

[
  [1,a,foo],
  [2,a,foo],
  [1,b,foo],
  [2,b,foo],
  [1,a,bar],
  [2,a,bar],
  [1,b,bar],
  [2,b,bar]
]
Joel Coehoorn
  • 399,467
  • 113
  • 570
  • 794
Kyle Hayes
  • 5,225
  • 8
  • 38
  • 53

5 Answers5

9

In Python, use itertools.product:

itertools.product(array1, array2, array3)

and wrap it in a list if you need a sequence, not just an iterable.

If you want to see how it's done, this is the "equivalent" code given in the itertools docs:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

although that version of the code isn't particularly efficient.

There is also a Python implementation in the PyPy version of itertools.

agf
  • 171,228
  • 44
  • 289
  • 238
4

itertools.product solves this problem directly and it is very fast:

>>> from itertools import product
>>> list(product([1,2], ['a', 'b'], ['foo', 'bar']))
[(1, 'a', 'foo'), (1, 'a', 'bar'), (1, 'b', 'foo'), (1, 'b', 'bar'), (2, 'a', 'foo'), (2, 'a', 'bar'), (2, 'b', 'foo'), (2, 'b', 'bar')]
Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
  • 1
    That's the first part of my answer. – agf Mar 25 '12 at 06:10
  • 3
    FWIW, my answer was constructed independently and it shows a worked-out example using the OP's data. As the author of *itertools* and its documentation, I don't think you would expect me to give any other answer :-) – Raymond Hettinger Mar 25 '12 at 09:03
3

Here's a rather verbose way of doing it in Python:

# define the sets of items
array1 = [1,2]
array2 = ['a', 'b']
array3 = ['foo', 'bar']

# create an empty list to collect combinations
all_combinations = []

# enumerate all combinations by nested iteration
for i in array1:
    for j in array2:
        for k in array3:
            all_combinations.append([i, j, k]) 

# print all combinations
for item in all_combinations:
    print item
Brendan Wood
  • 6,220
  • 3
  • 30
  • 28
  • 1
    This doesn't scale -- you have to write a different version for each different number of iterables. – agf Mar 25 '12 at 03:15
  • 2
    Yup, just demonstrating the principle. Your answer is much better, but also less comprehensible to anyone learning to code. – Brendan Wood Mar 25 '12 at 03:20
  • Calling a standard library function is "less comprehensible"? – Karl Knechtel Mar 25 '12 at 03:55
  • If the goal is to understand how something works, it is my opinion that black boxes don't help. And if you're new to Python or programming in general, looking at the source code (or equivalent source) for `itertools.product` will probably make things worse. – Brendan Wood Mar 25 '12 at 04:03
  • I agree with you in general, but your code is too simple -- it isn't adequate to show how to solve the problem. You _haven't_ demonstrated the principle. Being able to handle any number of iterables is the core of the issue. It just isn't that simple of a problem. – agf Mar 25 '12 at 04:17
  • OP requested all combinations of items in three sets, and that's exactly what my code does. OP did not indicate that he knew how to solve the problem in _any_ way, and this is a simple way to get started. Your solution is a black box, and the equivalent code you pulled from the docs is utterly incomprehensible to anyone not already skilled in Python (which you can't even assume, since OP tagged VB and JavaScript alongside Python). What is the issue with having a simpler, less general, and more readible solution alongside your example of how to do it properly? – Brendan Wood Mar 25 '12 at 04:29
3

Here is a solution in javascript:

function p(o){
    var count=1;
    var step_len=[];
    for(var i=0;i<o.length;i++){
        step_len[i]=count;
        count*=o[i].length;
    }
    for(var i=0;i<count;i++){
        var tmp=[];
        for(var n=0;n<o.length;n++){
            tmp.push(o[n][Math.floor(i/step_len[n])%o[n].length]);
        }
        console.log(tmp);
    }
}

var o=[
    [1,2],
    ['a','b'],
    ['foo','bar']
];

p(o);

/* console output:
[1, "a", "foo"]
[2, "a", "foo"]
[1, "b", "foo"]
[2, "b", "foo"]
[1, "a", "bar"]
[2, "a", "bar"]
[1, "b", "bar"]
[2, "b", "bar"]
*/

it works with any number of arrays.

Demo: http://jsfiddle.net/u9zJQ/

stewe
  • 41,820
  • 13
  • 79
  • 75
  • if instead of recording the values of the parameter in the output, if we record the position of the parameters in original o(n) lists, this will be a sequence of positions. Does anybody know what this sequence is called? – varun Aug 05 '12 at 06:35
1

just made a python equivalant of @stewe's answer. I like this answer better then any answer with itertools as its more generic and can be applied to any language. I needed this in VBA and it worked like a charm.. +1

def p(o):
    count=1
    step_len=[]
    for i, item in enumerate(o):
        step_len.append(count)
        count *= len(o[i])

    for i in range(count):
        tmp=[]
        for n, item in enumerate(o):
            tmp.append(o[n][(i//step_len[n]) % len(o[n])])

        print tmp
    print count
stewe
  • 41,820
  • 13
  • 79
  • 75
varun
  • 569
  • 7
  • 10