Python 计算唯一列表排列的可能性

Question

所以我在处理 lists/strings 的排列时遇到了问题，我很难解决。

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

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

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

所以我需要从我的列表中计算唯一字符组合的所有可能组合。希望每个人都能得到我在这里的要求。或者，如果可能的话，我什至不需要创建排列列表，我只需要计算总共有 HOW MANY 组合。由于实际问题中可能有大量单独的列表，因此内存占用较少

为了更详细地回答我的问题...如果我有两个列表：列表 1 = ["a"] 列表 2 = ["b"]

只有一种组合，因为您保留了置换字符串中的位置。列表 1 不包含 b，因此唯一的组合可能是 ("a","b")，而不是 ("b","a")。并进一步扩展这个问题的限制..我不一定要检索所有排列的结果，我只想 return 可能的 TOTAL NUMBER排列。返回结果会占用太多内存，因为我将处理大约 15 个列表，每个列表包含 1 到 15 个字符。

Answer 1

使用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 2

使用itertools.product to generate all possible combinations from the lists. Then, using itertools.ifilter，过滤掉所有包含重复字符的组合。一种简单的方法是检查列表的长度是否保持不变，如果你删除所有重复项（即如果你从中创建一个集合）。

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 3

您可以缓存 "starting from the i'th list, excluding elements in 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'])

它打印出它实际计算的值（而不是从缓存中调用），看起来像这样：

(3, frozenset(['a'])) 2
(2, frozenset(['a'])) 4
(2, frozenset(['a', 'b'])) 2
(1, frozenset(['a'])) 10
(0, frozenset([])) 10

例如，当查看列表 2 ("b"、"e") 时，只计算了两个计数：一个 "a" 和 "b" 都被排除在外，并且只有 "a" 被排除在外的一个。将此与您还计算许多其他组合（例如："a" 和 "c"）的天真实现进行比较。

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

Python 计算唯一列表排列的可能性

Python Calculating Unique List Permutation Possibilities

python

algorithm

list

unique

permutation