Order transformation

Question

Say I have two orders ABCDE and EDCBA, and I want to change from one to the other. But I can only exchange two groups of orders at one time, with associated cost per group.

So in this case, I can go from (A)(BCDE) to (BCDE)(A) to (B)(CDE)A to (CDE)(B)(A) to (C)(DE)BA to (DE)(C)(B)(A) to EDCBA, and the cost would be cost(A)*cost(BCDE) + cost(B)*cost(CDE) + cost(C)*cost(DE) + cost(D)*cost(E)

In other case, if I want to go from ABCD to CDBA, I could have (AB)(CD) to (CD)(BA) in one step with cost(AB)*cost(CD).

I want to ask what algorithms can I use to (1) minimize the steps it take to transform one order to the other and (2) what if I also want to minimize the cost? (minimized cost not necessarily implies minimized steps)

How many columns are there? The former half is trivial (hint: ab bc cd de) and if there are very few columns, you could brute force the latter. — John Dvorak, Jun 03 '16 at 05:48
Does (1) have higher priority than (2)? It's easy to come up with cases where this matters. — John Dvorak, Jun 03 '16 at 05:53
I think you need to build a graph of orders (with orders as vertices and transformations as edges), and search for a shortest path in it. The full graph will be large (N! vertices). You probably want to build it lazily so that parts of it that are too expensive are not built at all. — n. m. could be an AI, Jun 03 '16 at 05:58
You can think cost(A) as the size of matrix A, so cost(A)*cost(B) = (mn) * (np), cost(AB) = m*p. — Ryan, Jun 03 '16 at 06:06
(2) has higher priority than (1), I think (1) is a special case of (2) with cost equal for every column. — Ryan, Jun 03 '16 at 06:07

score 1 · Accepted Answer · edited May 23 '17 at 12:15

This feels like a shortest path problem to me, similar to other "how to get from one state to the other", like 15-puzzle.

When solving it as shortest path problem, you model the problem as a graph, where all valid states (in your case, all permutation of the characters) are vertices, and all valid transformations are edges. Formally:

G = (V,E)
V = { p | p is a permutation of the start/end state }
E = { (u,v) | can transform u to become v in one step }

In the weighted version (minimal cost), you also have a weight function: w(u,v), which is how expensive it is to make the transformation.

After you have a graph model, this is basically finding the shortest path from one source (the starting state) to one target (the goal).

This can be solved for example with:
Unweighted (shortest distance):

BFS
Bi-directional BFS
A* search algorithm (if you can have admissible heuristic)

Weighted (Smallest Cost):

Dijkstra's Algorithm
Bellman-Ford
A* search algorithm (if you can have admissible heuristic)

Important note:

You don't need to generate the graph before starting, you can have a function next:V->2^V, that given some state - generates all the possible transformation from it. Then you can use any of these algorithms with this next() function, and generate (on the fly) only the portion of the graph that is needed during the solution.

Order transformation

1 Answers1