Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct

Question

This problem is from LeetCode.

You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

My question is, why does the following greedy algorithm work?

minimum_integer(num, k):
 n <- length of num
 i <- 0
 while i < n and k > 0:
 pos <- position of the first smallest element in num[i..min(n-1, i + k)]
 while pos > i:
 swap pos and pos-1 of num
 decrease pos by 1
 decrease k by 1
 increase i by 1
 return num

The algorithm makes sense intuitively; we essentially move the minimum digit in a window of size at most k into each possible position, and since we minimize leading digits each time starting from the first leading digit, it makes intuitive sense that the resulting number should be minimized. But I'm not sure how to prove it produces an optimal solution using an exchange argument.

• Russel: Where did you get this solution and what is $n$?
• user3472: @Russel it's based off a solution from the link I provided. I basically just converted it to pseudocode.
• user16034: This code is not performing swaps !
• 喜欢算法和数学: @YvesDaoust Good catch. Updated.
• user3472: @YvesDaoust the previous code actually did perform swaps. It just did it in a different way through shifting.

Answer 1

Let $A$ be the greedy algorithm you presented and $A'$ be the algorithm that correctly solves the problem.

Let $m=d_{n-1}d_{n-2}d_{n-3}...d_2d_1d_0$ be the solution obtained by $A$ and $m'=d'_{n-1}d'_{n-2}d'_{n-3}...d'_2d'_1d'_0$ be the number obtained by $A'$.

First, some observation about $A$. For each index 0ドル \le j \le n-1$, $A$ select that smallest digit from indices $\le j$ that can be placed at index $j$ using the remaining number of moves. This implies that once a digit is in-place, it remains in its position until the end. Now, the number of swaps $A$ uses to move a digit initially at index $i$ is $j - i$, which is the minimum possible if swapping adjacent digits is the only allowed move. Therefore, $A$ uses the minimum possible moves to place a digit to its place.

Let $i$ be the last index that $A$ updated before it exhaust all the remaining moves. Because $A$ selects the minimum digit that can be placed at index $j \ge i$ using the minimum number of moves while not exceeding the available moves, it must be that $d_j = d'_j$ for $i \le j \le n-1$. Now, since $A$ uses the minimum number of moves possible to move a digit to its final position, the total number of moves $A'$ uses to change all index $j \ge i$ cannot be less than the total number of moves used by $A$. Therefore, both $A$ and $A'$ cannot change any remaining index less than $i$, thus $d_j = d'_j$ for 0ドル \le j \le i-1$. Finally, $m = m'$.

• 喜欢算法和数学: Does this answer mention that different moving order will not affect the number of total adjacent swaps used? For example, the same number of adjacent swaps will be used whether $d_3$ is moved to index 0 and then $d_2$ is moved to index 1 or $d_2$ is moved to index 1 and then $d_3$ is moved to index 0 and then $d_2$ is moved to index 1 , assuming $n\ge 6$. Or does it?