python - 维持某些元素顺序的排列

Question

正在寻找 Python 的实现，但我可能可以从任何东西进行翻译。

如果我有 string "cats "，即单词 cats 后跟四个空格，我如何找到所有可能的排列猫这个词的顺序。也就是说，我不是在寻找 a 是第一个实际字母或 t 等的任何排列，而是在 cats 中的字母之间的所有可能的空白排列。

一些例子:

"cats    "
"c ats   "
"  cat  s"
"c a t s "
" c a t s"

Answer 1

这是一个解决方案，而不是算法 :) 该算法隐藏在 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