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

Question

我试着想出一种算法，但做不到。这是问题所在:

共有 16 个元素，按四种类型(a、b、c 和 d)分组。我们也有四个组，A、B、C 和 D。

在初始状态下，四组各有四个随机元素，eg.:

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

我们可以通过以下方式使 X 都是 b

循环移位 X。

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

交换中间

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

现在循环移位和交换。

情况二)

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

成功了

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

交换最后两个。

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

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

(如果它只出现在一行中，那么我们的工作大部分都针对该字母完成了)

因此算法将是

确保 a 只出现在两行中。确保行是 A 和 B(稍后交换)。

现在执行上面的操作使A成为aaaa。

忽略 A。

考虑 B、C、D。确保 b 仅出现在两行中。如上使B为bbbb。

忽略 B。

给定 C 和 D，您可以使用上面的方法使 C 成为 cccc，D 成为 dddd。