Find Minimum Transformation Between Multisets of Lists of Cards

Question

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a valid Rummikub config) and want to find the fewest number of pickup->place tile operations to transform a into b.

Type Definitions:

• C = Pair<int, int>: Card represented as a suit and value pair.
• CL = List<C>: Card list.
• S = MultiSet<CL>: A collection of card lists.

Problem Statement: You are given two collections s0, s1, and one card list h. (s0 union {h} = a and s1 = b) Find a minimum number of "move" operations needed to convert s0 union {h} into s1. Note, s0 union {h} will be a rearrangement of s1. That is, if you flatten s0 union {h} into a CL and similarly flatten s1 into a CL then the two CL are equivalent up to permutation. Note, there is at most 3 copies of any C in s1.

Move Operation:

Move(C c,          // the card to move
     CL src,       // the CL to move c from
     CL dst,       // the CL to move c to
     int dstIndex) // the index in dst to insert c to

If dst is empty then this operation can be said to create dst. Similarly if, after the movement, src is empty then the operation can be said to delete src. Basically, creation and deletion of CLs is free and happens implicitly. I do not want to consider the creation of a CL, by itself, an operation. Only movement of cards is an operation.

First attempt: My first attempt at solving this was to linearize (i.e. flatten) s0 union {h} and s1 and compute their edit distance using only insertions & deletions (insert & delete pairs form a move op). However, the total number of edit operations depends on the order between the CL in the linearization. Since I want the minimum number of edit ops I would need to check each permutation of CLs, right? Doing so is not tractable in my application since I may have collections containing 20 or more differing CLs.

Additional Consideration: If it helps, changing the type of CL to Set<C> is possible in my application. Basically, s0 and s1 could have inner type of Set<C>. But I've used List<C> since I'm unsure if, in intermediate steps of the solution, there would be a need to have duplicates in a CL. Note if Set<C> is used, then the dstIndex argument to Move is not needed. Also, I would prefer if the input h was only moved from and not moved to, but this is a soft requirement.

Any help or pointers in the right direction would be greatly appreciated!

Answer 1

I think the variant with sets can be solved using bipartite matching.

Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer sets in s0 than in s1, add additional left vertices, corresponding to empty sets, until both sides have the same number of vertices. The edge between a left vertex and a right vertex corresponding to sets $L,R$ is assigned the weight $-|L \bigtriangleup R|$, where $L \bigtriangleup R$ is the symmetric difference of $L,R$.

Find the maximum weight matching in this graph.

I believe that this minimizes the number of moves. In particular, if this matching has total weight $w$, then you can solve your problem with $w/2$ moves. If the matching associates a set $L$ in s0 and a set $R$ in s1, then in your problem, $L$ becomes $R$ after all move operations; each element in $L \setminus R$ is moved to its new destination (according to s1), and each element in $R \setminus L$ is moved from its original source (according to s0).

Please double-check my logic and try it on some examples to verify that it appears to work correctly.

---

As for your original problem with lists can, I suspect, be solved by using

$$-|L \bigtriangleup R| - \pi(L \cap R)$$

as the weight on the edge between $L,R$, where $|L \bigtriangleup R|$ denotes the number of items present in only one of $L,R$, and $\pi(L \cap R)$ denotes the number of moves needed to sort the items that are common to $L,R$ from the order given by $L$ into the order given by $R$. I don't know how to compute $\pi(\cdots)$, but Inuyasha Yagami appears to have explained how it can be computed.

(This is different from computing the number of swaps needed to re-order the items common to $L,R$, from the order in $L$ to the order in $R$. The number of swaps is analyzed in Rearrange an array using swap with 0 (see also Algorithm for generating sorting instructions, Sort array with minimum swaps, Minimum number of swaps in sorting sequence). However, you are asking about the number of moves, which is a different problem.)

It's particularly important to check my reasoning for this variant of the problem, as I have not checked this approach at all and it could easily be bogus.

---

My thanks to Inuyasha Yagami for multiple improvements and bugfixes to this answer.

Answer 2

Update (or possible correction) to the answer of D.W..

Since we are given the move operations and not the swap operations, we can compute $\pi$ in polynomial time. The problem is known as the permutation edit distance problem. $\pi(L,R) = |L| - |LCS(L,R)|$, where $LCS$ denotes the longest common subsequence, which can be computed in polynomial time.