6
$\begingroup$

Inspired by a word game Waffle, see footnotes if interested. The abstracted problem:

You're given an input array of letters, some of which might be identical (i.e. repeated), e.g. GSAAKD. You are also given a desired outcome, which is a second array containing the same multiset of letters, e.g. ASKGAD. The challenge is to make the minimum no. of swaps to turn the first array into the second array.

In this example:

  • The shortest path is gSAaKD -> ASaGkD -> ASKGAD of $2$ total swaps.

  • The first letter in the desired outcome is A, but it makes a difference which A you move there. E.g. if your first move is gSaADK -> ASGAKD then you cannot finish in $1$ more swap ($2$ total swaps).

Related / special case: If the letters are all distinct, then this is the well known problem of minimum no. of swaps to turn one permutation into another. Can someone confirm what I remember about the solution in this case?

  • The min. no. of swaps $= N -$ no. of cycles

  • A greedy algorithm where each step you put one letter into its correct position achieves the minimum.

Questions: Bounty will be awarded if you answer either Q1 or Q2. If one person answers Q1 and another person answers Q2, I will award the full bounty to each. :)

Q1: characterization: What is a good way to characterize the answer? Are cycles even well-defined when there are repeats? (I'm looking for a characterization beyond the obvious one where we consider all possible mappings of repeated letters to their correct positions and just apply the permutation solution to each.)

Q2: greedy algorithm:

First let me propose the following greedy algorithm: At every step, make a move s.t. either (A) or (B) happens (or both):

  • (A) a non-repeated letter gets to its (unique) correct position,

  • (B) both swapped letters end up at correct positions (in this case, a swapped letter might be one of a repeated set, and it ends in one of its correct positions in the desired outcome).

The greedy algorithm as specified above is "incomplete" in the sense that one may be unable to find a move that meets (A) or (B). However, suppose there is such a sequence of moves (where every step meets (A) or (B)) resulting in the desired outcome. Is such a sequence guaranteed to achieve the minimum? Alternatively, can you devise a different greedy algorithm that can reach the minimum?


Footnote on motivation: In Waffle, some letters are jumbled in a crossword grid and the challenge is to minimize no. of swaps to make all the words correct. Waffle is a weird game in that it is both a word game (anagramming) and a combinatorial game (minimizing no. of swaps). This question is about the latter, i.e. how I can minimize no. of swaps after solving the entire grid and knowing the desired outcome.

$\endgroup$
6
  • $\begingroup$ Suppose we start with the string "ABCDE" and we want to get to "BACED" using cycle notation we get the permutation $(A\ B)(C)(D\ E)$, a cycle of length $1$ (the "C" in this case) was already in the right spot and thus costs no swaps. And as we can see a cycle of length $2$ is fixed with a single swap. In fact, it is easily verified that for cycles of length $n$ the amount of swaps we need is $n-1$ (the first element of the cycle is swapped with the next and so on). See next comment (... $\endgroup$ Jul 29, 2023 at 23:58
  • $\begingroup$ ...). In conclusion, for every permutation, the amount of swaps needed is equal to the sum of the orders of the cycles that form it minus 1. If the permutation has length $n$, this results in $n - \#\textit{cycles}$. Note that the string "ABCDE" was sorted, an unsorted string can be mapped to a sorted string or the cycles can still be written down easily from two-line cycle notation. $\endgroup$ Jul 29, 2023 at 23:58
  • $\begingroup$ @jorisperrenet - thanks for your comments. if i understand you correctly, you are confirming my recollection in the special (permutation) case, first bullet, that no. of swaps $= N - $ no. of cycles, right? $\endgroup$
    – antkam
    Jul 31, 2023 at 14:50
  • 1
    $\begingroup$ That is right. Although, from my reasoning you could see that the second bullet also holds (for each cycle put each letter to the correct position). I did not manage to find a greedy algorithm for your interesting question, only a brute force one which would probably run fast enough if the words are somehow restricted in size. For the general case of arbitrary long words the greedy algorithms I came up with were not correct. $\endgroup$ Jul 31, 2023 at 19:41
  • 1
    $\begingroup$ Thanks again. Yeah in this particular game the array is usually about 15-16 letters long, with maybe 8-10 distinct letters, so a small search-based / brute-force program should be able to solve any particular instance in very little time. But I'm hoping a human-doable greedy algorithm can work because, after all, I am a human playing Waffle and I dont want to have to run e.g. a python script to minimize! $\endgroup$
    – antkam
    Jul 31, 2023 at 22:08

1 Answer 1

0
$\begingroup$

Thought I found it, but no, this algorithm just came very close.

A Failed Algorithm

Define the input to be the original string, $s$, and the desired string $e$. Assume that $s_i\neq e_i$ holds $\forall i$. Now, we want to get the shortest cycle there is in the two-line cycle notation where $s$ is written above $e$.

Start with every unique letter in $s$, call it $A$, since a cycle repeats by definition, search for the length of the shortest route to get back to $A$ (the first time you encounter it). It is clear that if this is done for every letter the shortest cycle must be found (since all start and end letters are verified). Using memoization (on starting letter and ending letter) this search can be done in $O(d^2)$. Also, note that different letters may not be visited twice as this can lead to an infinite loop (and a longer cycle than necessary).

Once the shortest cycle is found, add $len(cycle)-1$ to the result, remove all indices of the cycle, and repeat this process until $s$ and $e$ are empty.

The problem is, there can be multiple cycles with the shortest length, only the maximum disjoint set (MDS) of cycles of that length can be flipped at the same time to give some/the correct answer.

An Example

I will use "AEBCFABC" to "BCEFABCA" as an example (the answer is $6$ swaps). $$ \begin{pmatrix} A\ E\ B\ C\ F\ A\ B\ C \\ B\ C\ E\ F\ A\ B\ C\ A \end{pmatrix} $$ We will look for the shortest cycle contained above (remember that only paths with no repeated letters are denoted). We get $$ A\to B \to \{C,E\}\to A \\ B\to \{C,E\}\to \{A, F\} \to B \\ C\to \{A,F\}\to B \to C \\ E\to C\to \{A, F\} \to B \to E \\ F\to A\to B\to \{C, E\} \to F\,, $$ the shortest cycle length is thus $3$ and therefore we add $2$ swaps to the total (to correctly swap $ABC\to BCA$) and remove the $3$ cycle leaving "AEBCF" to "BCEFA".

The "proof"

Once you swap a cycle (for now a cycle of distinct letters) you know that afterwards all letters are in the correct spot. Thus if once the shortest cycle was $3$, then after swapping the shortest cycle this number can only increase, never decrease.

You always want to get the least amount of swaps per letter you place correctly, since swapping a cycle costs $n-1$ swaps the ratio of swaps to correct placements becomes $\frac{n-1}{n}$, this is naturally minimal if $n$ is minimal (also, see the comments in the OP). Therefore, if we repetitively swap the shortest cycle we end up with the best we can achieve.

Now, for duplicate letters. It is clear that in the above example instead of swapping the final $3$ letters I also could have chosen the first and the last two. We agree that swapping the shortest cycles is the best, thus now, imagine coloring all cycles which have exactly that length. If a cycle can be colored without overlap, my algorithm will detect it and correctly swap it. If there are (multiple) cycles with overlap, my original algorithm will detect only one and swap it. However, this is where the MDS needs to be used, an NP-complete problem, as many cycles as possible with the shortest length need to be flipped, a (somewhat complex) example of where my original algorithm goes wrong is "ABCDCFAGB" to "BCABDCFAG". Also, maybe a flip of a cycle of length 3 breaks a cycle of length 4 causing more problems.

Python program implementing my faulty algorithm

This program can compute an upper bound for the answer for (random) lowercase strings of length 1000 in about a second.

from collections import Counter, defaultdict

def count_swaps(start, end):
    assert Counter(start) == Counter(end)

    conn = defaultdict(set)
    pairs = defaultdict(list)
    for idx, (s, e) in enumerate(zip(start, end)):
        if s == e: continue  # This letter is already correct
        conn[s].add(e)
        pairs[(s, e)].append(idx)

    if len(conn) == 0:  # If all letters are in the correct spot
        return 0

    cache = {}
    def from_to(u, v, path=(), path_set=set()):
        """Returns the number of swaps and route of the shortest path from u to v."""
        if v in conn[u]:
            return (1, (u, v))

        if (u, v) in cache:
            return cache[(u, v)]

        arr = []
        for w in conn[u]:
            if w in path_set:  # Already traversed this edge
                continue
            arr.append(from_to(w, v, (u,)+path, path_set.union({u})))
        length, route = min(arr, key=lambda x: x[0], default=(float('inf'), ()))
        ret = (length+1, (u,)+route)  # the (u, w) edge gets traversed
        cache[(u, v)] = ret
        return ret

    # Get the shortest cycle, i.e. shortest path from a node to itself
    cycle_len, route = min([from_to(i, i) for i in conn], key=lambda x: x[0])

    idxs_to_remove = set()
    for i in range(1, len(route)):
        # (route[i-1], route[i]) must be an edge
        # Note that taking the first index of pairs is interchangable.
        idxs_to_remove.add(pairs[route[i-1], route[i]][0])

    new_start = new_end = ''
    for idx in range(len(start)):
        if idx not in idxs_to_remove:
            new_start += start[idx]
            new_end += end[idx]

    return (cycle_len-1) + count_swaps(new_start, new_end)
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .