代码之家 › 专栏 › 技术社区 › Soyol

句子中词的递归排列

sentence permutation recursion python

1

Soyol · 技术社区 · 6 年前

我想 recursively 得到句子中单词的排列,将相邻单词分成两组,从左到右排列在一起。

作为一个例子,如果我考虑 a, B, c, D 是4个单词,主句中有5次出现这4个单词,如下所示:

主句: a + B + c + a + D

c + a + B + c + a
a + B + c + a + D
a + B + c + a + B
B + c + a + B + c

它们的长度都与主句相同,应该注意的是,主句中的最后一个词,即。 D 只出现一次,而且只出现在后面的句子末尾 a

2 回复 | 直到 6 年前

1

blhsing 6 年前

def adjacent_combinations(sentence, target=None, length=0):
    if not target:
        for target in set(sentence):
            for combination in adjacent_combinations(sentence, target, 1):
                yield combination
    elif length == len(sentence):
        yield [target]
    else:
        for a, b in set(zip(sentence, sentence[1:])):
            if a == target:
                for combination in adjacent_combinations(sentence, b, length + 1):
                    yield [a] + combination

以便:

list(adjacent_combinations(['a', 'B', 'c', 'a', 'D']))

将返回:

[['B', 'c', 'a', 'B', 'c'],
 ['c', 'a', 'B', 'c', 'a'],
 ['a', 'B', 'c', 'a', 'B'],
 ['a', 'B', 'c', 'a', 'D']]

2

1

Ajax1234 6 年前

可以使用带递归的生成器:

s = ['a', 'B', 'c', 'a', 'D']
def combinations(d, _c = []):
  if len(_c) == len(d)+1:
     yield _c
  else:
     for i in d:
       if not _c or any(s[c] == _c[-1] and s[c+1] == i for c in range(len(s)-1)):
          for k in combinations(d, _c+[i]):
            yield k

print('\n'.join(' + '.join(i) for i in combinations(set(s))))

输出:

a + B + c + a + B
a + B + c + a + D
B + c + a + B + c
c + a + B + c + a