All possible combinations from a list (Python) or array (Ruby)

Archive - Originally posted on "The Horse's Mouth" - 2011-04-23 04:29:51 - Graham Ellis

If there are eight of us at a meeting, how many possibilities are there for a pair of people to stongly disagree? The answer turns out to be 28. And if you look at subgoups of 3, looking for everyone to have the same opinion within the subgroup, the answer is many more.

If there are eight stations on a railway line, there aren't 28 different single journey opportunities - there are 56, because of two directions being involved - a to b and b to a. And if you look at where people live and work, you have 64 possibilities as the most environmentally friendly thing to do is to live and work in the same town and not travel at all, adding eight to the 56 journey opportunities.

Here is a (Python) example of a pair of loops to generate the two-way options for our meeting group:

def tessa(source):

  result = []

  for p1 in range(len(source)):

    for p2 in range(p1+1,len(source)):

      result.append([source[p1],source[p2]])

  return result

With the a full result and full program shown [here]. It starts to get more complex when you write code to go on to 3-way and 4-way links ... that would potentially be good use for a recursive (self-calling) function as you can't simply go on writing loops within loops.

Ruby offers you a combination method on an array, where you can pass in the number of elements wanted in a combination. So:

  for flow in stops.combination(2)

    p flow

    end

will print out all 28 combinations of two elements from an array (of 8 elements in our example). To find the reverse journeys, I need to add

p flow

and I can look at all 3-way combinations (from x to y via z) grous instead by looking at:

for flow in stops.combination(3)

although I have to bear in mind that if I'm looking at journeys, there are six possible orders for three values (xyz xzy yxz yzx zxy and zyx) and I must remember the most common of all trips - the xyx and yxy type where you commute / travel for a day out, and in the evening go back to where you started from.

Full ruby source code in the example [here].

Main Content

All possible combinations from a list (Python) or array (Ruby)