1

我试着想一个算法,但做不到。这是问题所在:

有 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等)。该算法在时间和解决方案方面不必是最优的,但平均而言它应该相当快(即没有蛮力)。

任何人都可以帮忙吗?这个算法甚至是多项式的吗?

4

2 回答 2

4

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

案例一)

X: b - - -
Y: - b b 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。

于 2010-08-10T16:43:57.183 回答
1

我最初的想法是尝试某种形式的动态编程——这个问题似乎与编辑距离比较相似,因为你有一组有限的操作和一个已知的期望结束状态。动态规划方法将产生多时间算法。但是,就像我说的,这只是我开始寻找算法的地方,我不知道这种方法是否真的有效。如果以后有时间,我会进行更深入的思考。

希望这可以帮助!

于 2010-08-10T12:10:05.153 回答