排列维持某些元素的顺序

Question

寻找一个实现,Python但我可以翻译任何东西.

如果我有string "cats ",这就是cat后跟四个空格的单词,我怎样才能找到维持单词cat顺序的所有可能的排列.那就是我不是在寻找任何排列,其中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