N choose N/2 sublists of a list

Question

Is there an efficient way in Python to get all partitions of a list of size n into two subsets of size n/2? I want to get some iterative construct such that each iteration provides two non-overlapping subsets of the original list, each subset having size n/2.

For example:

A = [1,2,3,4,5,6]    # here n = 6
# some iterative construct
    # in each iteration, a pair of subsets of size n/2
    # subsets = [[1,3,4], [2,5,6]] for example for one of the iterations
    # subsets = [[1,2,5],[3,4,6]] a different iteration example

The subsets should be non-overlapping, e.g. [[1,2,3], [4,5,6]] is valid but [[1,2,3], [3,4,5]] is not. The order of the two subsets does not matter, e.g. [[1,2,3], [4,5,6]] does not count as different from [[4,5,6], [1,2,3]] and thus only one of those two should appear in an iteration. The order within each subset also does not matter, so [[1,2,3], [4,5,6]], [[1,3,2], [4,5,6]], [[3,2,1], [6,5,4]], etc. all count as the same and so only one of them should show up in whole iteration.

Answer 1

You will want to use itertools.combinations to do this. The inputs are the list you want to select items out of and the second is the number of items to select.

result = [list(item) for item in itertools.combinations(input, len(input) // 2)]

For an input of [1,2,3,4] this yields

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

As @ShadowRanger pointed out, if order matters in your lists and you want all permutations, you'll want to substitute itertools.permutations into the solution.

result = [list(item) for item in itertools.permutations(input, len(input) // 2)]
# [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]

Edit

Upon reading your question closer it is unclear if you want all n/2 permutations like I have shown or you want a list of lits where each element is yet another list of the two "halves" of the permutation.

To accomplish this, you could do the following (incorporating some indexing help from @Blckknght)

result = [[list(item[::2]), list(item[1::2])] for item in itertools.permutations(input)]

In this case, the output of [1,2,3,4] would be

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

Edit2

Since order doesn't matter but you want an approach similar to the last one (lists of lists of lists), that's a little tricky with the last approach because of the array slicing. One alternative is to use set and frozenset to construct the initial information (rather than lists), because in a set the ordering doesn't matter when checking for equality. This will automatically allow us to remove duplicates. We can then add an extra step to convert back to a list if that's what you prefer.

from itertools import permutations
tmp = set([frozenset([frozenset(k[::2]),frozenset(k[1::2])]) for k in permutations(input)]) 
result = [[list(el) for el in item] for item in tmp];

This will yield

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