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 回答