数组元素排列的算法

Question

考虑以下情况:

我有一个数字数组:

 [ 1,2,3,4 ]

如果把这个数组连接起来，我会得到数字1234。

我想交换数字以获得最接近的较高数字。 1234将变成1243，然后是1324，再是1342等等。 我需要使用什么算法在数组中进行这些更改？ 理想情况下，我想以以下方式使用该算法：（假设Array有这个算法作为名为walkthrough的函数）

 [ 1,2,3,4].walkthrough() # gives [ 1, 2, 4, 3 ]
 [ 1,2,4,3].walkthrough() # gives [ 1, 3, 2, 4 ]

---

数字列表如下：

1234
1243
1324
1342
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241

以上是一组排列组合的数字列表。

- Stefan

---

请继续这个数字序列。在1342之后，我猜应该是1432，然后呢？4132，然后4312，最后4321？ - Lasse V. Karlsen

我认为你的列表中有一个错误，2413不应该在2341之后吗？ - AShelly

是的...谢谢...它已经被修复了。 - Stefan

Answer 1

这将为您提供下一个排列：

bool Increase(int[] values) {
   // locate the last item which is smaller than the following item
   int pos = values.Length - 2;
   while (pos >= 0 && values[pos] > values[pos + 1]) pos--;
   // if not found we are done
   if (pos == -1) return false;
   // locate the item next higher in value
   int pos2 = values.Length - 1;
   while (values[pos2] < values[pos]) pos2--;
   // put the higher value in that position
   int temp = values[pos];
   values[pos] = values[pos2];
   values[pos2] = temp;
   // reverse the values to the right
   Array.Reverse(values, pos + 1, values.Length - pos - 1);
   return true;
}

编辑：
将Array.Sort更改为Array.Reverse。项目始终按降序排列，应按升序排列，以便产生相同的结果。

- Guffa

---

你有Ruby中相当于Array.Sort部分的等效代码吗？ - Stefan

@Stefan：我从未使用过Ruby，所以不知道。这个Array.Sort方法的重载会对从第二个参数指定的索引开始，长度为第三个参数的数组部分进行排序。 - Guffa

@paracycle：谢谢。是的，这是C#。我刚刚发明了它，或者可能是重新发明了它... :) - Guffa

说起来，对于数组的部分排序，一个替代方案是简单地将其反转。项目始终会按降序排列，之后应该按升序排列。 - Guffa

Answer 2

这似乎是想以字典顺序生成列表的排列。这些搜索词应该让您走上有用的道路。

例如，Python2.6版本起在itertools模块中包含了此功能。该文档显示实现此算法的代码。

- Phil Miller