4

有许多算法可以生成给定值集的所有可能排列。通常，这些值表示为一个数组，它具有 O(1) 随机访问。

但是，假设要置换的元素表示为双向链表。在这种情况下，您无法在 O(1) 时间内随机访问列表中的元素，因此许多排列算法将经历不必要的减速。

是否有一种算法可以以尽可能少的时间和空间开销生成链表的所有可能排列？

4

4 回答 4

4

试着想想你是如何在一张纸上生成所有排列的。

你从最右边的数字开始，向左移动一个位置，直到你看到一个比它的邻居小的数字。然后将下一个值的数字放在那里，并在其后按升序排列所有剩余的数字。这样做，直到没有更多事情可做。稍微考虑一下，您可以根据它们的数量在线性时间内对数字进行排序。

据我所知，这实际上是用于下一个排列的典型算法。我看不出为什么这在数组上会比在列表上更快。

于 2013-01-10T20:58:59.873 回答
2

您可能想研究Steinhaus-Johnson-Trotter 算法。它仅通过交换相邻元素来生成序列的所有排列；您可以在双向链表中在 O(1) 中执行的操作。

于 2013-01-10T21:33:02.267 回答
1

您应该将链表的数据读入一个数组，O(n)然后使用堆的排列 ( http://www.geekviewpoint.com/java/numbers/permutation ) 来查找所有排列。

于 2013-01-11T03:28:36.917 回答
0

您可以使用Factoradic Permutation Algorithm，并相应地重新排列节点指针以在不递归的情况下生成结果排列。

伪描述：

element_to_permute = list
temp_list = new empty list
for i = 1 in n! 
   indexes[] = factoradic(i)
   for j in indexes[]
      rearrange pointers of node `indexes[j]` of `element_to_permute` in `temp_list`
于 2013-01-10T21:50:33.470 回答