python - 贪婪算法将数字列表的列表分成两个分区，每个分区在 Python 中的数量相同

Question

我有一个随机正整数子列表列表。该列表由 3 个参数控制:

1. max_num:每个子列表中允许的最大整数，例如如果 max_num = 3，列表将类似于 [[1,3], [3], [1,2,3], [1], ...];
2. max_length:每个子列表的最大整数个数；
3. n_gen:生成的子列表的个数，即列表的长度。

您可以使用以下代码生成这样的列表

import random

random.seed(10)
def random_numbers(length, max_num):
    return [random.randint(1, max_num) for _ in range(length)]

max_num = 3
max_length = 3 # I want max_length=10
n_gen = 10 # I want n_gen=200

lst = [random_numbers(random.randint(1, max_length), max_num) for _ in range(n_gen)]

现在我想把列表分成两个分区，每个分区有相同数量的每个数字。例如，如果 lst = [[1,2,3], [2,3], [1,3], [3]]，其中一个解决方案是 bipartition = [[[1,2,3], [3]], [[2,3], [1,3]]]。

我设法为所有可能的二分法编写了以下暴力枚举，这对小参数很有效。

from itertools import product

lst1 = []
lst2 = []
for pattern in product([True, False], repeat=len(lst)):
    lst1.append([x[1] for x in zip(pattern, lst) if x[0]])
    lst2.append([x[1] for x in zip(pattern, lst) if not x[0]])

bipartitions = []
for l1, l2 in zip(lst1, lst2):
    flat1 = [i for l in l1 for i in l]
    flat2 = [i for l in l2 for i in l]
    if sorted(flat1) == sorted(flat2):
        bipartitions.append([l1, l2])

for bipartition in bipartitions:
    print(bipartition)

输出:

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

但是，当参数变大时，这就变得不可行了。现在我想生成每个数字具有相同数量的随机二分法，我想一个贪心算法就可以了。对于我当前的任务，我需要使用

max_num = 3
max_length = 10
n_gen = 200

有什么建议吗？

编辑:我知道在某些情况下根本不可能进行这种二分法。我的想法是，当贪婪算法在最大数量的建议(例如 1000，如果足够快)之后建议二分时，我们应该相信没有这样的二分。当参数很大时，即使检查是否存在这种二分法也是不可行的。

Answer 1

天哪，这真是个傻瓜。首先，让我说明一点。贪心算法是确定性的，因为它总是会选择最优路径。其次，实际上能够对某些东西进行二分法的可能性非常非常小。我还建议，如果您想生成二分法，像这样尝试从随机集中找到它们并不是一个好主意。

无论如何，先上代码。首先，让我说代码不漂亮，也没有完全优化。到最后，我在某些领域甚至都不是 Pythonic，但它们都很容易修复。我已经做了好几个小时了，但这是一个有趣的项目。复制名单是主要嫌疑人。您可以根据自己的时间重新编写并优化它。我也不能保证它没有错误，但我很确定它是。唯一的异常(exception)是，如果您想要任何结果，您需要确保它至少进行一次“仔细”搜索。这就引出了下一点，即算法本身。

我们从一个非常标准的贪心算法开始。我们从我们的 partitionee 中选择一个索引，WLOG，将它分配给左二分区。接下来我们看看插入所有剩余列表的所有可能方法。我们选择最接近 0 的那个。我们重复直到遇到某个断点，之后我们切换到您的详尽算法。

现在，很可能我们没有为您的常量的高值找到一个分区。我相信这只是一个统计问题，而不是算法的问题，但我可能是错的。

我还实现了一个粗略的可行性测试，您很快就会发现大约 90% 的随机生成的嵌套列表可以立即被丢弃，因为它们不可能进行二分法。

但是，添加贪心算法现在允许我在我的机器上从测试 ~15 个长度的分区到 ~30 个长度的分区，并成功找到一个。它也可以在不到十分之一秒的时间内运行，例如3, 3, 40, 12 作为它的常量。

最后是代码 注意我只让它生成一个分区来测试，所以你可能需要运行几次才能得到一个可行的分区:

from itertools import product
import random
import datetime
import time
import sys

MAX_NUM = 3
MAX_LEN = 3
NUM_GEN = 200
NSWITCH = 12

random.seed(time.time())

def feasible(partitionee):
    '''Does a rough test to see if it is feasible to find a partition'''
    counts = [0 for _ in range(MAX_NUM)]
    flat = [x for sublist in partitionee for x in sublist]
    for n in flat:
        counts[n-1] += 1
    for n in counts:
        if n % 2 != 0:
            return False
    return True 

def random_numbers(length, max_num, n_lists):
    '''Create a random list of lists of numbers.'''

    lst = []
    for i in range(n_lists):
        sublist_length = random.randint(1, length)
        lst.append([random.randint(1, max_num) for _ in range(sublist_length)])
    return lst


def diff(lcounts, rcounts):
    '''Calculate the difference between the counts in our dictionaries.'''

    difference = 0
    for i in range(MAX_NUM):
        difference += abs(lcounts[i] - rcounts[i])

    return difference


def assign(partition, d, sublist):
    '''Assign a sublist to a partition, and update its dictionary.'''

    partition.append(sublist)
    for n in sublist:
        d[n-1] += 1


def assign_value(d1, d2, sublist):
    '''Calculates the loss of assigning sublist.'''

    for n in sublist:
        d1[n-1] += 1
    left_score = diff(d1, d2)
    for n in sublist:
        d1[n-1] -= 1
        d2[n-1] += 1
    right_score = diff(d1, d2)
    for n in sublist:
        d2[n-1] -= 1

    return (left_score, right_score)


def greedy_partition(left, right, lcounts, rcounts, i, partitionee):
    # Assign the i:th sublist to the left partition.
    assign(left, lcounts, partitionee[i])
    del partitionee[i]

    for _ in range(NUM_GEN - NSWITCH):
        # Go through all unassigned sublists and get their loss.
        value_for_index = {}
        for i, sublist in enumerate(partitionee):
            value = assign_value(lcounts, rcounts, sublist)
            value_for_index[i]  = value

        # Find which choice would be closest to 0 difference.
        min_value    = 100000000000 # BIG NUMBER
        best_index  = -1
        choose_left = True
        for key, value in value_for_index.items():
            if min(value) < min_value:
                min_value    = min(value)
                choose_left = value[0] < value[1]
                best_index  = key

        # Assign it to the proper list.
        if choose_left:
            assign(left, lcounts, partitionee[best_index])
        else:
            assign(right, rcounts, partitionee[best_index])
        del partitionee[best_index]

    return diff(lcounts, rcounts)



# Create our list to partition.
partition_me = random_numbers(MAX_LEN, MAX_NUM, NUM_GEN)

start_time = datetime.datetime.now()

# Start by seeing if it's even feasible to partition.
if not feasible(partition_me):
    print('No bipartition possible!')
    sys.exit()


# Go through all possible starting arrangements.
min_score_seen = 100000000000 # BIG NUMBER
best_bipartition = []
for i in range(NUM_GEN):
    # Create left and right partitions, as well as maps to count how many of each
    # number each partition has accumulated.
    left  = []
    right = []
    lcounts  = [0 for i in range(MAX_NUM)]
    rcounts  = [0 for i in range(MAX_NUM)]

    # Copy partitionee since it will be consumed.
    partition = partition_me.copy()

    # Do greedy partition.
    score = greedy_partition(left, right, lcounts, rcounts, i, partition)
    if score < min_score_seen:
        min_score_seen = score
        best_bipartition = [left] + [right]

# Now that we've been greedy and fast, we will be careful and slow.
# Consider all possible remaining arrangements.
print('Done with greedy search, starting careful search.')
left = best_bipartition[0]
right = best_bipartition[1]

for pattern in product([True, False], repeat=len(partition)):
    lst1 = left  + ([x[1] for x in zip(pattern, partition) if x[0]])
    lst2 = right +([x[1] for x in zip(pattern, partition) if not x[0]])
    left_flat  = [x for sublist in lst1 for x in sublist]
    right_flat  = [x for sublist in lst2 for x in sublist]
    if sorted(left_flat) == sorted(right_flat):
        print('Found bipartition by careful search:')
        print([lst1] + [lst2])
        break

end_time = datetime.datetime.now()
print('Time taken: ', end='')
print(end_time - start_time)