Python - 从大量的组合中构建符合特定条件的子列表

Question

读了很长时间，第一次找不到我正在研究的东西的答案。在

我有一个93个字符串的列表，每个6个字符长。从这93个字符串中，我想确定一组20个字符串，它们都符合相对于集合中其他字符串的特定标准。同时itertools.组合会给我所有可能的组合，不是所有的条件都值得检查。在

例如，如果[list[0]、list[1]等失败，因为list[0]和list[1]不能在一起，那么其他18个字符串是什么都不重要，集合每次都会失败，这是浪费大量的检查。在

目前我有20个嵌套for循环，但似乎必须有一个更好/更快的方法来实现它

for n1 in bclist:
    building = [n1]
    n2bclist = [bc for bc in bclist if bc not in building]
    for n2 in n2bclist:              #this is the start of what gets repeated 19 times
        building.append(n2)
        if test_function(building): #does set fail? (counter intuitive, True when fail, False when pass)
            building.remove(n2)
            continue
        n3bclist = [bc for bc in bclist if bc not in building]
        #insert the additional 19 for loops, with n3 in n3, n4 in n4, etc
        building.remove(n2)

在第20个for循环中有print语句，如果有一组20甚至存在，就会向我发出警报。for语句至少允许我在单次加法失败时提前跳过集合，但当较大的组合失败时没有内存：

例如，[list[0], list[1]]失败，所以跳到通过的[list[0], [list[2]]。下一个是[list[0], list[2], list[1]]，它将失败，因为0和1再次在一起，所以它将移动到{}，这可能通过也可能不通过。我担心的是，最终它还将考验：

• [list[0], list[3], list[2]]
• [list[2], list[0], list[3]]
• [list[2], list[3], list[0]]
• [list[3], list[0], list[2]]
• [list[3], list[2], list[0]]

所有这些组合的结果都将与之前的组合相同。基本上我交易的是itertools.组合测试我知道的所有集合的组合都失败了，因为早期的值失败了，for循环把值的顺序当作一个因素，而我不关心它们的顺序。这两种方法都大大增加了代码完成所需的时间。在

任何关于如何除掉魔鬼的想法都将不胜感激。在

Answer 1

您可以利用问题的两个方面：

1. 秩序不重要
2. 如果test_function(L)是True，那么{}的任何子列表的test_function也将是{}

您还可以通过处理索引0-92而不是list[0]-list[92]-我们只关心test_function列表的内容是什么。在

下面的代码首先找到可行的对，然后是4对、8对和16对。最后，它会找到16和4的所有可行组合，从而得到20的列表。但是有超过10万套的8套，所以还是太慢了，我放弃了。也许你可以按照同样的思路做一些事情，但是用itertools来加速，但可能还不够。在

target = range(5, 25)
def test_function(L):
    for i in L:
        if not i in target:
            return True
def possible_combos(A, B):
    """
    Find all possible pairings of a list within A and a list within B
    """
    R = []
    for i in A:
        for j in B:
            if i[-1] < j[0] and not test_function(i + j):
                R.append(i + j)
    return R
def possible_doubles(A):
    """
    Find all possible pairings of two lists within A
    """
    R = []
    for n, i in enumerate(A):
        for j in A[n + 1:]:
            if i[-1] < j[0] and not test_function(i + j):
                R.append(i + j)
    return R
# First, find all pairs that are okay
L = range(92) 
pairs = []
for i in L:
    for j in L[i + 1:]:
        if not test_function([i, j]):
            pairs.append([i, j])

# Then, all pairs of pairs
quads = possible_doubles(pairs)
print "fours", len(quads), quads[0]
# Then all sets of eight, and sixteen
eights = possible_doubles(quads)
print "eights", len(eights), eights[0]
sixteens = possible_doubles(eights)
print "sixteens", len(sixteens), sixteens[0]

# Finally check all possible combinations of a sixteen plus a four
possible_solutions = possible_combos(sixteens, fours)
print len(possible_solutions), possible_solutions[0]

我找到了一个更好的解决方案。首先，确定范围（0-92）内符合test_function的所有值对，并保持这些对的顺序。假设第一对的第一个值必须是解的第一个值，最后一个对的第二个值必须是解的最后一个值（但是请检查。。。这个假设对test_function成立吗？如果这不是一个安全的假设，那么您需要对start和finish的所有可能值重复find_paths）。然后找到从第一个值到最后一个值的路径，它的长度为20个值，并且符合test_function。在

^{pr2}$

Answer 2

def gen(l, n, test, prefix=()):
  if n == 0:
    yield prefix
  else:
    for i, el in enumerate(l):
      if not test(prefix + (el,)):
        for sub in gen(l[i+1:], n - 1, test, prefix + (el,)):
          yield sub

def test(l):
  return sum(l) % 3 == 0 # just a random example for testing

print list(gen(range(5), 3, test))

这将从l中选择基数n的子集，这样test(subset) == False。在

它尽量避免不必要的工作。但是，鉴于有1e20方法可以从93个元素中选择20个元素，您可能需要重新考虑您的总体方法。在

Answer 3

使用当前方法，但也要跟踪索引，以便在内部循环中可以跳过已检查的元素：

bcenum = list(enumerate(bclist))
for i1, n1 in bcenum:
    building = [n1]
    for i2, n2 in bcenum[i1+1:]:              #this is the start of what gets repeated 19 times
        building.append(n2)
        if test_function(building): #does set fail? (counter intuitive, True when fail, False when pass)
            building.remove(n2)
            continue
        for i3, n3 in bcenum[i2+1:]:
            # more nested loops
        building.remove(n2)