python - 将元素列表分配到具有不同排除项的 3 个列表中

Question

我有一个包含约 100,000 个唯一 ID 的列表，我需要将它们分发到 3 个列表中，以便每个列表获得约 33,000 个 ID。

棘手的部分是，每个列表都有约 20k 个无法使用的唯一 ID:排除列表。这 3 个排除列表重叠了 15%-50%，大小也各不相同，但最终，在排除之后，原始列表的内容足以各占 33%。

biglist = [] #100k elements
a_exc = [] #15k elements in common w/biglist
b_exc = [] #25k elements in common w/biglist
c_exc = []  #30k elements in common w/biglist

# function to distribute biglist into a_list, b_list, and c_list 
# such that no element in a_list is in a_exc, etc.
# but all elements in biglist are distributed if possible not in all 3 exc lists
# and a/b/c are equal in size or as close to equal as possible

由于排除列表重叠，因此并不像按顺序分配到每个列表那么简单。无论如何，我有一堆必须解决的问题，并且我需要将它们全部迭代地添加起来。在某些情况下，排除列表各自占较大列表的约 50%，并且彼此最多可以重叠约 50%。

这里有一些测试代码，用于显示为了速度而使用 1/10 元素的问题(在我的 CPU 上执行此操作对于 100k 和 30k 需要一段时间)。当我运行这个程序时，我始终获得所有 3 个元素的 ~3333、3333、2450，这与我在较大列表上运行它时得到的分布类似。

import random

def lst_maker(num):
    l = []
    for i in range(num):
      a = random.randint(1000000000, 9999999999)
      while a in l:
        a = random.randint(1000000000, 9999999999)
      l.append(a)
    return l

def exc_maker(inl, num):
    l = []
    for i in range(num):
        a = random.choice(inl)
        while a in l:
            a = random.choice(inl)
        l.append(a)
    return l


biglist = lst_maker(10000)

a_exc = exc_maker(biglist, 3000)
b_exc = exc_maker(biglist, 3000)
c_exc = exc_maker(biglist, 3000)

def distribute_3(lst):
    lst = set(lst)
    lst = list(lst)
    ll = len(lst)//3
    random.shuffle(lst)
    a = []
    b = []
    c = []
    for e in lst:
            if e not in a_exc and len(a) < ll:
                a.append(e)
            elif e not in b_exc and len(b) < ll:
                b.append(e)
            elif e not in c_exc and len(c) < ll:
                c.append(e)
    return a, b, c

a_list, b_list, c_list = distribute_3(biglist)

print len(a_list), len(b_list), len(c_list)

Answer 1

除了将项目分布在列表上之外，该问题还存在三个主要复杂性:

• 排除列表可防止简单拆分；
• 排除列表本身可能包含重复的排除项，因此简单的基于集合的解决方案不起作用；
• 排除列表将提供一个解决方案，但任何填充方法都可能导致结果列表过早地填充可能已进入其他列表的项目。

因此，有效的解决方案是简单地尝试将项目添加到可用的第一个列表中，但如果遇到问题，它只会回溯到之前的添加 - 如果最终遇到问题，对之前的添加等等。

在函数式语言中，这种类型的回溯可以在递归函数中很好地实现，但由于 Python 的最大递归深度非常有限，因此迭代方法可能更好 - 特别是考虑到数据集的大小。

这是我的解决方案:

# generate list of identifiers
biglist = list(range(20))

# arbitrary exclusions, with some duplication
a_exc = [0, 2, 8, 15]
b_exc = [1, 3, 4, 6, 12]
c_exc = [0, 1, 5, 6, 7, 9, 1, 0]


def distribute(xs, n, exclusions):
    # will distribute the contents of list xs over n lists, excluding items from exclusions[m] for the m-th list
    # returns a list of lists (destructive, so xs will be empty after execution, pass in a copy to avoid)

    # initialise result lists
    result = [set() for _ in range(n)]

    # calculate maximum size for each of the list for a balanced distribution
    result_size = len(xs) // n
    if len(xs) % n > 0:
        result_size += 1

    # initialise a list of additions, to allow for backtracking; recursion would be cleaner,
    # but your dataset is too large an Python is not a functional language that is optimised for this
    additions = []

    # add all xs to the lists, trying the list in order, backtracking if lists fill up
    while xs:
        # get the last element from the list
        x = xs.pop()
        # find a place to add it, starting at the first list
        i = 0
        while True:
            while i < n:
                # find a list that's not full and can take x
                if len(result[i]) < result_size and x not in exclusions[i]:
                    # add it
                    result[i].add(x)
                    # remember this exact addition
                    additions.append((i, x))
                    break
                i += 1
            # if x could not be added (due to exclusions and full lists)
            if i == n:
                # put current x back at the end of the list
                xs.append(x)
                # go back to the previous x
                i, x = additions.pop(-1)
                # take it out from the list it was put into
                result[i].remove(x)
                # try putting it in the next list available
                i += 1
            else:
                break
    return result


spread_lists = distribute(biglist, 3, [a_exc, b_exc, c_exc])

print(spread_lists)

还有优化的空间，但我确实认为这有效。

事实上，在生成一些较大的测试集后，我发现算法需要优化，这实际上非常简单:按匹配的排除数对输入列表进行排序。因此，被排除 n 次的标识符会先于那些被排除 n-1 次的标识符进行处理，依此类推。

这将以下行添加到 distribute 的开头:

# sort the input by most exclusions, most exclusions last, as list is processed in reverse order
xs = [x for _, x in sorted([([x in exc for exc in exclusions].count(True), x) for x in xs])]

这还有一个额外的优点，即不再清空 xs(如果这是不希望的)。