algorithm - 修改堆的算法以生成排列

Question

Heap 的算法是一种系统的方法，可以循环遍历 N 个元素的所有排列“一次交换一次”。对于奇数 N，它特别简洁，因为最终排列似乎只是与第一个排列不同的一次交换。

但是，即使是 N，这种环绕也不会发生。例如，对于 N=4，排列顺序为：

那么，有没有人有一个交换算法可以环绕 N 呢？如果不是，那么仅 N=4 怎么样？

score 2 · Accepted Answer

通过检查，满足约束的一种可能序列是：

在每个步骤中，应该只交换两个元素。

对于较大的 NI，建议您尝试实现Steinhaus-Johnson-Trotter 算法，我相信该算法仅使用相邻元素的交换来生成这些排列，并且会让您与初始位置有一个交换。

基于Rosetta 代码的 Python 代码：

N=4
def s_permutations(seq):
    def s_perm(seq):
        if not seq:
            return [[]]
        else:
            new_items = []
            for i, item in enumerate(s_perm(seq[:-1])):
                if i % 2:
                    new_items += [item[:i] + seq[-1:] + item[i:]
                                  for i in range(len(item) + 1)]
                else:
                    new_items += [item[:i] + seq[-1:] + item[i:]
                                  for i in range(len(item), -1, -1)]
            return new_items

    return [(tuple(item), -1 if i % 2 else 1)
            for i, item in enumerate(s_perm(seq))]

for x,sgn in s_permutations(range(1,N+1)):
    print ''.join(map(str,x))

score 1 · Accepted Answer

对于一个固定的小数，例如 N=4，您可以预先计算数组索引的所有排列，并使用索引的每个排列遍历数据以得出数据的所有排列，例如伪代码

originalData[] = { 1111, 2222, 3333, 4444 }
indexPermuations[0] = { 0, 1, 2, 3 }
indexPermuations[1] = { 0, 1, 3, 2 }
// Etc for all 16 permutations of 4 indices

foreach (ip in indexPermutations) 
{
    for (i = 0 to 3)
    {
        dataPermuation[ip][i] = originalData[indexPermutation[ip][i]];
    }
}

algorithm - 修改堆的算法以生成排列

2 回答 2

Related

Reference