How can I find a permutation of all the digits of a given number such that it is closest to the target number

Question

I just come across this interesting question from a book and I am unable to find the answer.

I have a given number X and a target number Y, task is to find such permutation of all the digits of X such that it is closest to Y. Numbers are in form of array. No array size limit is given there.

Example

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.

One of the solution I can find is to generate all permutations of the given number and at each stage calculates the difference. But this is very slow.

I tried to find the greedy approach, where I will iterate through all the indices of the target number Y and at each index I will put that digit of the given number X such that abs(Y[i] - X[i]) is minimum. But this fails for many cases.

I am trying to think of a DP approach, but unable to come up with any.

Any lead to the answer will be helpful.

Edit - Adding pseudo code for my greedy approach

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.

Answer 1

So, the problem can be seen as follow:

Starting from the largest significant digits, for each of these index, there are three cases:

• The current digit will be less than the desired digit, so for the rest of the digits, we try to create the largest number possible => for the rest of the digits, we sorted them in descending order , i.e if we have 0, 2, 7, 5 left -> we will create 7520

• The current digit will be larger than the desired digit, so for the rest of the digits, we try to create the smallest number possible => for the rest of the digits, we sorted them in ascending order , i.e if we have 0, 2, 7, 5 left -> we will create 0275

• If the current digit is equal to the desired digit, we will append it to the prefix and try to find better match in next iteration.

Pseudo-code:

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;

For example

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

Other example:

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

Answer 2

Beam search with width of 3 could be an approach. The idea is to construct the numbers from the largest to the smallest digit, and filling the rest with zeros. You construct the nearest and the second nearest numbers at each step for each number in the beam, and discarding all numbers which are worse than the top three. (In fact you're needing a beam size of two at most. The case of three is only needed, if the distance of two entries in the beams are equal.) During computation the constructed numbers Aand B should never be equal (except for the special case that X only contains the same digit.)

Here are the beams for the second example. The * denotes the best beam, and no * means that both are equally good:

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

This is for the first example:

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

Third example needs a beam size of 3 for second step, because the distance of second best beams 1900 and 2100 to 2000 is 100:

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

Note: I've joined the 3. and the 4. step in all examples.

The numbers X = 1992and Y = 2000 are an interesting example

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

because the best beam is changing during computation.

I wrote a small python program for demonstration:

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]

The code is not optimal but this algorithm has polynomial running time, O(n² ln n) at most, and this estimate is very generous.