unique combinations

June 18, 2010 9:27 AM

I have a list of 6 items. I need to make a list of unique combinations where 3 items are taken from the list in any order and the 4th item is also taken from the same list but cannot be one of the 3 items already selected

I hope I'm explaining this ok...

The problem I'm trying to solve is this:

I have 7 slots to fill and a list of 6 items.

The first 3 slots need to be filled with 3 unique items but their order is unimportant (so for the purposes of this A,B,C = B,A,C = C,B,A etc). The remaining 4 slots will be filled with a 4th item and that item cannot be one of the previous 3.

I need to create a list (not just how many) of all the unique combinations of 6 items that meet this criteria. Obviously a computer is going to do the hard work, I just need to tell it how ;)

posted by missmagenta to Education (13 answers total)

If I'm reading this correctly, you're just looking for the number of sets of 4 that you can make when drawing from 6 items. The phrase you're looking for is "combinations" and the answer is 15.
posted by chrisamiller at 9:32 AM on June 18, 2010

This online calculator will list them for you
posted by chrisamiller at 9:34 AM on June 18, 2010

Best answer: Here's what I've got. The example input list is named l. I take the combinations from this list of length 3 (i) and append an item from the list not present in that specific combination (j). This should work in python 2.6 or greater, need to use print() with parenthesis in python 3.0 or above.


>>> from itertools import permutations

>>> l = ['a', 'b', 'c', 'd', 'e', 'f']

>>> print [ list(i) + [j] for j in l for i in combinations(l, 3) if j not in i ]
[['b', 'c', 'd', 'a'], ['b', 'c', 'e', 'a'], ['b', 'c', 'f', 'a'], ['b', 'd', 'e', 'a'], ['b', 'd', 'f', 'a'], ['b', 'e', 'f', 'a'], ['c', 'd', 'e', 'a'], ['c', 'd', 'f', 'a'], ['c', 'e', 'f', 'a'], ['d', 'e', 'f', 'a'], ['a', 'c', 'd', 'b'], ['a', 'c', 'e', 'b'], ['a', 'c', 'f', 'b'], ['a', 'd', 'e', 'b'], ['a', 'd', 'f', 'b'], ['a', 'e', 'f', 'b'], ['c', 'd', 'e', 'b'], ['c', 'd', 'f', 'b'], ['c', 'e', 'f', 'b'], ['d', 'e', 'f', 'b'], ['a', 'b', 'd', 'c'], ['a', 'b', 'e', 'c'], ['a', 'b', 'f', 'c'], ['a', 'd', 'e', 'c'], ['a', 'd', 'f', 'c'], ['a', 'e', 'f', 'c'], ['b', 'd', 'e', 'c'], ['b', 'd', 'f', 'c'], ['b', 'e', 'f', 'c'], ['d', 'e', 'f', 'c'], ['a', 'b', 'c', 'd'], ['a', 'b', 'e', 'd'], ['a', 'b', 'f', 'd'], ['a', 'c', 'e', 'd'], ['a', 'c', 'f', 'd'], ['a', 'e', 'f', 'd'], ['b', 'c', 'e', 'd'], ['b', 'c', 'f', 'd'], ['b', 'e', 'f', 'd'], ['c', 'e', 'f', 'd'], ['a', 'b', 'c', 'e'], ['a', 'b', 'd', 'e'], ['a', 'b', 'f', 'e'], ['a', 'c', 'd', 'e'], ['a', 'c', 'f', 'e'], ['a', 'd', 'f', 'e'], ['b', 'c', 'd', 'e'], ['b', 'c', 'f', 'e'], ['b', 'd', 'f', 'e'], ['c', 'd', 'f', 'e'], ['a', 'b', 'c', 'f'], ['a', 'b', 'd', 'f'], ['a', 'b', 'e', 'f'], ['a', 'c', 'd', 'f'], ['a', 'c', 'e', 'f'], ['a', 'd', 'e', 'f'], ['b', 'c', 'd', 'f'], ['b', 'c', 'e', 'f'], ['b', 'd', 'e', 'f'], ['c', 'd', 'e', 'f']]
posted by doteatop at 9:34 AM on June 18, 2010

Ah dang, that first line should be:

>>> from itertools import combinations

grabbed the wrong line from my notes.
posted by doteatop at 9:35 AM on June 18, 2010

Here's a Matlab function that will do it.
posted by knile at 9:36 AM on June 18, 2010

Just noticed you said "The remaining 4 slots will be filled with a 4th item and that item cannot be one of the previous 3." Assuming you mean the last four slots should be the same, that gives us:

>>> print [ list(i) + [j, j, j, j] for j in l for i in combinations(l, 3) if j not in i ]
[['b', 'c', 'd', 'a', 'a', 'a', 'a'], ['b', 'c', 'e', 'a', 'a', 'a', 'a'], ['b', 'c', 'f', 'a', 'a', 'a', 'a'], ['b', 'd', 'e', 'a', 'a', 'a', 'a'], ['b', 'd', 'f', 'a', 'a', 'a', 'a'], ['b', 'e', 'f', 'a', 'a', 'a', 'a'], ['c', 'd', 'e', 'a', 'a', 'a', 'a'], ['c', 'd', 'f', 'a', 'a', 'a', 'a'], ['c', 'e', 'f', 'a', 'a', 'a', 'a'], ['d', 'e', 'f', 'a', 'a', 'a', 'a'], ['a', 'c', 'd', 'b', 'b', 'b', 'b'], ['a', 'c', 'e', 'b', 'b', 'b', 'b'], ['a', 'c', 'f', 'b', 'b', 'b', 'b'], ['a', 'd', 'e', 'b', 'b', 'b', 'b'], ['a', 'd', 'f', 'b', 'b', 'b', 'b'], ['a', 'e', 'f', 'b', 'b', 'b', 'b'], ['c', 'd', 'e', 'b', 'b', 'b', 'b'], ['c', 'd', 'f', 'b', 'b', 'b', 'b'], ['c', 'e', 'f', 'b', 'b', 'b', 'b'], ['d', 'e', 'f', 'b', 'b', 'b', 'b'], ['a', 'b', 'd', 'c', 'c', 'c', 'c'], ['a', 'b', 'e', 'c', 'c', 'c', 'c'], ['a', 'b', 'f', 'c', 'c', 'c', 'c'], ['a', 'd', 'e', 'c', 'c', 'c', 'c'], ['a', 'd', 'f', 'c', 'c', 'c', 'c'], ['a', 'e', 'f', 'c', 'c', 'c', 'c'], ['b', 'd', 'e', 'c', 'c', 'c', 'c'], ['b', 'd', 'f', 'c', 'c', 'c', 'c'], ['b', 'e', 'f', 'c', 'c', 'c', 'c'], ['d', 'e', 'f', 'c', 'c', 'c', 'c'], ['a', 'b', 'c', 'd', 'd', 'd', 'd'], ['a', 'b', 'e', 'd', 'd', 'd', 'd'], ['a', 'b', 'f', 'd', 'd', 'd', 'd'], ['a', 'c', 'e', 'd', 'd', 'd', 'd'], ['a', 'c', 'f', 'd', 'd', 'd', 'd'], ['a', 'e', 'f', 'd', 'd', 'd', 'd'], ['b', 'c', 'e', 'd', 'd', 'd', 'd'], ['b', 'c', 'f', 'd', 'd', 'd', 'd'], ['b', 'e', 'f', 'd', 'd', 'd', 'd'], ['c', 'e', 'f', 'd', 'd', 'd', 'd'], ['a', 'b', 'c', 'e', 'e', 'e', 'e'], ['a', 'b', 'd', 'e', 'e', 'e', 'e'], ['a', 'b', 'f', 'e', 'e', 'e', 'e'], ['a', 'c', 'd', 'e', 'e', 'e', 'e'], ['a', 'c', 'f', 'e', 'e', 'e', 'e'], ['a', 'd', 'f', 'e', 'e', 'e', 'e'], ['b', 'c', 'd', 'e', 'e', 'e', 'e'], ['b', 'c', 'f', 'e', 'e', 'e', 'e'], ['b', 'd', 'f', 'e', 'e', 'e', 'e'], ['c', 'd', 'f', 'e', 'e', 'e', 'e'], ['a', 'b', 'c', 'f', 'f', 'f', 'f'], ['a', 'b', 'd', 'f', 'f', 'f', 'f'], ['a', 'b', 'e', 'f', 'f', 'f', 'f'], ['a', 'c', 'd', 'f', 'f', 'f', 'f'], ['a', 'c', 'e', 'f', 'f', 'f', 'f'], ['a', 'd', 'e', 'f', 'f', 'f', 'f'], ['b', 'c', 'd', 'f', 'f', 'f', 'f'], ['b', 'c', 'e', 'f', 'f', 'f', 'f'], ['b', 'd', 'e', 'f', 'f', 'f', 'f'], ['c', 'd', 'e', 'f', 'f', 'f', 'f']]
posted by doteatop at 9:37 AM on June 18, 2010

I'm confused - doteatop's solution includes both ['a', 'b', 'c', 'd'] and ['b', 'c', 'd', 'a']. This seems to contradict your statement that "order is unimportant (so for the purposes of this A,B,C = B,A,C = C,B,A etc)."


If that's true and order is unimportant, there are only 15 unique combinations, as given by the calculator I linked:

{a,b,c,d} {a,b,c,e} {a,b,c,f} {a,b,d,e} {a,b,d,f} {a,b,e,f} {a,c,d,e} {a,c,d,f} {a,c,e,f} {a,d,e,f} {b,c,d,e} {b,c,d,f} {b,c,e,f} {b,d,e,f} {c,d,e,f}

Am I misunderstanding something, missmagenta?
posted by chrisamiller at 9:52 AM on June 18, 2010

Hey Chris, what I heard was "The first 3 slots need to be filled with 3 unique items but their order is unimportant (so for the purposes of this A,B,C = B,A,C = C,B,A etc). The remaining 4 slots will be filled with a 4th item and that item cannot be one of the previous 3." - that the order was unimportant for the first three, but the rule for the fourth made the ordering of the complete list significant (otherwise I would just have said combinations(l, 4)).
posted by doteatop at 9:54 AM on June 18, 2010

Response by poster: Am I misunderstanding something, missmagenta?

Yes, as I said in the question the order of the first 3 are unimportant but I need 4. abc=bca but abcd != dbca.
posted by missmagenta at 9:58 AM on June 18, 2010

ah - okay, I grok what you were saying there now. Glad you got your answer!
posted by chrisamiller at 11:35 AM on June 18, 2010

There should be 60 of them -- there are twenty ways to choose three items out of six, and then three ways to pick the remaining item which gets repeated. I don't want to write code to generate them but this is a useful check.
posted by madcaptenor at 11:48 AM on June 18, 2010

If I'm interpreting your question correctly, ditto madcaptenor: 60.
posted by SuzB at 3:08 PM on June 18, 2010

Best answer:

n=6
for (i = 1; i <= n; i++)
	for (j = 1; j <= n-2; j++)
		for (k=j+1; k <= n-1; k++)
			for (m=k+1; m <= n; m++)
				if (i != j && i != k && i != m)
					print(j,k,m,i,i,i,i)

There's a more general version that can be translated to nearly any language, the only real trick is choosing the item that occurs four times first.
posted by anaelith at 4:26 PM on June 18, 2010