功能，以产生具有限于1个相邻的移动元件序列的排列

假设有长度为n，其中包含字母A的列表 - 炭（N）。我想找到每个字母只能相邻移动或保持原位的排列组合。因此，每个seq有三个“set”排列，循环到左侧，循环到右侧（列表被认为是循环的）和原始列表。我无法提出一个算法来处理列表中间可能的交换。主要是，如何配对字母交换可以跳过字母。例：排列置换为列表，其中n = 3 [ABC，CAB，BCA，ACB，CBA，BAC] 此外，ABC和CAB被认为是，尽管有相对于彼此相同的位置中的元素是唯一的。主要寻找算法，而不是任何特定的语言。基本规则是这些元素最多可以离开它在列表中的原始位置1个位置。功能，以产生具有限于1个相邻的移动元件序列的排列

来源

2014-10-09 johnidel127

你可以举一个例子，这个例子可能来自'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

除去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枚举策略。我会继续编写代码，因为它需要一些小工具才能正确使用。

来源

2014-10-09 02:26:21

[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)

如果最终== 1的尺寸：打印开始+结束。
循环结束：
CH =端[I]
newString =从端
function(begin + ch, newString)

来源

2014-10-09 00:51:10

下一封可用的信件是什么意思？例如，第一次循环/递归运行，不会输出“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({a₁,a₂,…,a_n}, T) = NA({a₂,a₃,…,a_n}, T) 
         ⋃ NA({a₃,a₄,…,a_n}, T ⋃ {a₁}) 
NA({a}, T) = { T ⋃ {a} } 
NA({}, T) = { T }

应当清楚，有fibonacci(n + 1)套在最终的结果，因为NA（n）的计数是NA（n-1）和NA（n-2）的计数之和。

要占到圆，我们通过排除最后一个元素限制初始情况下，如果我们选择第一种：

CNA({a₁,a₂,…,a_n}) = NA({a₂,a₃,…,a_n}, {}) 
        ⋃ NA({a₃,a₄,…,a_n-1}, {a₁})

因为这只是在NA来定义，我们可以看到的数CNA的设置是fibonacci(n) + fibonacci(n - 2)。

来源

2014-10-09 02:48:38 rici

功能，以产生具有限于1个相邻的移动元件序列的排列

回答

相关问题