2

Googleで検索しようとしましたが、関連するリンクが見つかりませんでした。この問題への言及があれば、それで十分です。

2nの数、それぞれ1からnまでの2回の数は、数kがその間に正確にk個の数を持つように順番に配置されます。任意のnについてそのような配置を見つけることは可能ですか？いくつかのnのそのようなシーケンスを見つけるための一般的な戦略は何でしょうか。

たとえば、
n = 3-> 231213
n = 4-> 41312432

ヒットとトライアルだけで見つけましたが、n=5と6では見つかりませんでした。

4

2 に答える 2

1

n 2、5 、または 6の徹底的な検索によって簡単に検証できるような任意のnのシーケンスはありません。

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 にはかなりの数の解がありますが、徹底的な検索には数分かかります。

于 2012-10-15T09:03:33.910 に答える
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を参照してください。

于 2012-10-15T08:53:48.377 に答える