Minimum Adjacent Swaps to Reach the Kth Smallest Number solution and explanation

def next_permutation(perm):
    i = len(perm) - 2
    while i >= 0 and perm[i] >= perm[i + 1]:
        i -= 1
    if i == -1:
        return False
    j = len(perm) - 1
    while perm[j] <= perm[i]:
        j -= 1
    perm[i], perm[j] = perm[j], perm[i]
    perm[i + 1:] = perm[i + 1:][::-1]
    return True

def min_adjacent_swaps(num, k):
    num_list = list(num)
    b_list = num_list[:]
    for _ in range(k):
        next_permutation(num_list)

    def count_swaps(a, b):
        a = list(a)
        swaps = 0
        for i in range(len(a)):
            if a[i] != b[i]:
                j = a.index(b[i], i)
                while j > i:
                    a[j], a[j - 1] = a[j - 1], a[j]
                    swaps += 1
                    j -= 1
        return swaps

    return count_swaps(b_list, num_list)

num = "5489355142"
k = 4
print(min_adjacent_swaps(num, k))

function nextPermutation(perm) {
    let i = perm.length - 2;
    while (i >= 0 && perm[i] >= perm[i + 1]) i--;
    if (i === -1) return false;
    let j = perm.length - 1;
    while (perm[j] <= perm[i]) j--;
    [perm[i], perm[j]] = [perm[j], perm[i]];
    perm = [...perm.slice(0, i + 1), ...perm.slice(i + 1).reverse()];
    return perm;
}

function minAdjacentSwaps(num, k) {
    const numArr = num.split('');
    let bArr = numArr.slice();
    for (let count = 0; count < k; count++) {
        numArr = nextPermutation(numArr);
    }

    const countSwaps = (a, b) => {
        let swaps = 0;
        a = a.slice();
        for (let i = 0; i < a.length; i++) {
            if (a[i] !== b[i]) {
                let j = a.indexOf(b[i], i);
                while (j > i) {
                    [a[j], a[j - 1]] = [a[j - 1], a[j]];
                    swaps++;
                    j--;
                }
            }
        }
        return swaps;
    };

    return countSwaps(bArr, numArr);
}

const num = "5489355142";
const k = 4;
console.log(minAdjacentSwaps(num, k));

import java.util.*;

public class MinSwaps {
    public static int getNextPermutation(String num, int k) {
        char[] numArr = num.toCharArray();
        char[] original = num.toCharArray();
        while (k-- > 0) {
            nextPermutation(numArr);
        }
        return countSwaps(original, numArr);
    }

    private static void nextPermutation(char[] num) {
        int i = num.length - 2;
        while (i >= 0 && num[i] >= num[i + 1]) i--;
        if (i >= 0) {
            int j = num.length - 1;
            while (num[j] <= num[i]) j--;
            swap(num, i, j);
        }
        reverse(num, i + 1);
    }

    private static void swap(char[] num, int i, int j) {
        char temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }

    private static void reverse(char[] num, int start) {
        int end = num.length - 1;
        while (start < end) {
            swap(num, start, end);
            start++; end--;
        }
    }

    private static int countSwaps(char[] original, char[] target) {
        int swaps = 0;
        List<Character> listO = new ArrayList<>();
        for (char c : original) listO.add(c);
        for (int i = 0; i < target.length; i++) {
            if (listO.get(i) != target[i]) {
                int index = listO.lastIndexOf(target[i]);
                for (int j = index; j > i; j--) {
                    Collections.swap(listO, j, j - 1);
                    swaps++;
                }
            }
        }
        return swaps;
    }

    public static void main(String[] args) {
        String num = "5489355142";
        int k = 4;
        System.out.println(getNextPermutation(num, k));
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int getNextPermutation(string& num, int k) {
    string original = num;
    vector<int> swaps;
    while (k--) {
        next_permutation(num.begin(), num.end());
    }
    for (int i = 0; i < num.size(); ++i) {
        if (original[i] != num[i]) {
            int j = i;
            while (original[j] != num[i]) {
                j++;
            }
            while (j > i) {
                swap(original[j], original[j - 1]);
                swaps.push_back(j - 1);
                j--;
            }
        }
    }
    return swaps.size();
}

int main() {
    string num = "5489355142";
    int k = 4;
    cout << getNextPermutation(num, k);
    return 0;
}

function getMinSwaps(num: string, k: number): number {
    const n = num.length;
    const s = num.split('');
    for (let i = 0; i < k; ++i) {
        nextPermutation(s);
    }
    const d: number[][] = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < n; ++i) {
        d[+num[i]].push(i);
    }
    const idx: number[] = Array(10).fill(0);
    const arr: number[] = [];
    for (let i = 0; i < n; ++i) {
        arr.push(d[+s[i]][idx[+s[i]]++]);
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (arr[j] > arr[i]) {
                ans++;
            }
        }
    }
    return ans;
}

function nextPermutation(nums: string[]): boolean {
    const n = nums.length;
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i < 0) {
        return false;
    }
    let j = n - 1;
    while (j >= 0 && nums[i] >= nums[j]) {
        j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
    for (i = i + 1, j = n - 1; i < j; ++i, --j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return true;
}

func getMinSwaps(num string, k int) (ans int) {
	s := []byte(num)
	for ; k > 0; k-- {
		nextPermutation(s)
	}
	d := [10][]int{}
	for i, c := range num {
		j := int(c - '0')
		d[j] = append(d[j], i)
	}
	idx := [10]int{}
	n := len(s)
	arr := make([]int, n)
	for i, c := range s {
		j := int(c - '0')
		arr[i] = d[j][idx[j]]
		idx[j]++
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if arr[j] > arr[i] {
				ans++
			}
		}
	}
	return
}

func nextPermutation(nums []byte) bool {
	n := len(nums)
	i := n - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i--
	}
	if i < 0 {
		return false
	}
	j := n - 1
	for j >= 0 && nums[j] <= nums[i] {
		j--
	}
	nums[i], nums[j] = nums[j], nums[i]
	for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
	return true
}