使用递归按字典顺序打印字符串所有排列的Python程序

Question

学校的一项作业要求我按字典或字典顺序打印字符串的所有排列。

这是我对任务的解决方案-

from math import factorial

def print_permutations_lexicographic_order(s):

    seq = list(s)
    for _ in range(factorial(len(seq))):
        print(''.join(seq))
        nxt = get_next_permutation(seq)
        # if seq is the highest permutation
        if nxt is None:
            # then reverse it
            seq.reverse()
        else:
            seq = nxt

def get_next_permutation(seq):
    """
    Return next greater lexicographic permutation. Return None if cannot.

    This will return the next greater permutation of seq in lexicographic order. If seq is the highest permutation then this will return None.

    seq is a list.
    """
    if len(seq) == 0:
        return None

    nxt = get_next_permutation(seq[1:])

    # if seq[1:] is the highest permutation
    if nxt is None:
        # reverse seq[1:], so that seq[1:] now is in ascending order
        seq[1:] = reversed(seq[1:])

        # find q such that seq[q] is the smallest element in seq[1:] such that
        # seq[q] > seq[0]
        q = 1
        while q < len(seq) and seq[0] > seq[q]:
            q += 1

        # if cannot find q, then seq is the highest permutation
        if q == len(seq):
            return None

        # swap seq[0] and seq[q]
        seq[0], seq[q] = seq[q], seq[0]

        return seq
    else:
        return [seq[0]] + nxt


s = input('Enter the string: ')
print_permutations_lexicographic_order(s))

以下是一些输入/输出示例：

Enter the string: cow
>>> cow
    cwo
    ocw
    owc
    wco
    woc

Enter the string: dogs
>>> dogs
    dosg
    dsgo
    dsog
    gdos
    gdso
    gods
    gosd
    gsdo
    gsod
    odgs
    odsg
    ogds
    ogsd
    osdg
    osgd
    sdgo
    sdog
    sgdo
    sgod
    sodg
    sogd
    ogds
    ogsd

因此，我想知道我是否可以使我的程序更短，更有效率。

任何帮助都将不胜感激。

Answer 1

第三次，我将推荐您使用迭代工具模块：

正如我在另一个答案中所说的，您的代码是非常C/C++样式的，它不是Pythonic的。尽量避免使用索引进行手动迭代。Python有一个巨大的标准库，其中包含了许多有用的模块。我已经向您推荐了一个迭代工具模块。它包含一对用于迭代器的数十个泛型函数。其中一项--排列--完成了你90%的工作：

在第二次，我将向您推荐itertools.permutations函数，它可以用一行代码来解决问题：

from itertools import permutations

def get_lexicographic_permutations(s):
    return sorted(''.join(chars) for chars in permutations(s))

print(get_lexicographic_permutations('dogs'))

['dgos', 'dgso', 'dogs', 'dosg', 'dsgo', 'dsog', 'gdos', 'gdso', 'gods', 'gosd', 'gsdo', 'gsod', 'odgs', 'odsg', 'ogds', 'ogsd', 'osdg', 'osgd', 'sdgo', 'sdog', 'sgdo', 'sgod', 'sodg', 'sogd']

Answer 2

一种基本的递归思想是反复地将问题简化为同一类型的更简单的版本，直到达到不能再减少的基本情况为止。递归解决方案通常是“简单”的，因为不使用许多代码行，所以这是值得寻找的东西。

让我们看看如何将其应用于这个特定的问题。就拿“牛”这个词，加上排列

奶牛，cwo，ocw，owc，wco，woc

注意第一个字符是如何保持不变的，直到涵盖了所有的“尾”排列。这是您需要的简化步骤:对于字符串中的每个字符，使之成为第一个字符，然后使用其余的字符再次调用函数。跟踪字符选择顺序，因为这将是一个词。然后记住抓住大小写:如果字符串中没有剩下的字符，那么我们已经删除了字符，并且单词已经完成。

def lexperm(s, word=''):
    if not s:
        print(word)
    for i, char in enumerate(s):
        lexperm(s[:i] + s[i+1:], word + char)

请注意，这不需要交换或反转任何东西，因为我们正在按每个顺序删除所有字符。

Answer 3

我已经阅读了您过去的几个问题，我无法真正描述代码在不违反SE规则的情况下是多么的难看。

阅读并跟随PEP8。

跳过“愚蠢的一致性是小心灵的霍哥布林”一节，因为你似乎不知道好代码是什么样子，也不知道如何与遗留代码交互。现在最好是一个霍布林人，因为你会产生比现在更好的代码。

获得一些链接包装，如Flake8、探索者或考拉。确保打开所有警告，因为它们在默认情况下通常不会打开。

这些将帮助您了解代码的哪些部分很糟糕，而不必问其他人！

修复这些工具引发的所有错误有助于保持代码的整洁并使其变得更干净，因此当您生成更大的程序时，更容易理解您的代码所做的事情。你可以抗议，并说：“但人们在代码审查理解我的代码！”你是对的，但这是因为你在开发编码挑战的解决方案，而不是更复杂和需要更多代码的现实生活问题。