我试着想一个算法,但做不到。这是问题所在:
有 16 个元素,按四种类型(a、b、c 和 d)分组。我们也有四个组,A、B、C 和 D。
在初始状态下,四组各有四个随机元素,例如:
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
等)。该算法在时间和解决方案方面不必是最优的,但平均而言它应该相当快(即没有蛮力)。
任何人都可以帮忙吗?这个算法甚至是多项式的吗?