4

我正在寻找一个函数的帮助，该函数接受一个字符串，并以各种方式替换该字符串中的每个字符。我不太确定如何表达我的问题以使其有意义，因此我将向您展示它应该做什么。

stars('1')
returns ['*']

stars('12')
returns ['*1', '1*', '**']

stars('123')
returns ['*23', '1*3', '12*', '**3', '*2*', '**1', '***']

stars('1234')
returns ['*234', '1*34', '12*4', '123*', '**34', '*2*4', '*23*', '1**4', '1*3*', 
         '12**', '***4', '**3*', '*2**', '1***', '****']

这一切都是手工完成的，但即使我犯了一个错误，你也应该知道我现在在寻找什么。最后一个案例（所有 * 的）不是必需的，但我把它放在那里以确保问题被理解。

到目前为止，这是我想出的，但它并不完全奏效。

def stars(n):
    lst = []
    length = len(n)
    for j in xrange(0, length):
        p = list(n)
        for k in xrange(j, length):
            p[k] = '*'
            lst += [''.join(p)]
    return lst

输出：

'1' returns ['*']
'12' returns ['*2', '**', '1*']
'123' returns ['*23', '**3', '***', '1*3', '1**', '12*']
'1234' returns ['*234', '**34', '***4', '****', '1*34', '1**4', '1***', '12*4', '12**', '123*']

任何帮助将不胜感激。如果可能的话，希望用 Python 回答这个问题，但如果您不了解 Python，那么伪代码或其他语言也是可以接受的。如果写得很清楚，我相信我可以自己将它转换成 Python。

4

4 回答 4

8

我认为 Python 中的规范方法是使用该itertools模块：

>>> from itertools import product, cycle
>>> s = 'abcde'
>>> [''.join(chars) for chars in product(*zip(s, cycle('*')))]
['abcde', 'abcd*', 'abc*e', 'abc**', 'ab*de', 'ab*d*', 'ab**e', 'ab***', 
 'a*cde', 'a*cd*', 'a*c*e', 'a*c**', 'a**de', 'a**d*', 'a***e', 'a****', 
 '*bcde', '*bcd*', '*bc*e', '*bc**', '*b*de', '*b*d*', '*b**e', '*b***',
 '**cde', '**cd*', '**c*e', '**c**', '***de', '***d*', '****e', '*****']

然后你可以只扔第一个没有任何星星，但这似乎有点神奇。

如果您不想使用内置的笛卡尔积函数，ISTM 还有另外两种方法：您可以使用递归，或者您可以利用您想要打开和关闭每颗星的事实，即二进制开关。这意味着对于n字母，您将有 2^n（-1，如果您删除无星号的情况）返回的可能性，并且是否在某处放置星号对应于是否设置了数字中的相应位（例如，对于“abc”，您将从 1 循环到 7（含），1 = 001 所以你会在最后一个地方放一颗星，7 = 111 所以你会在任何地方放一颗星，等等）

最后一个很容易实现，所以我把它留给你。:^)

于 2012-11-07T17:41:15.313 回答
2

您可以将其视为查找和迭代原始字符串中所有字符子序列的问题。（对于每个子序列，将其中的字符替换为 '*'，其余部分不理会）。

对于给定的子序列，每个字符要么在其中，要么不在其中，因此对于 N 个字符的字符串，有 2^N 个子序列。可能最简单的迭代它们的方法是迭代从 0 到 (2^N)-1 的整数，并使用它们的二进制表示作为字符是否应该被替换的指示

对于 N=3，它看起来像这样：

0  000 abc
1  001 ab*
2  010 a*c
3  011 a**
4  100 *bc
5  101 *b*
6  110 **c
7  111 ***

在 Python 中，你可以这样做：

def stars(input):
    l = len(input)
    for i in xrange(2**l):
        yield ''.join([('*' if i&(2**(l-pos-1)) else ch) for pos, ch in enumerate(input)])

试试看：

>>> print list(stars('abc'))
['abc', 'ab*', 'a*c', 'a**', '*bc', '*b*', '**c', '***']
于 2012-11-07T17:53:00.517 回答
1

这是一种使用方法combinations：

from itertools import combinations
def stars(str):
    N,L = len(str), []
    for k in range(0,N+1):
        for com in combinations(range(N),k):
            S = list(str)
            for x in com: S[x] = '*'
            L.append(''.join(S))
    return L

试试看：

>>> stars('abc')
['abc', '*bc', 'a*c', 'ab*', '**c', '*b*', 'a**', '***']
>>> stars('1234')
['1234', '*234', '1*34', '12*4', '123*', '**34', '*2*4', '*23*', '1**4', '1*3*', '12**', '***4', '**3*', '*2**', '1***', '****']
于 2012-11-07T18:29:39.563 回答
0

或特定于 Python 请参阅此功能：http ://docs.python.org/2/library/itertools.html#itertools.combinations

于 2012-11-07T17:33:08.160 回答