贪婪算法将数字列表分成两个分区，每个分区的数量相同 Python
Greedy algorithm to split a list of lists of numbers into two partitions with same amount of each number in Python
我有一个随机正整数子列表列表。此列表由 3 个参数控制：
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，如果足够快）之后建议二分时，我们应该相信没有这样的二分。当参数很大时，即使检查是否存在这种二分法也是不可行的。
天哪，这个真是太棒了。首先，让我说明一点。贪心算法是确定性的，因为它总是会选择最优路径。其次，实际上能够对某些东西进行二分法的可能性非常非常小。我还建议，如果你想 生成 双分区，尝试从这样的随机集中找到它们并不是一个好主意。
总之，上代码。首先，让我说代码不漂亮，也没有完全优化。到最后，我在某些领域甚至都不是 Pythonic，但它们都很容易修复。我已经做了好几个小时了，但这是一个有趣的项目。复制名单是主要嫌疑人。您可以根据自己的时间重新编写并优化它。我也不能保证它没有错误，但我很确定它是。唯一的例外是，如果您想要任何结果，您需要确保它至少进行一次“仔细”搜索。这让我想到了下一点，即算法本身。
我们从一个非常标准的贪心算法开始。我们从我们的 partitionee 中选择一个索引，WLOG，将它分配给左二分区。接下来我们看看插入所有剩余列表的所有可能方法。我们选择最接近 0 的那个。我们重复直到遇到某个断点，之后我们切换到您的详尽算法。
现在，很可能我们没有为您的常量的高值找到分区。我相信这只是一个统计问题，而不是算法的问题，但我可能是错的。
我还实施了一个粗略的可行性测试，您很快就会发现大约 90% 的随机生成的嵌套列表可以立即被丢弃，因为它们不可能进行二分法。
然而，添加贪心算法现在允许我在我的机器上从测试 ~15 个长度的分区到 ~30 个长度的分区，并成功找到一个。它还 运行s 不到十分之一秒，例如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)
我有一个随机正整数子列表列表。此列表由 3 个参数控制：
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，如果足够快）之后建议二分时，我们应该相信没有这样的二分。当参数很大时，即使检查是否存在这种二分法也是不可行的。
天哪，这个真是太棒了。首先，让我说明一点。贪心算法是确定性的，因为它总是会选择最优路径。其次，实际上能够对某些东西进行二分法的可能性非常非常小。我还建议，如果你想 生成 双分区，尝试从这样的随机集中找到它们并不是一个好主意。
总之，上代码。首先，让我说代码不漂亮，也没有完全优化。到最后，我在某些领域甚至都不是 Pythonic，但它们都很容易修复。我已经做了好几个小时了，但这是一个有趣的项目。复制名单是主要嫌疑人。您可以根据自己的时间重新编写并优化它。我也不能保证它没有错误，但我很确定它是。唯一的例外是，如果您想要任何结果，您需要确保它至少进行一次“仔细”搜索。这让我想到了下一点，即算法本身。
我们从一个非常标准的贪心算法开始。我们从我们的 partitionee 中选择一个索引，WLOG，将它分配给左二分区。接下来我们看看插入所有剩余列表的所有可能方法。我们选择最接近 0 的那个。我们重复直到遇到某个断点，之后我们切换到您的详尽算法。
现在，很可能我们没有为您的常量的高值找到分区。我相信这只是一个统计问题，而不是算法的问题，但我可能是错的。
我还实施了一个粗略的可行性测试，您很快就会发现大约 90% 的随机生成的嵌套列表可以立即被丢弃，因为它们不可能进行二分法。
然而，添加贪心算法现在允许我在我的机器上从测试 ~15 个长度的分区到 ~30 个长度的分区，并成功找到一个。它还 运行s 不到十分之一秒，例如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)