python - 替换字符串列表中的字符并创造所有可能性

Question

嘿，我在我的代码中遇到了一个新问题。有一次我有一个看起来像这个的列表。 (通常更长，但这对理解问题并不重要)

['-0---11-', '--1--110', '01---100', '1--101-0', '10-1-1-0']

在带有条形的位置可以是 0 或 1。现在我想知道列表代表了多少只剩下 3 个条形的唯一字符串。在上面的示例中，最后三个字符串已经只有三个小节，但前两个字符串有四个和五个小节。 '-0---11-'因此可以表示 '-0--1111','-0--1110','000--11-',.... 所以我的想法基本上是先创造出所有的可能性，然后寻找独特的，这样才不会多算。我现在的问题是如何创造所有可能性？

编辑:另一个更简单的例子可能会澄清我的问题。假设列表看起来像:

['--11', '--10', '010-']

现在我想看看当我最多只有 1 个柱时我有多少个独特的字符串。每个条代表一个 1 或 0，所以我必须写下所有的可能性。结果将是:

['-111', '-011', '0-11', '1-11',  '-010', '-110', '0-10', '1-10',   '010-']

我希望我没有忘记任何可能性。现在我必须搜索重复项并想删除它们。在这个例子中没有任何东西，所以我完成了。

Answer 1

你可以使用这样的递归解决方案

def possibilities(pattern, ndash=0):
    if ndash <= pattern.count('-'):
        if not pattern:
            yield ''
        else:
            if pattern[0] == '-' and ndash > 0:
                for subpattern in possibilities(pattern[1:], ndash - 1):
                    yield '-' + subpattern
            for subpattern in possibilities(pattern[1:], ndash):
                if pattern[0] in '0-':
                    yield '0' + subpattern
                if pattern[0] in '1-':
                    yield '1' + subpattern

这是一个生成器函数，因此为了从中获取值，您需要遍历生成器。

>>> gen = possibilities('1----0', 3)
>>> for s in gen:
...     print s

或者您可以将它提供给 list 以获得所有可能性的列表。

>>> from pprint import pprint
>>> pprint(list(possibilities('1----0', 3)
['1---00',
 '1---10',
 '1--0-0',
 '1--1-0',
 '1-0--0',
 '1-1--0',
 '10---0',
 '11---0']