使用旋转和交换对二维环形阵列进行排序

Question

我尝试过一种算法，但无法做到这一点。这里是问题：

有16个元素，按四种类型（a，b，c和d）分组。我们也有四组，A，B，C和D.

在初始状态下，四组各有4个随机元件，例如：

A: c, c, a, d 
B: b, b, a, a 
C: b, b, c, c 
D: d, d, d, a 

元素组成的组中的顺序重大。

有允许两个操作：

1）旋转所述组的（）交换的基团中两个相邻元件与相应的元素在两个方向上），例如：

c, c, a, d -> d, c, c, a 

2在相邻的组的元素，考虑到第一个和最后组和元件也相邻，所以：

A: (c, c), a, d 
B: (b, b), a, a 

-> 

A: (b, b), a, d 
B: (c, c), a, a 

或

A: c), c, a, (d 
D: d), d, d, (a 

-> 

A: d), c, a, (a 
D: c), d, d, (d 

该算法的目标是将元素放入其相应的组（A: a, a, a, a等）。该算法不必在时间和解决方案方面达到最优，但它的平均速度应该相当快（即没有蛮力）。

任何人都可以帮忙吗？这个算法是多项式吗？

Answer 1

我认为这总是可能的。首先考虑一个字母（比如b）只出现在两行X和Y的情况。我们可以通过交换操作确保X和Y相邻。

情况下，我）

X: b - - - 
Y: - b b b 

我们可以通过

Cyclich转变X.

X: - - b - 
Y: - b b b 

掉期中间

X: - b b - 
Y: - - b b 

现在循环移位和交换使X的所有B的。

案例二）

X: b - b - 
Y: b - b - 

使其

X: - b - b 
Y: b - b - 

交换最后两个。

另一种情况是微不足道的。

现在给出2,3或4行中特定字母的任何分布，我们可以确保它只出现在两行中。我会把它留给你，因为它很容易看到，很难打字！

（如果只出现在一排，我们的工作主要是为信做）

这样的算法将是

确保只出现在两行。确保行是A和B（稍后交换）。

现在执行上面的步骤使A成为aaaa。

忽略A.

考虑B，C，D。确保b只出现在两行中。使B如上所述是bbbb。

忽略B.

鉴于C和d，您可以使用上面使C是CCCC，d将dddd完整。

Answer 2

我最初的想法是尝试某种形式的动态编程 - 这个问题看起来与Edit Distance比较相似，因为您拥有一组有限的操作和一个已知的期望结束状态。动态编程方法会产生多时间算法。但是，正如我所说，这正是我开始寻找算法的地方，我不知道这种方法是否真的有效。如果一段时间后我会有更深的思考。

希望这有助于！