递归生成器对象

Question

Python 2.7版

给定alleles列表和数组长度numb_alleles，例如：

alleles = [11, 12, 13, 14, 15, 16]
numb_alleles = 8

我一直在尝试遍历每个笛卡尔乘积，并选择符合以下选择标准的与我的研究相关的等位基因：

1. 笛卡尔积中的每一秒值必须大于它之前的值。例如，给定上述条件，笛卡尔积[13, 15, 11, 12, 14, 15, 16, 16]将满足选择标准，而[13, 15, 16, 12, 14, 15, 16, 16]将不满足选择标准，因为索引2和3。你知道吗
2. 在alleles中的每个值都必须出现在笛卡尔积中。 例如，[13, 15, 11, 12, 14, 15, 16, 16]将满足选择标准，而[13, 15, 11, 12, 14, 15, 11, 13]将不满足，因为16不在产品中。你知道吗

我一直在使用itertools.product(alleles, repeat = numb_alleles)遍历每个可能的笛卡尔积来进一步分析。然而，当numb_alleles增加到10或12时，总体计算量显著增加。你知道吗

我试图通过使用下面的递归函数选择相关的笛卡尔积来解决这个问题。你知道吗

def check_allele(allele_combination, alleles):
    """Check if all the alleles are present in allele_combination"""
    for allele in alleles:
        if allele not in allele_combination:
            return False
    return True

def recursive_product(alleles, numb_alleles, result):
    current_len = len(result[0])
    new_result = []
    final_result = []

    for comb in result:
        for allele in alleles:
            if current_len % 2 == 0:
                new_result.append(comb + [allele])
            elif current_len % 2 == 1:
                if comb[-1] <= allele:
                    new_result.append(comb + [allele])
                    if (check_allele(comb + [allele], alleles)):
                        final_result.append(comb + [allele])

    if current_len + 1 < numb_alleles:
        return recursive_product(alleles, numb_alleles, new_result)
    else:
        return final_result

a = (recursive_product(alleles, numb_alleles, [[]]))

但是，使用这种方法，我仍然无法处理numb_alleles = 12或alleles长度增加时的数组，因为我使用的是return，而不是yield。因此会导致内存不足错误。你知道吗

我想知道我是否有可能把这个函数变成一个生成器，或者是否有人可以建议一个不同的方法，这样我就可以进一步计算numb_alleles = 12和更长的alleles数组的输出。你知道吗

非常感谢！你知道吗

Answer 1

您说过：“笛卡尔积中的每一秒值必须大于它之前的值。”但在您的示例[13, 15, 11, 12, 14, 15, 16, 16]中，槽7（16）中的项等于上一槽中的项，因此我假设您的意思是奇数索引处的项必须大于等于上一偶数索引处的项。你知道吗

下面的生成器比您当前的方法效率高一些，它避免了在RAM中保存大型临时列表。核心思想是使用itertools.product为偶数时隙生成组合，然后再次使用product填充满足选择准则1的奇数时隙。我们使用set操作来确保最终的组合包含alleles中的每个项。你知道吗

from itertools import product

def combine_alleles(alleles, numb_alleles):
    ''' Make combinations that conform to the selection criteria. First create
        the items for the even slots, then create items for the odd slots such
        that each odd slot item >= the corresponding even slot item. Then test
        that the whole combination contains each item in alleles.
    '''
    # If the number of unique items in the even slots is < min_len, then it's
    # impossible to make a full combination containing all of the alleles.
    min_len = len(alleles) - numb_alleles // 2

    # Create a function to test if a given combination
    # contains all of the alleles.
    alleles_set = set(alleles)
    complete = alleles_set.issubset

    # Make lists of alleles that are >= the current allele number
    higher = {k: [u for u in alleles if u >= k] for k in alleles}

    # Make combinations for the even slots
    for evens in product(alleles, repeat=numb_alleles // 2):
        if len(set(evens)) < min_len:
            continue
        # Make combinations for the odd slots that go with this
        # combination of evens.
        a = [higher[u] for u in evens]
        for odds in product(*a):
            if complete(evens + odds):
                yield [u for pair in zip(evens, odds) for u in pair]

# test

alleles = [11, 12, 13, 14, 15, 16]
numb_alleles = 8

for i, t in enumerate(combine_alleles(alleles, numb_alleles), 1):
    print(i, t)

这段代码找到16020个组合，因此输出太大，无法包含在这里。你知道吗

---

这里有一个替代的生成器，它更接近您的版本，但是在我的测试中，它比我的第一个版本慢了一点。你知道吗

def combine_alleles(alleles, numb_alleles):
    total_len = len(alleles)

    # Make lists of alleles that are >= the current allele number
    higher = {k: [u for u in alleles if u >= k] for k in alleles}

    def combos(i, base):
        remaining = numb_alleles - i
        if len(set(base)) + remaining < total_len:
            return

        if remaining == 0:
            yield base
            return

        ii = i + 1
        for u in higher[base[-1]] if i % 2 else alleles:
           yield from combos(ii, base + [u])

    yield from combos(0, [])

此版本适用于Python3。Python 2没有yield from，但这很容易修复：

yield from some_iterable

相当于

for t in some_iterable:
    yield t