具有特定强度的下一个排列/排序 [英] Next permutation/ranking with specific strength

问题描述

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

I am searching an algorithm which gives me the next permutation with a specific strength. A permutation of length n is defined with the elements (1,2,3,...n)

排列的强度是什么?

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

The strength of a permutation with length 10 is definded as |a1-a2|+|a2-a3|+...+|a9-a10|+|a10-a1|.

例如:

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

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

是否存在一个公式来计算给定强度和长度的下一个排列，还是必须计算所有元素?

Exist there a formula to compute the next permutation of a given strength and length, or its necesary to compute all elements?

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

Is ranking/unranking of the subsets possible?

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

The next permutation function should return the next lexicographical permutation within the subset defined by the given strength and length and without compute the intermediate permutations different strengths.

推荐答案

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

This is a nicely masked problem in combinatorics. First, note that this is a ring of integers; the linear "array" is an implementation choice, rather than part of the strength analysis. Let's look at the second case, given as (1,2,6,3,4,5):

  1
5   2
4   6
  3

每个元素都以正好两个术语出现.因此，我们对元素进行了简单的线性组合，系数为-2，02.如果元素大于两个邻居(例如5)，则系数为2；如果元素大于两个邻居，则系数为2.如果小于两个邻居(例如1)，则为-2；如果介于两者之间，则两个abs操作将取消，并且为0(例如4).

Every element appears in exactly two terms. Thus, we have a simple linear combination of the elements, with coefficients of -2, 0 2. If the element is larger than both neighbors (e.g. 5), the coefficient is 2; if smaller than both neighbors (e.g. 1), it's -2; if between, the two abs operations cancel, and it's 0 (e.g. 4).

引理:强度必须为偶数.

Lemma: the strength must be an even number.

因此，求和与某些变换可以通过简单的分析就足够容易地进行检查.最大的数字始终具有+2的系数；最小的系数始终为-2.

Thus, the summation and some transformations can be examined easily enough with simple analysis. The largest number always has a coefficient of +2; the smallest always has a coefficient of -2.

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

You can find "close relative" permutations by finding interchangeable elements. For instance, you can always interchange the largest two elements (6 and 5) and/or the smallest two elements (1 and 2), without affecting the strength. For instance, 6 and 5 can be interchanged because they're strictly larger than their neighbors:

(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可以互换，即使它们是相邻的，也有类似的原因……除了只有三个术语，其中一个涉及该对:

1 and 2 can be interchanged, even though they're adjacent, for a similar reason ... except that there are only three terms, one of which involves the pair:

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

---

取决于数字集的分布，可能会有更直接的方法来构造具有给定强度的环.由于尚未在排列中定义顺序，因此我们无法确定下一个".但是，简单的一点是要注意，给定排列的旋转和反射将具有相同的强度:

---

Depending on the distribution of the set of numbers, there will likely be more direct ways to construct a ring with a given strength. Since we do not yet have an ordering defined on the permutations, we have no way to determine a "next" one. However, the simple one is to note that rotations and reflections of a given permutation will all have the same strength:

(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更新:

Addition w.r.t. OP updates:

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

There are several trivially strength-invariant swaps available. I've already mentioned the two extreme pairs (6-5) and (1-2). You can also swap adjacent, consecutive numbers: that adds (4-5) and (3-4) in the above example. From simple algebraic properties, you can often identify a 2-element swap or 3-element rotation (respecting an increase in lexicographic position) that generates the next desired permutation. For instance:

(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

但是，以这种方式很难找到顺序的中断.例如，大胆地更改第一个或第二个元素并不是那么干净:

However, there are irruptions in the sequence that you'd be hard-pressed to find in this fashion. For instance, making the leap to change the first or second element is not so clean:

(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).但是，遵循这些规则通常要比处理所有排列花费更多的时间.

I feel that finding these would require a set of algebraic rules that would find the simple moves and eliminate invalid moves (such as generating 563421 before the "wholesale rearrangement" just above). However, following these rules would often take more time than working through all permutations.

我很想发现我在这最后一点上是错的. :-)

I'd love to find that I'm wrong on this last point. :-)

这篇关于具有特定强度的下一个排列/排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！