如何找到一个给定数字的所有数字排列中最接近目标数字的排列？

Question

我刚在一本书中看到了这个有趣的问题，但是我找不到答案。

我有一个给定的数字X和一个目标数字Y，任务是找到X的所有数字的排列中最接近Y的那个。 数字以数组形式给出。没有给出数组大小限制。

示例

Given number X = 1212
Target number Y = 1500
Answer = 1221
Here, abs(1500-1221) is smallest among all permutations of X.

Given number X = 1212
Target number Y = 1900
Answer = 2112
Here, abs(1900-2112) is smallest among all permutations of X.

Given number X = 1029
Target number Y = 2000
Answer = 2019
Here, abs(2000-2019) is smallest among all permutations of X.

我找到的一种解决方法是对给定的数字生成所有排列，并在每个阶段计算差异。但是这非常慢。

我尝试寻找贪心算法，我将遍历目标数字 Y 的所有索引，并在每个索引处将给定数字 X 的那个数字放置在使 abs(Y[i] - X[i]) 最小的位置上。但是这在许多情况下失败了。

我正尝试想出一个动态规划的方法，但无法想出任何方法。

任何有关答案的线索都将有所帮助。

编辑 - 添加我的贪心方法的伪代码

for each index i in [0,Y]:

    min_index = 0;
    for each index j in [1, X.length]:
        if abs(X[j] - Y[i]) < abs(X[min_index] - Y[i]):
            min_val = j

    print X[min_index]
    remove min_index from X

Example X = 1212 and Y = 1900.
step 1 - output 1 and remove index 0 from X.
step 2 - output 2 and remove index 1 from X.
step 3 - output 1 and remove index 2 from X.
step 2 - output 1 and remove index 3 from X.
answer = 1212 which is wrong (correct answer is 2112).
So fails for this test case and lots more.

- Abhishek Kumar

---

{btsdaf} - Pham Trung

@PhamTrung 我已经编辑了问题。看一下吧。 - Abhishek Kumar

问题有任何限制条件吗？ - Pham Trung

{btsdaf} - Abhishek Kumar

Answer 1

因此，问题可以如下所示：

从最大有效数字开始，对于每个索引，有三种情况：

当前数字将小于所需数字，因此对于其余数字，我们尝试创建可能的最大数字 => 对于其余数字，我们按降序排序，即如果我们还剩下0、2、7、5 -> 我们将创建7520

当前数字将大于所需数字，因此对于其余数字，我们尝试创建可能的最小数字 => 对于其余数字，我们按升序排序，即如果我们还剩下0、2、7、5 -> 我们将创建0275

如果当前数字等于所需数字，则将其附加到前缀中，并在下一次迭代中尝试找到更好的匹配。

伪代码：

int prefix, result;
for each index i from 0 to Y.length() {

       int larger = prefix + smallestDigitLargerThan(Y(i)) + OtherDigitInAscendingOrder;
       int smaller = prefix + largestDigitSmallerThan(Y(i)) + OtherDigitInDescendingOrder;
       update result based on larger and smaller;
       if there is no digit equals to Y(i)
          break;
       else {
          remove Y(i) in X
          prefix = prefix*10 + Y(i)
       } 
    }
}
if prefix == Y {
   //We have a full match
   return prefix;
}
return result;

例如。

X = 1029
Y = 2000

At index 0 -> Y(0) = 2, 

int smaller = 0 (prefix) + 1(largest digit that is less than 2) + 920 (other digit in descending order) = 1920
int larger = 0 (prefix) + 9(smallest digit that is greater than 2) + 012 (other digit in ascending order) = 9012
int result = 1920
int prefix = 2

At index 1 -> Y(1) = 0,

int smaller = //Not exist
int larger = 2 + 1 + 09 = 2109
int result = 1920
int prefix = 20

At index 2 -> Y(2) = 0,

int smaller = //Not exist
int larger = 20 + 1 + 9 = 2019
int result = 2019
//Break as there is no digit match Y(2) = 0 from X

其他例子：

X = 1212
Y = 1500

At index 0 -> Y(0) = 1, 

int smaller = //Not exist
int larger = 0 + 2 + 112 = 2112
int result = 2112
int prefix = 1

At index 1 -> Y(1) = 5,

int smaller = 1 + 2 + 21 = 1221
int larger = //Not exist
int result = 1221
//Break from here as there is no digit match Y(1) = 5 in X

- Pham Trung

---

你的算法中的“desired digit”是什么意思？能否举一个例子（最好是问题中的最后一个例子）并展示模拟结果。谢谢。 - Abhishek Kumar

@AbhishekKumar 添加了一个示例。请检查伪代码和示例，从中应该很清楚。 - Pham Trung

{btsdaf} - Abhishek Kumar

{btsdaf} - Pham Trung

{btsdaf} - Pham Trung

Answer 2

宽度为3的波束搜索可能是一种方法。其思想是从最大到最小的数字构造数字，并用零填充其余部分。对于波束中的每个数字，您在每个步骤中构造最接近和次接近的数字，并丢弃所有比前三个更差的数字。（实际上，最多只需要波束大小为2。如果波束中两个条目的距离相等，则仅需要三个的情况。）在计算过程中，构造的数字A和B不应该相等（除非X只包含相同的数字）。

以下是第二个示例的波束。 *表示最佳波束，没有*表示两者同样好：

2000* -> 2100* -> 2112*
         2200  -> 2211
1000  -> 1200  
         1100

这是第一个例子：

1000  -> 1200* -> 1221*
         1100  -> 1122
2000  -> 2100
         2200

第三个例子需要在第二步使用3作为横梁大小，因为第二好的横梁1900和2100到2000的距离是100：

1000  -> 1900  -> 1901
         1100
2000* -> 2000* -> 2019*
         2100     2109

注意：在所有示例中，我已经完成了第三步和第四步。

数字 X = 1992 和 Y = 2000 是一个有趣的例子。

1000  -> 1900  -> 1992*
         1200
2000* -> 2100  -> 2199
         2900

因为在计算过程中最佳梁会发生变化。

我写了一个小的Python程序进行演示:

import sys

X = sys.argv[1]
Y = int(sys.argv[2])

def remove(s, i):
    return s[:i] + s[i+1:]

def expand(t):
    result = set()
    val = t[0]
    chars = t[1]
    index = len(val) - len(chars)
    for i in range(len(chars)):
        s = val[:index] + chars[i]
        r = remove(chars, i)
        if index < len(val):
            s += val[index + 1:]
        result.add((s, r))
    return result

beams = [("0" * len(X), X)]
for i in range(len(X)):
    newBeams = set()
    for t in beams:
        newBeams.update(expand(t))
    beams = sorted(newBeams, key = lambda t: abs(Y - int(t[0])))[:3]
    print beams

print "Result:", beams[0][0]

代码并不是最优的，但这个算法的运行时间是多项式级别的，最多为O(n² ln n)，而且这个估计非常宽松。

- clemens

---

{btsdaf} - clemens

{btsdaf} - Abhishek Kumar

{btsdaf} - clemens

{btsdaf} - Abhishek Kumar

{btsdaf} - clemens