gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:59:51 25 4
gpt4 key购买 nike

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

诀窍是:我无法将任何 2 个元素相互比较。无论元素值如何,所有操作都必须“自动”完成。

最佳答案

你可以这样做:

// 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} 并生成下一个排列 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)

关于algorithm - 在不比较元素的情况下生成所有字典顺序排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27891575/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com