如何获取列表中没有连续重复字符的元素的排列数

Question

我想要一组没有连续重复字符的数字的排列数。

如果我有一个输入为(['1', '2', '3'])的函数number_of_permutations，我希望它返回6，因为它的排列都没有连续重复的字符。

123，132，213中，231中，312，321

但如果我有参数(['1', '4', '1'])，我希望它返回2，因为只有两个排列没有连续重复的字符。

141中，141

如何在python中使用递归实现这一点？

Answer 1

如果我们可以放弃recursion作为需求，则可以使用itertools.permutations和O(n(循环来解决此问题。复杂性与计算所有排列保持不变，并且等于优化算法的最坏情况。

from typing import Iterator
import itertools

def number_of_permutations(possibilities: list) -> Iterator:
for potential in itertools.permutations(possibilities):
for i, c in enumerate(potential):
try:
if c == potential[i+1]:
break 
except IndexError:
yield potential