<p>You are given a string <code>num</code>, representing a large integer, and an integer <code>k</code>.</p>

<p>We call some integer <strong>wonderful</strong> if it is a <strong>permutation</strong> of the digits in <code>num</code> and is <strong>greater in value</strong> than <code>num</code>. There can be many wonderful integers. However, we only care about the <strong>smallest-valued</strong> ones.</p>

<ul>
	<li>For example, when <code>num = &quot;5489355142&quot;</code>:

	<ul>
		<li>The 1<sup>st</sup> smallest wonderful integer is <code>&quot;5489355214&quot;</code>.</li>
		<li>The 2<sup>nd</sup> smallest wonderful integer is <code>&quot;5489355241&quot;</code>.</li>
		<li>The 3<sup>rd</sup> smallest wonderful integer is <code>&quot;5489355412&quot;</code>.</li>
		<li>The 4<sup>th</sup> smallest wonderful integer is <code>&quot;5489355421&quot;</code>.</li>
	</ul>
	</li>
</ul>

<p>Return <em>the <strong>minimum number of adjacent digit swaps</strong> that needs to be applied to </em><code>num</code><em> to reach the </em><code>k<sup>th</sup></code><em><strong> smallest wonderful</strong> integer</em>.</p>

<p>The tests are generated in such a way that <code>k<sup>th</sup></code>&nbsp;smallest wonderful integer exists.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;5489355142&quot;, k = 4
<strong>Output:</strong> 2
<strong>Explanation:</strong> The 4<sup>th</sup> smallest wonderful number is &quot;5489355421&quot;. To get this number:
- Swap index 7 with index 8: &quot;5489355<u>14</u>2&quot; -&gt; &quot;5489355<u>41</u>2&quot;
- Swap index 8 with index 9: &quot;54893554<u>12</u>&quot; -&gt; &quot;54893554<u>21</u>&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;11112&quot;, k = 4
<strong>Output:</strong> 4
<strong>Explanation:</strong> The 4<sup>th</sup> smallest wonderful number is &quot;21111&quot;. To get this number:
- Swap index 3 with index 4: &quot;111<u>12</u>&quot; -&gt; &quot;111<u>21</u>&quot;
- Swap index 2 with index 3: &quot;11<u>12</u>1&quot; -&gt; &quot;11<u>21</u>1&quot;
- Swap index 1 with index 2: &quot;1<u>12</u>11&quot; -&gt; &quot;1<u>21</u>11&quot;
- Swap index 0 with index 1: &quot;<u>12</u>111&quot; -&gt; &quot;<u>21</u>111&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;00123&quot;, k = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> The 1<sup>st</sup> smallest wonderful number is &quot;00132&quot;. To get this number:
- Swap index 3 with index 4: &quot;001<u>23</u>&quot; -&gt; &quot;001<u>32</u>&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= num.length &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>num</code> only consists of digits.</li>
</ul>

# this function modifies l to a new list, which is
# strictly after l and before or equal to the k-th successor of l
# in the lex order.
# "find the minimum i such that l[i:] is reverse-sorted.
# find the maximum j >= i with l[j] > l[i - 1].
# swap l[j] and l[i - 1] and then sort l[i:]."
# note that after the swap, l[i:] will still be reverse-sorted.
# so equivalently, just reverse l[i:].
# shortcut:
# given a sorted terminal segment, we can do a bit of combinatorics
# to determine the number of rearrangements of that segment, and
# often skip quite a number of permutations.
# it also accepts and returns an upper bound for i, `skip`,
# since after doing the shortcut, we don't need to check
# the whole reversed suffix.
def lex_succ(l, k, skip):
    for i in reversed(range(skip)):
        if l[i] > l[i - 1]:
            break
    # now l[i:] is reverse-sorted.
    # if it's also sorted, then switch to the shortcut:
    if k > 1 and l[i] == l[-1]:
        # l[j:] is sorted. How many permutations of l[j:] are there?
        # answer: N! / (N_1! N_2! ... N_t!)
        # where N = len(l[j:]) and N = N_1 + ... + N_t
        # and the N_i are the number of times the distinct elements
        # appear in the list.
        N = 0
        perms = 1
        prev = 10
        for x, g in groupby(reversed(l)):
            if x > prev:
                break
            for Ni in accumulate(1 for _ in g):
                N += 1
                if perms * N // Ni > k + 1:
                    N -= 1
                    l[-N:] = reversed(l[-N:])
                    return perms - 1, len(l) - N + 1
                perms = perms * N // Ni
            prev = x
        l[-N:] = reversed(l[-N:])
        return perms - 1, len(l) - N + 1
    # else produce the successor as normal.
    else:
        # we could use binary search here.
        # but it doesn't seem to provide a practical improvement.
        for j in reversed(range(len(l))):
            if l[j] > l[i - 1]:
                break
        l[j], l[i - 1] = l[i - 1], l[j]
        l[i:] = reversed(l[i:])
        return 1, len(l)

# distance between a and b in the "bubble metric".
# essentially the problem is "how many swaps would bubblesort need to make
# in order to sort L?"
# this is basically the problem of counting inversions. There are O(n log n)
# algorithms: https://stackoverflow.com/questions/337664/counting-inversions-in-an-array/6424847#6424847
# but they're not worth it in this case.
def dist(a, b):
    res = 0
    for i, x in enumerate(a):
        if b[i] != x:
            j = b.index(x, i + 1)
            res += j - i
            b.insert(i, b.pop(j))
    return res

class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        kth_wond = list(map(int, num))
        skip = len(kth_wond)
        while k:
            d, skip = lex_succ(kth_wond, k, skip)
            k -= d
        # the first argument to dist may be any iterable.
        return dist(map(int, num), kth_wond)
55