问题描述
有许多算法可用于生成给定值集的所有可能排列.通常，这些值表示为一个数组，该数组具有 O(1) 随机访问.
There are many algorithms for generating all possible permutations of a given set of values. Typically, those values are represented as an array, which has O(1) random access.
然而，假设要置换的元素表示为双向链表.在这种情况下，您无法在 O(1) 时间内随机访问列表中的元素，因此许多排列算法将经历不必要的减速.
Suppose, however, that the elements to permute are represented as a doubly-linked list. In this case, you cannot randomly access elements in the list in O(1) time, so many permutation algorithms will experience an unnecessary slowdown.
是否有一种算法可以以尽可能少的时间和空间开销生成链表的所有可能排列?
Is there an algorithm for generating all possible permutations of a linked list with as little time and space overhead as possible?
推荐答案
试着想一想你是如何在一张纸上生成所有排列的.
Try to think of how you generate all permutations on a piece of paper.
您从最右边的数字开始，向左移动一个位置，直到您看到一个小于其邻居的数字.然后将值中的下一个数字放在那里，并在其后按升序排列所有剩余数字.这样做直到无事可做.稍微考虑一下，您可以在线性时间内对数字进行排序.
You start from the rightmost number and go one position to the left until you see a number that is smaller than its neighbour. Than you place there the number that is next in value, and order all the remaining numbers in increasing order after it. Do this until there is nothing more to do. Put a little thought in it and you can order the numbers in linear time with respect to their number.
据我所知，这实际上是用于下一次排列的典型算法.我看不出为什么这在数组上会比在列表上更快.
This in fact is the typical algorithm used for next permutation as far as I know. I see no reason why this would be faster on array than on list.
这篇关于有效地生成链表的所有可能排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！