max_num
: 每个子列表中允许的最大整数,例如如果max_num=3
,那么列表将如下所示:[[1,3], [3], [1,2,3], [1], ...]
;max_length
: 每个子列表中的最大整数个数;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)后,我们应该相信不存在这样的二分法。当参数很大时,即使检查这种二分法是否存在也将是不可行的。