sequence - 找到一个序列，使得 k 之间恰好有 k 个数字

Question

我试图在谷歌上搜索它，但找不到任何相关链接。如果对这个问题有任何参考，那就足够了。

2n 个数字，每个数字从 1 到 n 两次，将按顺序排列，使得数字 k 之间恰好有 k 个数字。是否有可能为任何 n 找到这样的安排？什么可以是为一些 n 找到这样的序列的一般策略。

例如，
n = 3 --> 231213
n = 4 --> 41312432

我只是通过点击和试验找到了它们，但无法找到 n = 5 和 6。

Answer 1

请参阅此处http://en.wikipedia.org/wiki/Langford_pairing了解更多信息。特别是：“朗福德配对仅在 n 与 0 或 3 模 4 一致时存在；例如，当 n = 1、2 或 5 时，不存在朗福德配对。” 意味着您在 n = 5 和 n = 6 时运气不佳。

有关给定 n 的解决方案数量，请参见http://oeis.org/A014552 。

Answer 2

不存在任意n的这样的序列，可以通过对n 2、5 或 6的详尽搜索轻松验证：

def check(t, n): 
  for i in range(1, n + 1): 
    p1 = t.index(i)
    p2 = t.index(i, p1 + 1)
    if p2 - p1 != i + 1:
      return False
  return True

assert check((2, 3, 1, 2, 1, 3), 3)
assert check((4, 1, 3, 1, 2, 4, 3, 2), 4)

def allseqs(n):
  if n > 1:
    for seq in allseqs(n - 1): 
      for i in range(len(seq) + 1): 
        for j in range(i, len(seq) + 1): 
          yield seq[:i] + (n,) + seq[i:j] + (n,) + seq[j:]
  else:
    if n == 1:
      yield (1, 1)
    else:
      yield ()

def findseqs(n):
  for p in allseqs(n):
    if check(p, n): 
      print p

n=2, 3, 4, 5 的结果：

>>> findseqs(2)
>>> findseqs(3)
(2, 3, 1, 2, 1, 3)
(3, 1, 2, 1, 3, 2)
>>> findseqs(4)
(2, 3, 4, 2, 1, 3, 1, 4)
(4, 1, 3, 1, 2, 4, 3, 2)
>>> findseqs(5)
>>> findseqs(6)
>>> 

n=7 有很多解决方案，但详尽的搜索需要几分钟。