find number in close proximity to a given number

Question

I have a number (int y = 12345). I want to find how I can shuffle y to find the number that is the middle of all possible combinations that can be made when shuffling. In this case, the answer would be 32541.

I initially tried to put 1,2,3,4,5 in a list and use Collections.shuffle to get all options and put them in a sortedSet. Then get the index at size()/2. But this doesn't work well for numbers larger than 123456789...

I also tried to use recursion to switch around all the numbers using heap's algorithm. That worked slightly better, but still couldn't process large numbers. See below. (I switched the integer to a string abcdefghij)

public static SortedSet<String> allStrings = new TreeSet<>();

public static SortedSet<String> findMidPerm(String strng) {
    permutation("", strng);
    return allStrings;
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) {
        allStrings.add(prefix);
    } else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
    }
}

public static void main(String[] args) {
    System.out.println(findMidPerm("abcdefghij"));
}

My current idea is to not create all possible numbers, but find the exact center of all possible combinations (int x = 33333). And then see which combination of numbers is closest to that number. In this case, this is either 32541 OR 34125. Both numbers are 792 steps away from x.

This is what I have so far:

    public static float findMidPerm(String strng) {
    float maxNum = findMaxNum(strng);
    float minNum = findMinNum(strng);
    float middleNum = findMiddleNum(minNum, maxNum);
    return middleNum;

}

private static float findMiddleNum(float minNum, float maxNum) {
    return (minNum+maxNum)/2;
}

private static float findMinNum(String strng) {
    String s = "";
    for (int i = 0; i <= strng.length(); i ++) {
        s += i;
    }
    return Float.parseFloat(s);
}

private static Float findMaxNum(String strng) {
    String s = "";
    for (int i = strng.length(); i> 0; i --) {
        s += i;
    }
    return Float.parseFloat(s);
}

public static void main(String[] args) {
    System.out.println(findMidPerm("abcdefghijklmnop"));
}

Now for the difficult part of creating the algorithm that finds the order of integers closest to x. Does anyone have any ideas how this can be achieved?

Answer 1

(This is an answer to the original problem, how to find the median of all permutations, not for the XY-problem, how to find the permutation closest to a given number.)

I think, if you want to find exactly the median of the permutations, there is good and bad news: Good news: There seems to be an easy algorithm for that. Bad news: There is no exact median, as the number of permutations is always even (as it is 1 x 2 x 3 x ... x n)

1. Sort the input number so the digits are in ascending order
2. If the number has an odd number of digits, pick the middle digit as the first digit
3. The number now has an even number of digits; you have to pick either of the two middle digits, but this will skew the result (see the bad news above)
4. If you picked the lower of the middle digits, form the largest possible number from the remaining digits, otherwise the lowest possible number.

For your example: 12345 -> 3 1245 --> 32 145 --> 32541, or 12345 -> 3 1245 --> 34 125 --> 34125.

---

The intuition behind this is as follows: You can subdivide the n! (sorted) permutations of a number with n digits into n groups, each starting with the ith digit and having (n-1)! elements. As those groups are ordered, and each has the same number of elements, the median has to be in the middle group for an odd-numbered input, and right in between the middle two groups for an even-numbered input. So you have to pick either the largest of the smaller, or the smallest of the larger middle group. (And for an odd-numbered input, do the same for the n-1 sub-groups of the middle group.)

---

Here's a sample code (in Python, because I'm too lazy...)

# above algorithm
def med_perm(n):
    lst = sorted(str(n))                                      # step 1
    res = [lst.pop(len(lst)//2)] if len(lst) % 2 == 1 else [] # step 2
    res.append(lst.pop(len(lst)//2))                          # step 3
    res.extend(lst)                                           # step 4
    return int(''.join(res))

# for reference
import itertools
def med_perm2(n):
    perms = list(map(''.join, itertools.permutations(sorted(str(n)))))
    return int(perms[len(perms)//2])

# testing
import random
n = random.randint(1, 100000000)
x, y = med_perm(n), med_perm2(n)
print(n, x, y, x==y)

Answer 2

I actually found a sneaky way to do this. I was writing everything down on paper and recognized a pattern. This is the first draft of the code and it can probably be done way more efficient. Feel free to adjust!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Kata {

public static String findMidPerm(String strng) {
    strng = sortString(strng);
    StringBuilder sb = new StringBuilder();
    List<Integer> s = createNum(strng);
    for(int i =0; i <s.size(); i++) {
        int b = s.get(i);
        sb.append(strng.charAt(b-1));
    }
    return sb.toString();
}

private static String sortString(String strng) {
    char[] ar = strng.toCharArray();
    Arrays.sort(ar);
    String sorted = String.valueOf(ar);
    return sorted;
}

public static List<Integer> createNum(String strng) {
    List<Integer> list = new ArrayList<>();
    int s = strng.length() / 2;
    int s2 = (strng.length() / 2) + 1;
    if (strng.length() % 2 == 0) {
        list.add(s);
        for (int i = strng.length(); i > 0; i--)
            if (i != s) {
                list.add(i);
            }
    } else {
        list.add(s2);
        list.add(s);
        for (int i = strng.length(); i > 0; i--)
            if (i != s && i != s2) {
                list.add(i);
            }
    }
    return list;
}

public static void main(String[] args) {
    System.out.println(findMidPerm("cmafilezoysht")); // cmafilezoysht is an input string in this case.

}

}