如何避免Python中的内存错误，同时通过来自另一个列表中的大量排列来ziping列列表以获取唯一的组合？

Question

我有以下代码来生成卡车和三位数排列之间的所有独特组合。我（下）的方式给了我正确的结果。但是，只有在Len（Tripares）＆Lt时才起作用； 10。 11我遇到了一个内存错误。有没有办法避免此内存错误？

import itertools
from itertools import cycle

trucks=['A','B','C']
tripares = ['trip1', 'trip2', 'trip3', 'trip4', 'trip5', 'trip6', 'trip7', 'trip8', 'trip9', 'trip10', 'trip11', 'trip12'] 

# Get all permutations of the tripares list
perms = itertools.permutations(tripares,len(tripares))

# Zip the two lists and cycle the trucks list so all trips are matched with a truck
combinations = [list(zip(cycle(trucks), x)) for x in perms]

# Drop duplicates to get unique values
combs_unique = set([tuple(sorted(x)) for x in combinations ])

print(len(combs_unique))
# Should print 34650

Answer 1

如果您只想要唯一组合的数字，则可以简单地计算它，而无需生成所有这些大序列。

让我们以您的榜样输入。第一辆卡车将有4次旅行中有4辆（无卡车旅行 /否卡车）：相当于12！ / 8！ / 4！ = 495。然后，第二辆卡车将进行剩下的8次旅行中的4次：8！ / 4！ / 4！ = 70。第三辆卡车进行了最后4次旅行：4！ / 0！ / 4！ = 1。因此总数为495 * 70 * 1 = 34650

您可以使用这样的代码：

from math import factorial

def count_combos(n,k):
    return factorial(n)//factorial(k)//factorial(n-k)

def count_trips(ntrips, ntrucks):
    total = 1
    tt = ntrips//ntrucks
    for x in range(ntrips, tt, -tt):
        total *= count_combos(x, tt)
    return total

count_trips(12,3)
34650

编辑：如果需要实际组合，则获取组合

，而不仅仅是它们的数字，您可以一次通过递归来“手动”中的代码生成它们：列出第一辆卡车的所有旅行的连击，附加到每个卡车的每个旅行中，第二辆卡车剩余的旅行的连击列表和因此，直到卡车只剩下一个可能的组合。这使用了合理的内存，并且也不像人们期望的那样慢：

from itertools import combinations

def list_combos(trips, trucks):
        #print(trips)
        combos = []
        ntrips = len(trips)
        ntrucks = len(trucks)
        tt = ntrips//ntrucks
        if ntrips == tt:
                return trips
        fs_trips = frozenset(trips)
        for c in combinations(fs_trips, tt):
                for subc in list_combos2(fs_trips.difference(c), tt):
                        #print(c, subc)
                        combos.append(c + tuple(subc))
        return combos
    
def list_combos2(fs_trips, tt):
        #print('combos2:', fs_trips)
        combos = []
        ntrips = len(fs_trips)
        if ntrips == tt:
                #print('returning')
                return (fs_trips,)
        for c in combinations(fs_trips, tt):
                for subc in list_combos2(fs_trips.difference(c), tt):
                        #print(c, subc)
                        combos.append(c + tuple(subc))
        return combos

x = list_combos(['t1','t2','t3','t4','t5','t6','t7','t8','t9','t10','t11','t12'], ['a','b','c'])
len(x)
34650

我在18次旅行/3辆卡车（17153136连击）和16/4（63063000连击）上对其进行了测试。在后一种情况下，我的PC上花费了大约275秒。

（注意：我只是为每个组合返回元组旅行，而无需将其添加到卡车上 subtuples中。只需考虑第一个ntrips // ntrucks元素属于第一辆卡车，依此类推）。

优化

由于您想提取最佳组合，为什么要生成全部，然后进行计算？从上面的代码开始，一旦获得每个组合，就可以很容易地计算每个组合的消耗，将其与当前最佳的最佳选择，并且只能跟踪新的最佳状态，甚至不维护巨型列表。

这种方法甚至可以让您进行一些前进检查，在之前丢弃组合，然后完全定义它，从而大大加快执行力。

Answer 2

第一次尝试是使用发电机，而不是立即存储列表中的排列。

# Zip the two lists and cycle the trucks list so all trips are matched with a truck
combinations = [list(zip(cycle(trucks), x)) for x in perms](1)

# Drop duplicates to get unique values
combs_unique = set([tuple(sorted(x)) for x in combinations ](2))(3)

这创建了2-3个排列副本：一次创建组合列表一次。（1）
然后，您可以创建另一个列表，其中包含分类元素（2）。
最后，您使用此新列表来创建您的列表。（3）

因此，您可以尝试使用圆形支架使用发电机，然后立即对列表中的元素进行排序：

combinations = (sorted(zip(cycle(trucks), x) for x in perms)
combs_unique = set(tuple(x) for x in combinations)

在这里，您实际上只有一次创建一组，而无需浪费所有的元素中间的空间。