我尝试思考一种算法，但无法实现。问题是：
有 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
or
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 等）。该算法不必在时间和解决方案方面是最佳的，但平均而言应该相当快（即没有暴力）。
有人可以帮忙吗？这个算法是多项式吗？
I tried thinking of an algorithm, but couldn't do it. Here is the problem:
There are 16 elements, grouped by four types (a, b, c and d). We also have four groups, A, B, C and D.
In the initial state, the four groups have four random elements each, eg.:
A: c, c, a, d
B: b, b, a, a
C: b, b, c, c
D: d, d, d, a
The order of elements in the group is significant.
There are two operations permitted:
1) rotating the elements of the group (in both directions), eg.:
c, c, a, d -> d, c, c, a
2) swapping two adjacent elements in a group with the corresponding elements in an adjacent group, considering that the first and last groups and elements are also adjacent, so.:
A: (c, c), a, d
B: (b, b), a, a
->
A: (b, b), a, d
B: (c, c), a, a
or
A: c), c, a, (d
D: d), d, d, (a
->
A: d), c, a, (a
D: c), d, d, (d
The goal of the algorithm is to place the elements into their corresponding groups (A: a, a, a, a, etc.). The algorithm doesn't have to be optimal in terms of time and solution, but it should be reasonably fast on average (ie. no brute-force).
Can anyone help? Is this algorithm even polynomial?
发布评论
评论（2）
我认为这总是可能的。首先考虑字母（比如b）只出现在X和Y两行中的情况。我们可以通过交换操作确保X和Y相邻。
情况 i)
使 X 全部为 b
我们可以通过循环移位 X
。交换中间
现在循环移位和交换。
情况 ii)
使其
交换最后两个。
另一种情况是微不足道的。
现在，给定特定字母在 2,3 或 4 行中的任意分布，我们可以确保它仅出现在两行中。我将把它留给你，因为它很容易看到但很难打字！
（如果它只出现在一行中，我们的工作主要是针对该字母完成的）
因此算法将是
确保 a 只出现在两行中。确保行是 A 和 B（稍后交换）。
现在执行上面的操作，使 A 变为 aaaa。
忽略 A。
考虑 B、C、D。确保 b 仅出现在两行中。如上所述，使 B 为 bbbb。
忽略B。
给定C和D，您可以使用上面的内容使C成为cccc，D将成为dddd。
I think it is always possible. First consider the case when a letter (say b) appears only in two rows X and Y. We can ensure that X and Y are adjacent by the swap operations.
Case i)
We can make X all b's by
Cyclich shift X.
swap middle
Now cyclic shift and swap.
Case ii)
make it
Swap last two.
The other case is trivial.
Now given any distribution of a particular letter in 2,3 or 4 rows, we can ensure that it appears only in two rows. I will leave that to you, as it is easy to see and hard to type!
(If it appears only in one row, our work is mostly done for that letter)
Thus the algorithm would be
Ensure a appears only in two rows. Make sure the rows are A and B (by swapping later).
Now perform above to make A to be aaaa.
Ignore A.
Consider B,C,D. Ensure that b appears only in two rows. Make B to be bbbb as above.
Ignore B.
Given C and D, you can use the above to make C to be cccc, D will be dddd.
我最初的想法是尝试某种形式的动态编程 - 问题似乎与 编辑距离，因为您有一组有限的操作和已知的所需最终状态。动态规划方法将产生多时间算法。但是，就像我说的，这就是我开始寻找算法的地方，我不知道这种方法是否真的有效。如果我以后有时间的话，我会进行更深入的思考。
希望这有帮助！
My initial idea would be to attempt some form of Dynamic Programming - the problem seems relatively similar to Edit Distance in that you have a limited set of operations and a known desired end state. A dynamic programming approach would yield a poly-time algorithm. But, like I say, this is just where I would start searching for an algorithm, I don't know if this approach would actually work. If I get some time later I'll have a deeper think.
Hope this helps!