java - 查找与给定数字非常接近的数字

Question

我有一个数字 (int y = 12345)。我想找到如何洗牌 y 以找到洗牌时可以进行的所有可能组合的中间数字。在这种情况下，答案将是 32541。

我最初尝试将 1,2,3,4,5 放入一个列表中，然后使用 Collections.shuffle 获取所有选项并将它们放入一个 sortedSet 中。然后获取 size()/2 处的索引。但这对于大于 123456789 的数字并不适用......

我还尝试使用递归来使用堆算法来切换所有数字。效果稍微好一些，但仍然无法处理大量数据。见下文。 (我把整数换成了字符串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"));
}

我目前的想法是不创建所有可能的数字，而是找到所有可能组合的确切中心 (int x = 33333)。然后查看哪个数字组合最接近该数字。在这种情况下，这要么是 32541，要么是 34125。这两个数字都与 x 相差 792 步。

这是我目前所拥有的:

    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"));
}

现在是创建找到最接近 x 的整数阶的算法的困难部分。有谁知道如何实现这一点？

Answer 1

(这是原始问题的答案，如何找到所有排列的中位数，而不是 XY 问题，如何找到最接近给定数字的排列。)

我认为，如果您想准确地找到排列的中位数，则有好消息也有坏消息:好消息:似乎有一个简单的算法。坏消息:没有确切的中位数，因为排列的数量总是偶数(因为它是 1 x 2 x 3 x ... x n)

1. 对输入的数字进行排序，使数字按升序排列
2. 如果数字是奇数位，取中间位作为第一位
3. 现在数字的位数是偶数；你必须选择两个中间数字中的任何一个，但这会扭曲结果(见上面的坏消息)
4. 如果您选择了较低的中间数字，则从剩余的数字中形成最大可能的数字，否则最低可能的数字。

对于您的示例:12345 -> 3 1245 --> 32 145 --> 32541，或 12345 -> < strong>3 1245 --> 34 125 --> 34125.

---

这背后的直觉如下:您可以将具有 n 个数字的数字的 n!(排序)排列分割为 n组，每个组都以 第 位数字开头并具有 (n-1)! 个元素。由于这些组是有序的，并且每个组都具有相同数量的元素，对于奇数输入，中位数必须在中间组中，对于偶数输入，中位数必须位于中间两组之间。编号输入。所以你必须选择较小的最大的，或者较大的中间组中的最小的。 (对于奇数输入，对中间组的 n-1 个子组执行相同的操作。)

---

这里有一个示例代码(Python的，因为我太懒了。。。)

# 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)