Given integers X and Y, how do you find the largest permutation of X that is less than or equal to Y-CodePudding

Given two positive integers X and Y, find the largest permutation of X
that is less than or equal to Y. Return the largest permutation that is
less than or equal to Y as an integer. If there is no permutation of X
that is less than or equal to Y, return -1.

Example 1:
Input: X = 123, Y = 321
Output: 321

Example 2:
Input: X = 1733, Y = 3311
Output: 3173

Example 3:
Input: X = 999, Y = 111
Output: -1

Got this problem for an online assessment earlier yesterday, couldn't find an efficient solution for it and have been thinking about it but still can't think of the right approach. I first tried greedy, in which I would iterate Y from left to right and I create a permutation of X by appending the largest digit in X that is less than or equal to the digit in Y. But for X = 1733 and Y = 3311, my implementation would return -1 because the greedy algorithm rearranged X to 3317. So I turned to recursion, but as you'd expect this very quickly reached stack limit.

I've read this thread that seems to discuss a similar problem, but I believe the top solution fails for example 2. How do you approach this problem?

CodePudding user response：

A recursive solution.

Sort the digits of X decreasingly. Then, as long as you find no solution

take in turn every digit in X that is not larger than the leading digit of Y;
- if those digits are equal, recurse on X less this digit and the tail of Y;
- if the digit of X is smaller (or X is empty), you are done;
- if there is no such digit, you reached a dead-end.

This works because you are trying the permutations of X by decreasing value.

321 vs. 321
    3 21 vs. 3 21
        21 vs. 21
            1 vs. 1
                Done

7331 vs. 3311
    3 731 vs. 3 311
        3 71 vs. 3 11
            1 7 vs. 1 1
                Dead end
        1 73 vs. 3 11
            Done

999 vs. 111
    Dead end

A non-recursive efficient solution, hinted by @Stef.

The permutations of X can be ordered increasingly by sorting the digits then picking every first digit and recursing on the remaining ones. This established a bijection between the permutations and the integers in [0, d!) for d digits.

For an integer m, you can retrieve the corresponding permutation using a conversion from the factorial basis (take the quotient by (d-1)! and proceed recursively with the remainder). This takes d operations, and you can compare the permutation to Y in O(d) operations.

Now just implement a dichotomic search on the d! permutations, which takes O(d.log(d!)) = O(d².log(d))) operations.

Update: the second solution only works for distinct digits otherwise the permutations do not yield increasing numbers. I hope that there is a workaround.

CodePudding user response：

If X has more digits then there is no solution. If Y has more digits then a descending sort of the digits of X is the solution. Assuming X and Y have the same number of digits:

Put the digits of X in a counting hash.

For each digit of Y going in descending order (left-to-right), take the max digit of X that isn't greater than it and use that in your permutation.

If you ever place a digit lower than its counterpart in Y, place all remaining digits in descending order.

If there ever isn't a non-greater digit available then do the following: repeatedly unwind your prior move until you get to a digit where a lower digit was available. Select the max such lower digit. Then, all remaining digits can be placed in descending order from the map. If there is no such digit (where a lower digit could have been chosen) then there is no solution.

If you get through all the digits then you've produced the max solution.

This is linear in the number of digits if this is limited to base 10. If your base can vary, this is O(num_digits * base)

Here's Ruby code for this.

def get_perm(x, y)
  # hist keeps a count of each of the digits of x
  hist = Hash.new 0; x.digits.each { |d| hist[d]  = 1 }
  
  # output_digits is the answer we're building
  output_digits = []
  
  y_digits = y.digits
  x_digits = x.digits
  
  # If x has fewer digits then all permutations are good so pick the largest
  if x.digits.length < y.digits.length
    9.downto(0) do |digit|
      output_digits  = [digit] * hist[digit]
    end
    return output_digits
  end
    
  # If y has fewer digits then no permutation is good, return -1
  if y.digits.length < x.digits.length
    return -1
  end

  # parse the digits of y

  (y_digits.length - 1).downto(0) do |i|
    cur_y_digit = y_digits[i]
    
    # use the current digit of y if possible
    if hist[cur_y_digit] > 0
      hist[cur_y_digit] -= 1
      output_digits.append(cur_y_digit)
      return output_digits if i == 0
      
    # otherwise, use the largest smaller digit available if possible
    else
      (cur_y_digit - 1).downto(0) do |smaller_digit|
        if hist[smaller_digit] > 0
          # place the smaller digit, then all remaining digits in descending order
          hist[smaller_digit] -= 1
          output_digits.append(smaller_digit)
          9.downto(0) do |digit|
            output_digits  = [digit] * hist[digit]
          end
          return output_digits
        end
      end
      
      # If we make it here then no digit was available; we need to unwind moves until we
      # can replace a digit of our solution with a smaller digit
      
      smallest_digit = hist.keys.min
      while i < (y.digits.length - 1) do
        i  = 1
        cur_y_digit = y_digits[i]
        cur_unwound_digit = output_digits.pop
        hist[cur_unwound_digit]  = 1
        smallest_digit = [smallest_digit, cur_unwound_digit].min
        if cur_y_digit > smallest_digit
          (cur_y_digit - 1).downto(smallest_digit) do |d|
            if hist[d] >= 1
              output_digits.append(d)
              hist[d] -= 1
              9.downto(0) do |digit|
                output_digits  = [digit] * hist[digit]
              end
              return output_digits
            end
          end
        end
      end
      return -1
    end
  end
end

Outputs for OP sample cases:

> get_perm(123, 321)
=> [3, 2, 1]
> get_perm(1733, 3311)
=> [3, 1, 7, 3]
> get_perm(999, 111)
=> -1

CodePudding user response：

If Z is the answer, and the numbers have n digits, you can show that there is an index i such that Z[:i] = Y[:i], Z[i]<Y[i], and Z[i 1:] is as large as possible given digits of X \ Z[:i 1] (I use python array slice notation, and the last expression means "the set of digits of X minus those already chosen in Z up to i 1").

Given this, you can easily loop over each candidate i, and efficiently check if it's feasible to chose such i as in above. The solution is with the largest possible i.

The solution should be O(n*log(n)).

I'll leave the proof and implementation details, as I understand it's a homework :)