4

我有一个问题是约瑟夫斯问题变体。描述如下：

有 m 张卡片，编号从 1 到 m，每张卡片都有一个唯一的编号。卡片分发给围成一圈的 n 个人。请注意m >= n。

然后我们选择坐在位置“p”的人“A”离开圆圈，就像约瑟夫斯问题一样。下一步，我们跳过 p 右边的“k”个人，而 k 是“A”个人拿到的牌的编号，我们做同样的事情，直到圈子里只剩下一个人。

问题给定n个人和m张卡片，我们是否可以选择n张卡片分配给第n个人，使得无论从哪个位置开始（不包括第一个位置），最后生存的人总是第一个圆圈。

例如，m = n = 5，唯一的解是 (4, 1, 5, 3, 2)。

我认为这个问题是一个 np-complete 问题，但我无法证明。任何人都有一个好主意来找到多项式时间解决方案或证明它是 np-hard 吗？

--- 示例解决方案 ---

 2: [ 1,  2]
 2: [ 2,  1]
 3: [ 1,  3,  2]
 3: [ 3,  1,  2]
 4: [ 4,  1,  3,  2]
 5: [ 4,  1,  5,  3,  2]
 7: [ 5,  7,  3,  1,  6,  4,  2]
 9: [ 2,  7,  3,  9,  1,  6,  8,  5,  4]
 9: [ 3,  1,  2,  7,  6,  5,  9,  4,  8]
 9: [ 3,  5,  1,  8,  9,  6,  7,  4,  2]
 9: [ 3,  9,  2,  7,  6,  1,  5,  4,  8]
 9: [ 6,  1,  8,  3,  7,  9,  4,  5,  2]
10: [ 3,  5,  6, 10,  1,  9,  8,  7,  4,  2]
10: [ 4,  5,  2,  8,  7, 10,  6,  1,  9,  3]
10: [ 5,  1,  9,  2, 10,  3,  7,  6,  8,  4]
10: [ 6,  3,  1, 10,  9,  8,  7,  4,  5,  2]
10: [ 8,  5,  9, 10,  1,  7,  2,  6,  4,  3]
10: [10,  5,  2,  1,  8,  7,  6,  9,  3,  4]
11: [ 2,  1, 10, 11,  9,  3,  7,  5,  6,  8,  4]
11: [ 3,  7, 11, 10,  9,  8,  1,  6,  5,  4,  2]
11: [ 3, 11, 10,  9,  8,  1,  7,  2,  4,  5,  6]
11: [ 4,  1, 10,  2,  9,  8,  7,  5, 11,  3,  6]
11: [ 4,  2,  7, 11,  5,  1, 10,  9,  6,  3,  8]
11: [ 4,  7,  2,  3,  1, 10,  9,  6, 11,  5,  8]
11: [ 4,  7,  3,  9, 11, 10,  1,  8,  6,  5,  2]
11: [ 4, 11,  7,  2,  1, 10,  9,  6,  5,  3,  8]
11: [ 5, 11,  3,  9,  8,  7,  6,  1, 10,  4,  2]
11: [ 6,  1, 10,  2,  9,  8,  7,  5, 11,  3,  4]
11: [ 6,  2,  7, 11,  5,  1, 10,  9,  4,  3,  8]
11: [ 6, 11,  1,  3, 10,  2,  7,  5,  4,  9,  8]
11: [ 9,  5,  3,  1, 10,  2,  8,  7, 11,  6,  4]
12: [ 1,  7, 11, 10,  4,  9,  2, 12,  6,  5,  8,  3]
12: [ 3,  7, 12,  2, 11, 10,  9,  1,  6,  5,  4,  8]
12: [ 3,  8, 11,  2, 12,  9,  1,  7,  5, 10,  4,  6]
12: [ 4,  2,  5,  1, 11, 10,  9,  8, 12,  7,  3,  6]
12: [ 4,  3,  7,  6,  1, 11, 10,  9,  8, 12,  5,  2]
12: [ 5,  1,  6, 11,  9,  2, 10,  7, 12,  8,  3,  4]
12: [ 5,  2,  3, 12,  9, 10,  7,  6,  1, 11,  4,  8]
12: [ 5,  7, 12,  2, 10,  9,  8, 11,  1,  4,  6,  3]
12: [ 7,  1,  2,  3,  5,  9, 10,  8, 11,  6, 12,  4]
12: [ 8,  7,  1, 11,  9,  3,  5, 10,  6,  4, 12,  2]
12: [ 8,  7, 11, 10, 12,  3,  1,  9,  6,  5,  4,  2]
12: [12,  3, 11,  5,  1, 10,  8,  7,  6,  4,  9,  2]
12: [12,  7, 11,  1,  9,  3,  2, 10,  6,  5,  4,  8]
13: [ 2,  1,  4,  7, 11,  6,  3, 10, 13,  5,  8, 12,  9]
13: [ 2,  5, 13, 12,  4, 11,  3,  1,  9,  7,  8,  6, 10]
13: [ 2, 13, 12, 11,  3,  1,  9,  4,  8,  7, 10,  5,  6]
13: [ 3,  5,  2,  1, 12,  9, 11, 10,  7,  6, 13,  4,  8]
13: [ 3,  5, 13,  1, 11,  2,  9,  8,  7, 12,  6,  4, 10]
13: [ 4, 13,  3,  1, 12, 11, 10,  9,  7,  2,  5,  6,  8]
13: [ 6,  4,  3,  1, 10, 11, 13,  5,  9, 12,  7,  8,  2]
13: [ 6,  4, 13,  7,  5,  1, 12, 11, 10,  9,  8,  3,  2]
13: [ 6,  7,  3, 13, 12, 11, 10,  2,  1,  9,  5,  4,  8]
13: [ 6,  7, 13, 11,  2, 10,  9,  1,  8, 12,  5,  3,  4]
13: [ 6, 11,  7, 13,  1, 10,  2, 12,  9,  8,  5,  4,  3]
13: [ 7,  3,  2,  1, 11, 10,  9,  8, 13,  5, 12,  4,  6]
13: [ 7,  5, 13,  3, 10, 11,  2,  9,  1,  6,  8,  4, 12]
13: [ 7,  5, 13,  3, 11,  2,  9,  8,  1,  6, 12,  4, 10]
13: [ 7,  5, 13,  3, 11, 12,  2,  1,  9,  8,  6,  4, 10]
13: [ 7,  9,  1, 11,  3, 13,  2, 10, 12,  6,  5,  4,  8]
13: [ 8,  3,  5, 11, 13,  9, 10,  7,  1,  6,  4, 12,  2]
13: [ 8,  3, 13,  1,  5, 11, 10,  9, 12,  7,  6,  4,  2]
13: [ 9,  3, 13,  2, 10,  4,  1,  7,  6,  5, 12, 11,  8]
13: [ 9,  4,  7,  5,  1, 11, 13, 10, 12,  8,  6,  3,  2]
13: [ 9,  5,  4, 13,  2, 11,  8, 10,  1,  7, 12,  3,  6]
13: [ 9,  5, 13,  4, 11,  1,  8,  3,  7, 12,  6, 10,  2]
13: [10,  4,  3,  5, 13,  1,  9, 11,  7,  6,  8, 12,  2]
13: [11,  2,  7,  3, 12,  1, 10,  9,  6,  5, 13,  4,  8]
13: [11, 13,  5,  2, 10,  9,  8,  7,  1,  6,  4,  3, 12]
13: [11, 13,  7,  1, 12,  9,  2,  3, 10,  5,  4,  6,  8]
13: [12,  1,  3,  5, 11, 13,  4, 10,  9,  8,  7,  6,  2]
13: [12,  7, 13,  3, 11,  1,  9,  8,  6,  5, 10,  4,  2]
13: [12, 13,  7, 11,  2,  5,  1,  9, 10,  6,  4,  3,  8]
13: [13,  3,  1, 12, 11,  2,  9, 10,  7,  6,  4,  5,  8]
13: [13,  3,  7,  1,  5, 12,  4, 10,  9,  8, 11,  6,  2]
14: [ 3,  5, 13, 14,  1, 12, 11, 10,  9,  8,  7,  6,  4,  2]
14: [ 3,  9,  1, 13, 11, 10,  2,  4,  7, 14,  6,  8,  5, 12]
14: [ 3, 14,  4, 12, 11,  1,  9,  8,  2, 13,  7,  5, 10,  6]
14: [ 4, 11,  1, 13,  7, 10, 12,  2, 14,  9,  8,  5,  6,  3]
14: [ 4, 14,  2,  5, 13,  1, 12, 11,  7,  6, 10,  9,  3,  8]
14: [ 5,  7,  1, 13, 12, 11, 10,  2,  9,  8, 14,  6,  4,  3]
14: [ 6,  3, 14,  5, 11, 13,  2, 12,  9,  1,  7,  4,  8, 10]
14: [ 6, 14,  1, 12,  5, 13,  2, 11,  9,  7,  8,  4,  3, 10]
14: [ 7,  5, 13, 12,  1, 11,  4, 10,  2, 14,  9,  8,  6,  3]
14: [ 7, 11,  5, 13,  1,  3,  2,  4, 10,  9, 14,  6,  8, 12]
14: [ 7, 14,  1, 13,  2,  5, 11, 12, 10,  9,  8,  4,  3,  6]
14: [ 8,  7,  5, 13,  2, 11,  3,  9, 10, 12,  1, 14,  4,  6]
14: [11,  2, 10,  5,  8,  7,  9,  1, 13, 14, 12,  4,  3,  6]
14: [11,  3, 14,  2, 13,  1, 10,  8,  9,  7,  5, 12,  4,  6]
14: [11,  5,  3, 14,  2,  1, 13, 10,  8,  7,  6, 12,  4,  9]
14: [11, 14,  5,  3, 13,  1, 10,  2,  9,  4,  7,  8, 12,  6]
14: [12,  1, 14,  3, 13,  4, 10,  9,  2,  7,  6,  5, 11,  8]
14: [12, 11,  7,  5, 13,  3,  2, 14,  1,  9,  8,  4,  6, 10]
14: [12, 14,  7, 13,  6,  5, 11,  1, 10,  9,  8,  4,  3,  2]
14: [13,  1,  7,  2, 11,  3,  9, 14,  8,  6,  5, 10,  4, 12]
14: [13, 11,  3,  1,  4,  2,  7, 10,  9,  6, 14, 12,  5,  8]
14: [14,  1, 13,  3, 11,  5, 10,  9,  2,  6,  8,  7,  4, 12]
14: [14, 5, 1, 13, 12, 2, 11, 3, 7, 9, 6, 8, 4, 10]

--- 可能对数学解决方案有帮助 --- 我注意到从长度 9 开始，每个长度的至少一个解决方案都有一个较长的整数序列，该序列减 1。

 9: [3,  1,  2,                               7, 6, 5,    9, 4, 8]  
10: [6,  3,  1,                     10, 9, 8, 7,          4, 5, 2] 
11: [3,  7,                     11, 10, 9, 8,             1, 6, 5, 4, 2]
11: [3,                         11, 10, 9, 8,             1, 7, 2, 4, 5, 6]
11: [5, 11,  3,                         9, 8, 7, 6,       1, 10, 4, 2]
12: [4,  2,  5,  1,             11, 10, 9, 8,            12, 7, 3, 6] 
12: [4,  3,  7,  6, 1,          11, 10, 9, 8,            12, 5, 2] 
13: [6,  4, 13,  7, 5, 1,   12, 11, 10, 9, 8,             3, 2]
14: [3,  5, 13, 14, 1,      12, 11, 10, 9, 8, 7, 6,       4, 2]
4

1 回答 1

2

我注意到，对于我测试的每个长度，除了非常小的长度之外，至少有一个解决方案包含相对较长的递减数字。到目前为止，这个答案只考虑 m = n。这里有一些例子; 请注意，多余的是 n - run_len：

n = 3, run_len = 2, excess = 1: [1] + [3-2] + []
n = 4, run_len = 2, excess = 2: [4, 1] + [3-2] + []
n = 5, run_len = 2, excess = 3: [4, 1, 5] + [3-2] + []
n = 6, no solution
n = 7, run_len = 1, excess = 6: [5] + [7-7] + [3, 1, 6, 4, 2]
n = 8, no solution
n = 9, run_len = 3, excess = 6: [3, 1, 2] + [7-5] + [9, 4, 8]
n = 10, run_len = 4, excess = 6: [6, 3, 1] + [10-7] + [4, 5, 2]
n = 11, run_len = 4, excess = 7: [3, 7] + [11-8] + [1, 6, 5, 4, 2]
n = 12, run_len = 4, excess = 8: [4, 2, 5, 1] + [11-8] + [12, 7, 3, 6]
n = 13, run_len = 5, excess = 8: [6, 4, 13, 7, 5, 1] + [12-8] + [3, 2]
n = 14, run_len = 7, excess = 7: [3, 5, 13, 14, 1] + [12-6] + [4, 2]
n = 15, run_len = 8, excess = 7: [3, 15, 2] + [13-6] + [1, 5, 4, 14]
n = 16, run_len = 6, excess = 10: [6, 3, 1, 10] + [16-11] + [2, 9, 7, 4, 5, 8]
n = 17, run_len = 8, excess = 9: [2, 5, 17, 15, 14, 1] + [13-6] + [4, 3, 16]
n = 18, run_len = 10, excess = 8: [6, 3, 17, 18, 1] + [16-7] + [5, 4, 2]
n = 19, run_len = 10, excess = 9: [4, 19, 3, 17, 18, 1] + [16-7] + [5, 6, 2]
n = 20, no solution found with run_length >= 10
n = 21, run_len = 14, excess = 7: [3, 21, 2] + [19-6] + [1, 5, 4, 20]
n = 22, run_len = 14, excess = 8: [22, 3, 2, 1] + [20-7] + [5, 21, 4, 6]
n = 23, run_len = 14, excess = 9: [7, 1, 23, 3] + [21-8] + [6, 5, 22, 4, 2]
n = 24, run_len = 16, excess = 8: [6, 5, 24, 2] + [22-7] + [3, 1, 23, 4]
n = 25, run_len = 17, excess = 8: [25, 3, 2, 1] + [23-7] + [5, 24, 4, 6]
n = 26, run_len = 17, excess = 9: [26, 3, 25, 2, 1] + [23-7] + [5, 24, 4, 6]
n = 27, run_len = 20, excess = 7: [3, 27, 2] + [25-6] + [1, 5, 4, 26]
n = 28, run_len = 18, excess = 10: [28, 1, 27, 2, 3] + [25-8] + [6, 5, 7, 4, 26]
n = 29, run_len = 20, excess = 9: [2, 5, 29, 27, 26, 1] + [25-6] + [4, 3, 28]
n = 30, run_len = 23, excess = 7: [30, 5, 2, 1] + [28-6] + [29, 3, 4]
n = 31, run_len = 24, excess = 7: [5, 31, 3] + [29-6] + [1, 30, 4, 2]
n = 32, run_len = 23, excess = 9: [7, 32, 31, 2, 1] + [30-8] + [5, 4, 3, 6]
n = 33, run_len = 26, excess = 7: [3, 33, 2] + [31-6] + [1, 5, 4, 32]
n = 34, run_len = 27, excess = 7: [3, 5, 33, 34, 1] + [32-6] + [4, 2]
n = 35, run_len = 27, excess = 8: [5, 35, 3, 33, 34, 1] + [32-6] + [4, 2]
n = 36, run_len = 26, excess = 10: [35, 7, 3, 1, 36, 2] + [34-9] + [6, 5, 4, 8]
n = 37, run_len = 29, excess = 8: [6, 5, 2, 1] + [35-7] + [36, 37, 3, 4]
n = 38, run_len = 29, excess = 9: [3, 7, 37, 38, 1] + [36-8] + [6, 4, 5, 2]
n = 39, run_len = 32, excess = 7: [3, 39, 2] + [37-6] + [1, 5, 4, 38]
n = 40, run_len = 31, excess = 9: [5, 2, 1] + [38-8] + [3, 7, 40, 4, 6, 39]
n = 41, run_len = 33, excess = 8: [3, 5, 1, 40, 2] + [38-6] + [41, 39, 4]
n = 42, run_len = 33, excess = 9: [42, 3, 41, 2, 1] + [39-7] + [5, 4, 40, 6]
n = 43, run_len = 34, excess = 9: [6, 5, 7, 43, 1] + [41-8] + [42, 4, 3, 2]
n = 44, run_len = 35, excess = 9: [5, 3, 2, 1] + [42-8] + [43, 7, 4, 44, 6]
n = 45, run_len = 38, excess = 7: [3, 45, 2] + [43-6] + [1, 5, 4, 44]
n = 50, run_len = 43, excess = 7: [50, 5, 2, 1] + [48-6] + [49, 3, 4]
n = 100, run_len = 91, excess = 9: [5, 2, 1] + [98-8] + [3, 7, 100, 4, 6, 99]
n = 201, run_len = 194, excess = 7: [3, 201, 2] + [199-6] + [1, 5, 4, 200]

上表中缺少 20，因为运行长度最多为 10，并且需要很长时间来计算。我测试过的较大值相对于 n 没有如此小的最大运行长度。

我通过检查从 n-1 降序的运行长度，以及运行和周围元素的所有可能的起始值和排列来找到这些。这极大地减少了搜索空间。

对于给定的 n，如果 n 的任何解决方案中的最大运行长度为 nk，那么这将在 O(k! * n) 中找到它。虽然这看起来很严峻，但如果 k 有一个恒定的上限（例如 k <= 对于所有足够大的 n 的某个阈值），那么这实际上是 O(n)。在上面的例子中，“多余”就是我所说的 k。我没有找到任何大于 10 的值，但我还没有 n = 20 的解决方案。如果它有一个解决方案，那么它的过剩将超过 10。

更新：这里有很多模式。

如果 n mod 6 为 3 且 n >= 9，则 [3, n, 2, [n-2, n-3, ..., 6], 1, 5, 4, n-1] 有效。

如果 n mod 12 是 5 并且 n >= 17 那么 [2, 5, n, n-2, n-3, 1, [n-4, n-5, ..., 6], 4, 3, n -1] 是有效的。

如果 n mod 20 为 10，则 [n, 5, 2, 1, [n-2, n-3, ..., 6], n-1, 3, 4] 有效。

如果 n mod 60 为 7、11、31 或 47，则 [5, n, 3, [n-2, n-3, ..., 6], 1, n-1, 4, 2] 有效.

如果 n mod 60 是 6 或 18 并且 n >= 18 那么 [6, 3, n-1, n, 1, [n-2, n-3, ..., 7], 5, 4, 2] 是有效的。

如果 n mod 60 是 1, 22, 25 或 52 并且 n >= 22 那么 [n, 3, 2, 1], [n-2, n-3, ..., 7], 5, n-1, 4, 6] 有效。

如果 n mod 60 为 23，则 [7, 1, n, 3, [n-2, n-3, ..., 8], 6, 5, n-1, 4, 2] 有效。

如果 n mod 60 为 14 或 34，则 [3, 5, n-1, n, 1, [n-2, n-3, ..., 6], 4, 2] 有效。

如果 n mod 60 为 24，则 [6, 5, n, 2, [n-2, n-1, ..., 7], 3, 1, n-1, 4] 有效

如果 n mod 60 是 2, 6, 26, 42 并且 n >= 26 那么 [n, 3, n-1, 2, 1, [n-3, n-4, ..., 7], 5, n -2, 4, 6] 是有效的。

如果 n mod 60 为 16 或 28，则 [n, 1, n-1, 2, 3, [n-3, n-4, ..., 8], 6, 5, 7, 4, n-2]已验证。

如果 n mod 60 为 32，则 [7, n, n-1, 2, 1, [n-2, n-3, ..., 8], 5, 4, 3, 6] 有效。

如果 n mod 60 为 35 或 47，则 [5, n, 3, n-2, n-1, 1, [n-3, n-4, ..., 6], 4, 2] 有效。

如果 n mod 60 为 37，则 [6, 5, 2, 1, [n-2, n-1, ..., 7], n-1, n, 3, 4]

如果 n mod 60 为 38，则 [3, 7, n-1, n, 1] + [n-2, n-3, ..., 8] + [6, 4, 5, 2]

如果 n mod 60 为 40，则 [5, 2, 1, [n-2, n-3, ..., 8], 3, 7, n, 4, 6, n-1] 有效

如果 n mod 60 为 0 且 n >= 60 则 [3, 5, n, 2, [n-2, n-3, ..., 7], 1, 6, n-1, 4] 有效

如果 n mod 60 为 7、19 或 31 且 n >= 19，则 [4, n, 3, n-2, n-1, 1, [n-3, n-4, ..., 7], 5, 6, 2] 有效

如果 n mod 60 是 23、38 或 43，则 [7, 3, n, 1, [n-2, n-3, ..., 8], 6, 5, n-1, 4, 2] 是一个有效的解决方案

如果 n mod 60 是 14 或 44 并且 n >= 74 那么 [3, 5, n-1, n, 1, [n-3, n-4, ..., 6], n-2, 4, 2 ] 已验证。

如果 n mod 60 是 1 或 49 并且 n >= 49 那么 [3, 5, n, 1, [n-2, n-3, ..., 7], 2, n-1, 4, 6] 是有效的。

如果 n mod 60 为 6、18、30、42 或 54 且 n >= 18 则 [n, 3, n-1, 2, 1, [n-3, n-4, ..., 7], 5, 4, n-2, 6] 是有效的。

如果 n mod 60 是 10, 18, 38 或 58 并且 n >= 18 则 [n-1, 7, 5, n, 1, [n-2, n-3, ..., 8], 2, 6 , 4, 3] 是有效的。

目前解决的 n mod 60 是以下任何值：

 0,  1,  2,  3,      5,  6,  7,      9, 
10, 11,         14, 15, 16, 17, 18, 19,
    21, 22, 23, 24, 25, 26, 27, 28, 29, 
30, 31, 32, 33, 34, 35,     37, 38, 39, 
40, 41, 42, 43, 44, 45,     47,     49,
50, 51, 52, 53, 54,         57, 58

还，

如果 n mod 42 为 31，则 [n, 3, 2, 1, [n-2, n-3, ..., 8], n-1, 5, 4, 7, 6] 有效。

如果 n mod 420 为 36 或 396，则 [n-1, 7, 3, 1, n, 2, [n-2, n-3, ..., 9], 6, 5, 4, 8] 有效.

--- n=21 的示例，使用上面列出的第一个模式和所有起始索引。

1:  [21,  2, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
2:  [ 2, 18, 21, 16, 19, 14, 17, 12, 15, 10, 13,  8, 11, 6, 9, 5, 1,  4, 20,  7]
3:  [19, 21, 18,  2, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
4:  [18, 21, 19, 17,  2, 15, 16, 13, 14, 11, 12,  9, 10, 7, 8, 1, 5,  4, 20,  6]
5:  [17, 21, 19, 18, 16,  2, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
6:  [16, 21, 19, 18, 17, 15,  2, 13, 14, 11, 12,  9, 10, 7, 8, 1, 5,  4, 20,  6]
7:  [15, 21, 19, 18, 17, 16, 14,  2, 12, 13, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
8:  [14, 21, 19, 18, 17, 16, 15, 13,  2, 11, 12,  9, 10, 7, 8, 1, 5,  4, 20,  6]
9:  [13, 21, 19, 18, 17, 16, 15, 14, 12,  2, 10, 11,  8, 9, 6, 7, 5,  4, 20,  1]
10: [12, 21, 19, 18, 17, 16, 15, 14, 13, 11,  2,  9, 10, 7, 8, 1, 5,  4, 20,  6]
11: [11, 21, 19, 18, 17, 16, 15, 14, 13, 12, 10,  2,  8, 9, 6, 7, 5,  4, 20,  1]
12: [10, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11,  9,  2, 7, 8, 1, 5,  4, 20,  6]
13: [ 9, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  8, 2, 6, 7, 5,  4, 20,  1]
14: [ 8, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 7, 2, 1, 5,  4, 20,  6]
15: [ 7, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 6, 2, 5,  4, 20,  1]
16: [ 6, 21, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 7, 1, 5,  4, 20,  2]
17: [ 1,  5,  2, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 7, 6, 4, 19, 20, 21]
18: [ 5,  2, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 4,  1, 20, 21]
19: [ 4,  2, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11,  8, 9, 6, 7, 5, 20, 21,  1]
20: [20,  4, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10,  9, 8, 7, 6, 1,  5, 21,  2]

对于该模式适用的所有 n 值，您可以观察到递减运行中的元素与其他元素之间的相同关系。这不是一个证明，但你可以把它变成一个证明，尽管我认为需要为每个模式分别完成工作，这超出了我将花费时间进行 S/O 的范围问题。

--- 我们可以用 m > n 来填空。---

模式 [n-1, n, 1, [n-2, n-3, ..., 3], n+5] 对 n mod 4 为 1 且 n >= 9 有效。

模式 [n, 2, 1, [n-2, n-3, ..., 3], n+4] 对 n mod 2 为 0 且 n >= 6 有效。

有了这两个，再加上我们已经找到的，我们几乎得到了一切。我通过检查有限范围内的单个替换值找到了这些。

 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 
40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54,     56, 57, 58

如果 n mod 30 是 29，那么 [3, n, 2, [n-2, n-3, ..., 4], n-1, n+15) 是有效的，给我们 n mod 60 是 59。我们只剩下一个未知数：n mod 60 是 55。

……最后！如果 n mod 12 为 7（即 n mod 60 为 7、19、31、43 或 55），则 [n-1, n, 1, [n-2, n-3, ..., 6], 2 , 5, 3, n+4] 对所有 n >= 19 都有效。

我们现在有了所有 n mod 60 的解决方案，在大多数情况下使用 m=n，在最坏的情况下使用 m=n+15。

于 2021-07-16T20:43:35.437 回答