algorithm - 要素を比較せずにすべての辞書順列を生成する

Question

特定のシーケンス s=(a,b,c,d,e...) があるときに問題が発生しました-減少しない順序でソートされています。私の仕事は、可能なすべての順列を辞書式順序で生成するアルゴリズムを開発することです-逆の s (順序が最も高い) で終了します。

トリックは次のとおりです。2つの要素を互いに比較することはできません。要素の値に関係なく、すべての操作は「自動的に」実行する必要があります。

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)