algorithm - sorting bins two at a time -

algorithm - sorting bins two at a time -

i'm stumped next problem in case there 4 bins. can 6 or 8 not 4. also, can help me come generalized algorithm this?

you have n bins (arranged in alternate order of b b ...) can move 2 @ time , given 2n slots. sort them in end "a" bins left of "b" bins. should adjacent, i.e. no gaps @ end. example:

_ _ _ _ b b a

thanks

edit: yes have move 2 adjacent bins @ time 2 adjacent spots.

edit 2: no can't transpose bins. here's illustration 6 bins:

_ _ _ _ _ _ b b b a

_ _ _ _ b b _ _ b a

_ _ _ _ b b b a _ _

_ _ a b b b _ _ _ _

a straightforward breadth-first search of reachable positions 4 bins case showed cannot solved. here rough pseudo-code can seek writing yourself:

todo_queue = ["____baba", []] path_to_position = {} while things in todo_queue: (position, path) = todo_queue.next() if position in path_to_position: go on # we've been here before. if position success: print path exit here move in possible_moves(position): todo_queue.add([position after move, path + [move]])

for general solution, suffices breadth-first search cases of 6, 8, 10 , 12 bins special cases. larger numbers bins can solve 1 of 4 create middle of solution, , solve blocks of 8. can move around , rearrange solved blocks pair pair final solution.

algorithm sorting