arrays - 具有特定强度的下一个排列/排名

Question

我正在寻找一种算法，该算法可以为我提供具有特定强度的下一个排列。长度为 n 的排列由元素 (1,2,3,...n) 定义

排列的强度是多少？

长度为 10 的排列的强度定义为 |a1-a2|+|a2-a3|+...+|a9-a10|+|a10-a1|。

例如:

(1,2,3,4,5,6) 强度 10

(1,2,6,3,4,5) 强度 14

是否存在计算给定强度和长度的下一个排列的公式，或者计算所有元素所必需的公式？

是否可以对子集进行排名/取消排名？

下一个排列函数应该返回给定强度和长度定义的子集中的下一个字典排列，而不计算中间排列不同的强度。

Answer 1

这是组合学中一个很好的掩蔽问题。首先，请注意这是一个整数环；线性“阵列”是一种实现选择，而不是强度分析的一部分。让我们看看第二种情况，以 (1,2,6,3,4,5) 形式给出:

  1
5   2
4   6
  3

每个元素恰好出现在两个术语中。因此，我们有一个元素的简单线性组合，系数为 -2、0 2。如果元素大于两个相邻元素(例如 5)，则系数为 2;如果小于两个邻居(例如 1)，则为 -2；如果介于两者之间，则两个 abs 操作取消，并且它是 0(例如 4)。

引理:强度必须是偶数。

因此，可以通过简单的分析很容易地检查求和和一些变换。最大数的系数总是+2；最小的总是具有 -2 的系数。

您可以通过查找可互换的元素来找到“近亲”排列。例如，您可以始终交换最大的两个元素(6 和 5)和/或最小的两个元素(1 和 2)，而不影响强度。例如，6 和 5 可以互换，因为它们严格大于它们的邻居:

(6-2) + (6-3) + (5-1) + (5-4) =
(5-2) + (5-3) + (6-1) + (6-4) =
2*6 + 2*5 - 2 - 3 - 1 - 4

1 和 2 可以互换，即使它们是相邻的，出于类似的原因......除了只有三个项，其中一个涉及对:

(5-1) + (2-1) + (6-2) =
(5-2) + (2-1) + (6-1) =
5 + 6 - 2*1

---

根据数字集的分布，可能会有更直接的方法来构建具有给定强度的环。由于我们还没有对排列定义排序，因此我们无法确定“下一个”排列。然而，简单的方法是注意给定排列的旋转和反射都具有相同的强度:

(1,2,6,3,4,5)
(2,6,3,4,5,1)
(6,3,4,5,1,2)
...
(5,4,3,6,2,1)
(4,3,6,2,1,5)
...

这会让你动起来吗？

---

添加 w.r.t.操作更新:

有几种简单的强度不变交换可用。我已经提到了两个极端对 (6-5) 和 (1-2)。您还可以交换相邻的连续数字:在上例中添加 (4-5) 和 (3-4)。从简单的代数属性，您通常可以识别生成下一个所需排列的 2 元素交换或 3 元素旋转(考虑到字典位置的增加)。例如:

(5, 6, 1, 3, 4, 2)
(5, 6, 1, 4, 2, 3)   rotate 3, 4, 2
(5, 6, 1, 4, 3, 2)   swap 2, 3

但是，您很难以这种方式找到序列中的中断。例如，改变第一个或第二个元素的飞跃并不是那么干净:

(5, 6, 3, 1, 4, 2)
(5, 6, 3, 2, 4, 1)   swap 1, 2 -- easy
(6, 1, 2, 4, 5, 3)   wholesale rearrangement --
                       hard to see that this is the next strength=14

我觉得找到这些需要一组代数规则来找到简单的着法并消除无效着法(例如在上面的“批发重排”之前生成 563421)。然而，遵循这些规则通常比处理所有排列花费更多时间。

我很乐意发现我在最后一点上是错的。 :-)