找到一個序列，使k正好在它之間有k個數字

我試圖在Google上搜索它，但找不到任何相關鏈接。如果提到這個問題，就足夠了。找到一個序列，使k正好在它之間有k個數字

2n數字，從1到n兩次的每個數字將被安排在一個序列中，使得數字k恰好在它之間有k個數字。有沒有可能爲任何n找到這樣的安排？對於某些n來說，找到這樣的序列可能是一種通用策略。

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

我發現他們只是通過命中和試驗，但未能找到對於n = 5和6。

來源

2012-10-15 Shashwat Kumar

k是已知的，或者您需要搜索任何數量？ – Anshu

這似乎不是一個編程問題。建議移動到math.stackexchange.com –

我認爲N = 1沒有解決方案？你有號碼1，2，2，沒有解決方案？ – Alan

請參閱此處http://en.wikipedia.org/wiki/Langford_pairing瞭解更多信息。特別是：「只有當n與0或3模4一致時才存在Langford配對;例如，當n = 1,2或5時，不存在Langford配對。」意味着你對n = 5和n = 6運氣不佳。

有關給定n的解決方案數目，請參閱http://oeis.org/A014552。

來源

2012-10-15 08:53:48 Henrik

感謝您的鏈接。我很驚訝甚至有一個相關的術語。 –

存在用於任意Ñ沒有這樣的序列可以很容易地通過窮舉搜索Ñ 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有很多解決方案，但詳盡的搜索需要幾分鐘的時間。

來源

2012-10-15 09:03:33

找到一個序列，使k正好在它之間有k個數字

回答

相關問題