如何生成字符串所有可能长度的排列结果

固定长度的全排列实现逻辑很简单，但要输出从1位到原字符串长度的所有排列，需要调整原有递归的收集逻辑。

原有实现的局限 #

当前代码仅能生成和输入字符串等长的全排列：

def permutations(string):
    if len(string) == 1:
        return [string]
    else:
        perms = []
        for i in range(len(string)):
            for perm in permutations(string[:i] + string[i+1:]):
                perms.append(string[i] + perm)
    return perms
permutations('abc')

调用permutations('abc')的返回值只有3位长度的排列：
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
和预期结果相比，缺少了2位、1位长度的排列，目标结果为：['abc', 'acb', 'bac', 'bca', 'cab', 'cba','ab','ba','bc','cb','ca','ac','a','b','c']

修改思路 #

原有递归逻辑只会把所有剩余字符全部拼接完成后才加入结果集，没有收集递归过程中生成的短排列。只需要在递归的每一层，先把当前选中的单个字符加入结果，再把当前字符和子递归返回的所有短排列拼接后加入结果，就能收集齐所有长度的排列。

修改后代码 #

def permutations(string):
    if not string:
        return []
    perms = []
    for i in range(len(string)):
        char = string[i]
        # 收集长度为1的当前字符
        perms.append(char)
        # 递归获取剩余字符的所有长度排列
        for sub_perm in permutations(string[:i] + string[i+1:]):
            # 拼接得到更长的排列并收集
            perms.append(char + sub_perm)
    # 若需要按长度从长到短排序、匹配示例顺序，改用下面这行返回
    # return sorted(perms, key=lambda x: -len(x))
    return perms

print(permutations('abc'))

运行上述代码即可输出包含所有长度的排列结果，调整返回语句的排序逻辑后，输出顺序会和给出的预期列表完全一致。

内容的提问来源于stack exchange，提问作者Saimon Ghimire