CODEWITHSUNDEEP
python-3.xalgorithmlistcombinationspartitioning
Stoner
Stoner

Reputation: 906

(Python) Finding all possible partitions of a list of lists subject to a size limit for a partition

Suppose that I have a list k = [[1,1,1],[2,2],[3],[4]], with size limit c = 4.

Then I will like to find all possible partitions of k subject ot c. Ideally, the result should be:

[ {[[1,1,1],[3]], [[2,2], [4]]}, {[[1,1,1],[4]], [[2,2], [3]]}, {[[1,1,1]], [[2,2], [3], [4]]}, ..., {[[1,1,1]], [[2,2]], [[3]], [[4]]} ]

where I used set notation { } in the above example (actual case its [ ]) to make it clearer as to what a partition is, where each partition contains groups of lists grouped together.

I implemented the following algorithm but my results do not tally:

def num_item(l):
    flat_l = [item for sublist in l for item in sublist]
    return len(flat_l)

def get_all_possible_partitions(lst, c):
    p_opt = []
    for l in lst:
        p_temp = [l]
        lst_copy = lst.copy()
        lst_copy.remove(l)
        iterations = 0
        while num_item(p_temp) <= c and iterations <= len(lst_copy):
            for l_ in lst_copy:
                iterations += 1
                if num_item(p_temp + [l_]) <= c:
                    p_temp += [l_]
        p_opt += [p_temp]
    return p_opt

Running get_all_possible_partitions(k, 4), I obtain:

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

I understand that it does not remove duplicates and exhaust the possible combinations, which I am stuck on.

Some insight will be great! P.S. I did not manage to find similar questions :/

Upvotes: 3

Views: 1083

Answers (3)

Sash Sinha
Sash Sinha

Reputation: 22370

Note: This answer is actually for a closed linked question.

If you only want to return the bipartitions of the list you can utilize more_iterools.set_partions:

>>> from more_itertools import set_partitions
>>>
>>> def get_bipartions(lst):
...     half_list_len = len(lst) // 2
...     if len(lst) % 2 == 0:
...         return list(
...             map(tuple, [
...                 p
...                 for p in set_partitions(lst, k=2)
...                 if half_list_len == len(p[0])
...             ]))
...     else:
...         return list(
...             map(tuple, [
...                 p
...                 for p in set_partitions(lst, k=2)
...                 if abs(half_list_len - len(p[0])) < 1
...             ]))
...
>>> get_bipartions(['A', 'B', 'C'])
[(['A'], ['B', 'C']), (['B'], ['A', 'C'])]
>>> get_bipartions(['A', 'B', 'C', 'D'])
[(['A', 'B'], ['C', 'D']), (['B', 'C'], ['A', 'D']), (['A', 'C'], ['B', 'D'])]
>>> get_bipartions(['A', 'B', 'C', 'D', 'E'])
[(['A', 'B'], ['C', 'D', 'E']), (['B', 'C'], ['A', 'D', 'E']), (['A', 'C'], ['B', 'D', 'E']), (['C', 'D'], ['A', 'B', 'E']), (['B', 'D'], ['A', 'C', 'E']), (['A', 'D'], ['B', 'C', 'E'])]

Upvotes: 1

javidcf
javidcf

Reputation: 59701

I think this does what you want (explanations in comments):

# Main function
def get_all_possible_partitions(lst, c):
    yield from _get_all_possible_partitions_rec(lst, c, [False] * len(lst), [])

# Produces partitions recursively
def _get_all_possible_partitions_rec(lst, c, picked, partition):
    # If all elements have been picked it is a complete partition
    if all(picked):
        yield tuple(partition)
    else:
        # Get all possible subsets of unpicked elements
        for subset in _get_all_possible_subsets_rec(lst, c, picked, [], 0):
            # Add the subset to the partition
            partition.append(subset)
            # Generate all partitions that complete the current one
            yield from _get_all_possible_partitions_rec(lst, c, picked, partition)
            # Remove the subset from the partition
            partition.pop()

# Produces all possible subsets of unpicked elements
def _get_all_possible_subsets_rec(lst, c, picked, current, idx):
    # If we have gone over all elements finish
    if idx >= len(lst): return
    # If the current element is available and fits in the subset
    if not picked[idx] and len(lst[idx]) <= c:
        # Mark it as picked
        picked[idx] = True
        # Add it to the subset
        current.append(lst[idx])
        # Generate the subset
        yield tuple(current)
        # Generate all possible subsets extending this one
        yield from _get_all_possible_subsets_rec(lst, c - len(lst[idx]), picked, current, idx + 1)
        # Remove current element
        current.pop()
        # Unmark as picked
        picked[idx] = False
    # Only allow skip if it is not the first available element
    if len(current) > 0 or picked[idx]:
        # Get all subsets resulting from skipping current element
        yield from _get_all_possible_subsets_rec(lst, c, picked, current, idx + 1)

# Test
k = [[1, 1, 1], [2, 2], [3], [4]]
c = 4
partitions = list(get_all_possible_partitions(k, c))
print(*partitions, sep='\n')

Output:

(([1, 1, 1],), ([2, 2],), ([3],), ([4],))
(([1, 1, 1],), ([2, 2],), ([3], [4]))
(([1, 1, 1],), ([2, 2], [3]), ([4],))
(([1, 1, 1],), ([2, 2], [3], [4]))
(([1, 1, 1],), ([2, 2], [4]), ([3],))
(([1, 1, 1], [3]), ([2, 2],), ([4],))
(([1, 1, 1], [3]), ([2, 2], [4]))
(([1, 1, 1], [4]), ([2, 2],), ([3],))
(([1, 1, 1], [4]), ([2, 2], [3]))

Upvotes: 2

Tim
Tim

Reputation: 2161

If all elements in the list are unique, then you can use bit.

Assume k = [a,b,c], which length is 3, then there are 2^3 - 1 = 7 partions:

if you use bit to compresent a, b, c, there will be

001 -> [c]
010 -> [b]
011 -> [b, c]
100 -> [a]
101 -> [a,c]
110 -> [a,b]
111 -> [a,b,c]

so, the key to solving this question is obvious now.

Upvotes: 2

Related Questions