假設有長度爲n，其中包含字母A的列表 - 炭（N）。我想找到每個字母只能相鄰移動或保持原位的排列組合。因此，每個seq有三個「set」排列，循環到左側，循環到右側（列表被認爲是循環的）和原始列表。我無法提出一個算法來處理列表中間可能的交換。主要是，如何配對字母交換可以跳過字母。 例：排列置換爲列表，其中n = 3 [ABC，CAB，BCA，ACB，CBA，BAC] 此外，ABC和CAB被認爲是，儘管有相對於彼此相同的位置中的元素是唯一的。主要尋找算法，而不是任何特定的語言。 基本規則是這些元素最多可以離開它在列表中的原始位置1個位置。功能，以產生具有限於1個相鄰的移動元件序列的排列
除去I指數我將繪製的有效枚舉策略。
首先，讓我們來解決簡單的問題在沒有環繞。最左邊的元素有兩種可能性。要麼保持原狀或者向右移動。如果它向右移動，那麼它所移動的元素必須向左移動。我們可以遞歸地列舉剩餘置換的可能性。
# this code is for the simpler problem, without wraparound
# the algorithm for the problem with wraparound is described in prose below
def perms_line(lst, j):
if len(lst) - j < 2:
print(lst)
else:
perms_line(lst, j + 1)
lst[j], lst[j + 1] = lst[j + 1], lst[j]
perms_line(lst, j + 2)
lst[j], lst[j + 1] = lst[j + 1], lst[j]
perms_line([1, 2, 3, 4, 5], 0)
現在讓我們考慮環繞。如果兩個連續的元素向右移動，那麼每個元素都必須向右移動。如果連續兩個元素向左移動，則每個元素都必須向左移動。分開處理這些特殊的排列。
首先，考慮到最左邊的元素。要麼保持放置，要麼將元素與其右側交換，要麼與最右側的元素交換。對於這三種可能性中的每一種（注意：如果n = 2，則爲兩個，如果n = 1，則只有一個），對排列的其餘部分使用no-wraparound枚舉策略。我會繼續編寫代碼，因爲它需要一些小工具才能正確使用。
[2,3,4,5,1]也是有效的（參見原始問題下的註釋）。 – 2014-10-09 02:29:15
@גלעדברקן這是一個特殊的排列組合。 – 2014-10-09 02:29:54
哦，對不起，我只是試過你的代碼，沒有列出它。 – 2014-10-09 02:30:48
確定新的方法：
function(String begin,String end)
function(begin + ch, newString)下一封可用的信件是什麼意思？例如，第一次循環/遞歸運行，不會輸出「a」x n？（如果n = 3，則爲「aaa」） – johnidel127 2014-10-09 01:06:15
好吧，即使對我來說，現在看起來還不清楚。編輯。 – 2014-10-09 01:15:31
好吧，讓我們說n = 3。首先運行列表是ABC，在第一次遞歸調用之後，列表應該是AB還是BC？或者有些不同？ – johnidel127 2014-10-09 01:24:23
如果我正確理解您的問題，就需要找到能夠通過選擇非重疊的組相鄰的對和交換每對中的兩個元素來生成一個圓形序列的所有排列。
相鄰的一對可以通過在所述一對的第一個元素被唯一地識別;如果不包括兩個連續的元素，則一組相鄰的對是不重疊的。如果沒有圓度方面，這只是斐波那契數編碼：非相鄰元件的集合（NA）可以遞歸如下產生：
NA({a1,a2,…,an}, T) = NA({a2,a3,…,an}, T)
⋃ NA({a3,a4,…,an}, T ⋃ {a1})
NA({a}, T) = { T ⋃ {a} }
NA({}, T) = { T }
應當清楚，有fibonacci(n + 1)套在最終的結果，因爲NA（n）的計數是NA（n-1）和NA（n-2）的計數之和。
要佔到圓，我們通過排除最後一個元素限制初始情況下，如果我們選擇第一種：
CNA({a1,a2,…,an}) = NA({a2,a3,…,an}, {})
⋃ NA({a3,a4,…,an-1}, {a1})
因爲這只是在NA來定義，我們可以看到的數CNA的設置是fibonacci(n) + fibonacci(n - 2)。
你可以舉一個例子，這個例子可能來自'n = 4'嗎？ – 2014-10-09 00:49:55
無效排列可能是CBAD，因爲C無法到達位置1，因爲它只能向左或向右移動1個位置。 – johnidel127 2014-10-09 01:02:02
允許多少次相鄰交換來構造一個排列？ – 2014-10-09 01:17:03