有趣的排序问题

Question

有一个,零和'U'按特定顺序排列.(例如"1001UU0011")1和0的数量是相同的,并且总是有两个'U'彼此相邻.您可以将这对'U'与任何一对相邻数字交换.这是一个示例移动:

      __
     /  \
1100UU0011 --> 11001100UU

任务是将所有零置于之前.

这是一个示例解决方案:

First step:
  __
 /  \
1100UU0011

Second step:
  ____
 /    \
UU00110011

000011UU11  --> DONE

创建一个强力算法非常容易.但是,就像我的例子一样,需要数百甚至数千个动作来解决一个简单的动作.所以我正在寻找更"聪明"的算法.

---

这不是功课; 这是比赛中的一项任务.比赛已经结束,但我无法找到解决方案.

编辑:这里的任务是创建一个算法,可以对那些0和1进行排序 - 而不仅仅是输出N 0和N 1和2 Us.你必须以某种方式显示步骤,就像在我的例子中一样.

编辑2:任务没有用最少的动作或类似的东西询问结果.但我个人希望看到一个算法提供:)

Answer 1

如果您使用宽度优先的蛮力，它仍然是蛮力，但至少保证您能得出最短的移动序列（如果有答案的话）。这是使用宽度优先搜索的快速 Python 解决方案。

from time import time

def generate(c):
    sep = "UU"
    c1, c2 = c.split(sep)
    for a in range(len(c1)-1):
        yield c1[0:a]+sep+c1[(a+2):]+c1[a:(a+2)]+c2
    for a in range(len(c2)-1):
        yield c1+c2[a:(a+2)]+c2[0:a]+sep+c2[(a+2):]

def solve(moves,used):
    solved = [cl for cl in moves if cl[-1].rindex('0') < cl[-1].index('1')]
    if len(solved) > 0: return solved[0]
    return solve([cl+[d] for cl in moves for d in generate(cl[-1]) if d not in used and not used.add(d)],used)

code = raw_input('enter the code:')

a = time()
print solve([[code]],set())
print "elapsed time:",(time()-a),"seconds"