在 Python
中寻找实现,但我可能可以从任何东西中进行翻译。
如果我有 string
"cats "
,它是单词cats 后跟四个空格,我怎样才能找到所有可能的排列 来保持单词cats 的顺序。也就是说,我不是在寻找 a 是第一个实际字母或 t 等的任何排列,而是寻找 cats
中字母之间的所有可能的空格排列。
一些例子:
"cats "
"c ats "
" cat s"
"c a t s "
" c a t s"
最佳答案
这是一个解决方案,而不是算法 :) 该算法隐藏在 itertools.combinations
的实现中(但请参阅下面的没有内置库函数的实现)。
from functools import reduce
from itertools import combinations
def assign(v, p):
v[p[0]] = p[1]
return v
def interp(word, letter, size):
return (''.join(reduce(assign, zip(comb, word), [letter] * size))
for comb in combinations(range(size), len(word)))
示例(使用点代替空格使它们更明显):
>>> print('\n'.join(interp("cats", ".", 6)))
cats..
cat.s.
cat..s
ca.ts.
ca.t.s
ca..ts
c.ats.
c.at.s
c.a.ts
c..ats
.cats.
.cat.s
.ca.ts
.c.ats
..cats
实现
combinations
实际上很容易(但是为什么要麻烦,因为它已经定义了?)。这是一个解决方案,它执行过多的元组连接而无法提高效率,但演示了该算法:def combs(vec, count, start=0):
if count == 0:
yield ()
else:
for i in range(start, len(vec) + 1 - count):
for c in combs(vec, count - 1, i + 1):
yield((i,) + c)
换句话说,对于每个可能的第一个位置,选择那个位置并完成与剩余位置的组合。同样,您可以直接实现所需的功能:
def interp(word, letter, size):
if len(word) == 0:
yield letter * size
else:
for i in range(size + 1 - len(word)):
for comb in interp(word[1:], letter, size - i - 1):
yield letter * i + word[0] + comb
关于python - 排列保持某些元素的顺序,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/42081799/