在不比较元素的情况下生成所有字典顺序排列

Question

当我有一个给定序列 s=(a,b,c,d,e...) - 按非递减顺序排序时，我遇到了问题。我的工作是开发一种算法，该算法将按字典顺序生成所有可能的排列 - 以反转的 s 结尾（最高顺序）。

诀窍是：我无法将任何 2 个元素相互比较。无论元素值如何，都必须完成所有操作 "automatically"。

Answer 1

你可以这样做：

// n is the number of elements in the given sequence
p = all permutations of [0, 1, ..., n - 1] in lexicographical order    
for permutation in p:  
        for i = 0 ... n - 1
            print(s[permutation[i]]) // s is the given sequence

您可以使用任何标准算法生成 [0, 1, ..., n - 1] 的所有排列（递归或从 {0, 1, ..., n - 1} 开始并生成下一个排列 n! - 1 次）。实际上，用于生成直接应用于给定序列的所有排列的标准递归算法将以正确的顺序生成它们（并且不需要比较元素）。

这里是递归算法的伪代码：

// Generates all permutations recursively
// permutation - a prefix of an arbitrary permutation
// sequence - the input sequence
// used - a boolean array where used[i] = true if and only if
// an element with index i is already in permutation
def generatePermutations(permutation, sequence, used)
    if permutation.length() == sequence.length()
        // The permutation is fully generated
        print(permutation)
    else
        // Adds all elements that are not present in permutation yet.
        // Starts with the smallest index to maintain the correct order.
        for i = 0 ... sequence.length() - 1
            if not used[i]
                used[i] = true
                permutation.push_back(sequence[i])
                generatePermutations(permutation, sequence, used)
                used[i] = false
                permutation.pop_back()

sequence = input()
permutation = an empty list
used = array of sequence.length() elements filled with a
generatePermutations(permutation, sequence, used)

在不比较元素的情况下生成所有字典顺序排列

Generating all lexicographical permutations without comparisons of elements

algorithm

permutation

discrete-mathematics

lexicographic