下一个 permutation/ranking 具有特定强度
Next permutation/ranking with specific strength
我正在搜索一种算法，该算法可以为我提供具有特定强度的下一个排列。
长度为 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
是否存在计算给定强度和长度的下一个排列的公式，或者计算所有元素所必需的公式？
ranking/unranking 个子集可能吗？
下一个排列函数应该 return 由给定强度和长度定义的子集中的下一个字典排列，而不计算中间排列不同的强度。
这是组合学中一个很好的掩蔽问题。首先，请注意这是一个整数环；线性 "array" 是一种实现选择，而不是强度分析的一部分。让我们看看第二种情况，给出 (1,2,6,3,4,5):
1
5 2
4 6
3
每个元素恰好出现在两个术语中。因此，我们有一个元素的简单线性组合，系数为 -2, 0 2。如果元素大于两个邻居（例如 5），则系数为 2；如果小于两个邻居（例如 1），则为 -2；如果介于两者之间，则两个 abs 操作取消，并且它是 0（例如 4）。
引理：强度必须是偶数。
因此，通过简单的分析就可以很容易地检查求和和一些变换。最大数的系数总是+2；最小的总是有-2的系数。
您可以通过查找可互换的元素来找到 "close relative" 排列。例如，您可以 always 交换最大的两个元素（6 和 5）and/or 最小的两个元素（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
根据数字集的分布，可能会有更直接的方法来构造具有给定强度的环。由于我们还没有对排列定义排序，因此我们无法确定 "next" 排列。然而，简单的是要注意给定排列的旋转和反射都具有相同的强度：
(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。 OP 更新：
有几个简单的 strength-invariant 交换可用。我已经提到了两个极端对 (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
但是，您会 hard-pressed 以这种方式找到序列中的中断。例如，改变第一个或第二个元素的飞跃并不是那么干净：
(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
我觉得找到这些需要一组代数规则来找到简单的走法并消除无效的走法（例如在上面的 "wholesale rearrangement" 之前生成 563421）。但是，遵循这些规则通常比完成所有排列需要 更多 时间。
我很乐意发现我在最后一点上是错的。 :-)
我正在搜索一种算法，该算法可以为我提供具有特定强度的下一个排列。 长度为 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
是否存在计算给定强度和长度的下一个排列的公式，或者计算所有元素所必需的公式？
ranking/unranking 个子集可能吗？
下一个排列函数应该 return 由给定强度和长度定义的子集中的下一个字典排列，而不计算中间排列不同的强度。
这是组合学中一个很好的掩蔽问题。首先，请注意这是一个整数环；线性 "array" 是一种实现选择，而不是强度分析的一部分。让我们看看第二种情况，给出 (1,2,6,3,4,5):
1
5 2
4 6
3
每个元素恰好出现在两个术语中。因此，我们有一个元素的简单线性组合，系数为 -2, 0 2。如果元素大于两个邻居（例如 5），则系数为 2；如果小于两个邻居（例如 1），则为 -2；如果介于两者之间，则两个 abs 操作取消，并且它是 0（例如 4）。
引理：强度必须是偶数。
因此，通过简单的分析就可以很容易地检查求和和一些变换。最大数的系数总是+2；最小的总是有-2的系数。
您可以通过查找可互换的元素来找到 "close relative" 排列。例如，您可以 always 交换最大的两个元素（6 和 5）and/or 最小的两个元素（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
根据数字集的分布，可能会有更直接的方法来构造具有给定强度的环。由于我们还没有对排列定义排序，因此我们无法确定 "next" 排列。然而，简单的是要注意给定排列的旋转和反射都具有相同的强度：
(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。 OP 更新：
有几个简单的 strength-invariant 交换可用。我已经提到了两个极端对 (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
但是，您会 hard-pressed 以这种方式找到序列中的中断。例如，改变第一个或第二个元素的飞跃并不是那么干净：
(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
我觉得找到这些需要一组代数规则来找到简单的走法并消除无效的走法（例如在上面的 "wholesale rearrangement" 之前生成 563421）。但是，遵循这些规则通常比完成所有排列需要 更多 时间。
我很乐意发现我在最后一点上是错的。 :-)