生成字符串列表及其子字符串排列的算法

Question

这个算法已经逃避我一段时间了。假设我得到了字符串“cccaatt”。我正在尝试生成每个重复字母子串的所有可能变体。EG，“cccaatt”作为输入将返回：

猫，猫猫，猫猫，猫猫，猫猫，猫猫，猫猫，猫猫，猫猫，猫猫，猫猫，猫猫，猫猫

结果的顺序无关紧要，只要它返回所有结果即可。一般输入是一个字符串，由g组重复字母组成，每组k_n个字母长。

我的直觉是这是一个递归算法，但它的确切结构很难理解。

Answer 1

将字符串分解为数字和重复次数的列表，即“cccaatt” => [(c,3), (a,2), (t,2)]。那么问题就可以递归地定义。

Let xs = [(a_1, n_1), (a_2, n_2), (a_3, n_3), ... (a_k, n_k)]
define Perm(xs):
    if len(xs) == 1:
        return all length variations of xs
    else:
        return every sequence in Perm(x[:-1]) appended with one or more from x[-1]

我很快就会有一个 python 示例。

Let xs = [(a_1, n_1), (a_2, n_2), (a_3, n_3), ... (a_k, n_k)]
define Perm(xs):
    if len(xs) == 1:
        return all length variations of xs
    else:
        return every sequence in Perm(x[:-1]) appended with one or more from x[-1]

附代码

> perm("cccaatt")
> ['cat', 'ccat', 'cccat', 'caat', 'ccaat', 'cccaat', 'catt', 'ccatt', 'cccatt', 'caatt', 'ccaatt', 'cccaatt']