Python计算唯一列表置换的可能性

Question

所以我在处理列表/字符串的排列时遇到了一个问题，我很难解决这个问题。在

所以，假设我有几个列表：

list1 = ["a"]
list2 = ["a","b","c","d"]
list3 = ["b","e"]
list4 = ["f","g","a"]

我需要计算所有可能的排列组合的数量，同时从每个列表中选择一个字符。所以，从第一个列表中，我选择了一个角色。”在这种情况下，因为列表中只有一个项目。接下来，我从第二个列表中选择一个项目，但它不能是“a”，因为它是在我之前的列表中选择的，所以它可以是“b”、“c”或“d”。接下来，我从第三个列表中选择一个项目，如果我在第一个列表中选择了“a”，在第二个列表中选择了“b”，那么我只能选择“e”，因为“b”之前已经使用过了。第四份名单也是如此。在

所以我需要从我的列表中计算出所有可能的独特字符组合组合。希望大家都能理解我的要求。或者，如果可能的话，我甚至不需要创建排列列表，我只需要计算组合的总数。因为实际问题中可能有大量的单独列表，所以内存占用较少

对我的问题再详细一点。。。如果我有两个清单： 列表1=[“a”] 列表2=[“b”]

只有一个组合，因为您在置换字符串中保留了位置。列表一不包含b，因此唯一的组合可以是（“a”，“b”），而不是（“b”，“a”）。为了进一步扩展这个问题的限制。。我不一定要检索所有排列的结果，我只想返回可能排列的总数。返回结果占用了太多的内存，因为我将使用非常粗糙的15个列表，每个列表中有1到15个字符。在

Answer 1

使用^{}从列表中生成所有可能的组合。然后，使用^{}，过滤掉包含重复字符的所有组合。一种简单的方法是，如果删除所有重复项（即，如果从列表中创建一个集合），则检查列表的长度是否保持不变。在

import itertools

list1 = ["a"]
list2 = ["a","b","c","d"]
list3 = ["b","e"]
list4 = ["f","g","a"]

f = lambda x: len(x) == len(set(x))
it = itertools.ifilter(f, itertools.product(list1, list2, list3, list4))

# print all combinations
for combination in it:
    print combination

Answer 2

使用itertools.product. 它遍历所有排列，为每个列表选择一个项。另外，使用列表理解来消除不满足您的需求的迭代。在

>>> a='a'
>>> b='abcd'
>>> c='be'
>>> d='fga'
>>> import itertools
>>> [a+b+c+d for a,b,c,d in itertools.product(a,b,c,d) if b != a and c not in [a,b] and d not in [a,b,c]]
['abef', 'abeg', 'acbf', 'acbg', 'acef', 'aceg', 'adbf', 'adbg', 'adef', 'adeg']

Answer 3

您可以缓存“从第i个列表开始，不包括S中的元素”的计数。通过小心地将S限制为只包含可能被排除的字符（即，仅限于出现在后面的列表中的元素），可以减少重复计算的数量。在

下面是一个示例程序：

def count_uniq_combs(sets, i, excluding, cache):
    if i == len(sets): return 1
    key = (i, excluding)
    if key in cache:
        return cache[key]
    count = 0
    for c in sets[i][0]:
        if c in excluding: continue
        newx = (excluding | set([c])) & sets[i][1]
        count += count_uniq_combs(sets, i + 1, newx, cache)
    cache[key] = count
    print key, count
    return count

def count(xs):
    sets = [[set(x)] for x in xs]
    # Pre-compute the union of all subsequent sets.
    union = set()
    for s in reversed(sets):
        s.append(union)
        union = union | s[0]
    return count_uniq_combs(sets, 0, frozenset(), dict())

print count(['a', 'abcd', 'be', 'fga'])

它打印出它实际计算的值（而不是从缓存中调用），如下所示：

^{pr2}$

例如，当查看列表2（“b”、“e”）时，只计算了两个计数：一个是排除“a”和“b”，另一个是只排除“a”。比较一下这个简单的实现，在这个实现中，您还需要计算许多其他的组合（例如：“a”和“c”）。在

如果仍然不够快，您可以尝试启发式排序列表：您希望稍后出现包含相对较少其他列表符号的列表。在