Finding the largest possible number in permutations of digits less than a limit

Question

I want to permute the digits of an int in a way that the result is the biggest possible permutation. This is easily done like this:

//how to deal with really large ints e.g.int32.MaxValue goes here 
// in this case the algorithm would need to round down to the largest possible value 
// but still needs to be less than int32.MaxValue 
//This code will just handle normal values <int32.MaxValue 
public static int Max(int number)
{
    var numberAsCharArray = number.ToString().OrderByDescending(c => c).ToArray();
    var largestNumberAsString = new string(numberAsCharArray);
    return Int32.Parse(largestNumberAsString);
}

However, when the input has the same number of digits as Int32.MaxValue and contains at least one high digit, this digit will go to the first position making the result > Int32.MaxValue and leading to an exception when converting to int.

How could I limit the result to be <= Int32.MaxValue but within this limit still be the greatest possible permutation?

N.B. Negative numbers, e.g. -1234567890 are allowed as well as positive ones; in case of negative input, - sign should be dropped: -1234567890 should produce 2147398650 output

Answer 1

For small numbers (less or equal to 1000000000) you can do the business as usual; for numbers greater than one billion you can try the follow approach:

1. Try follow int.MaxValue pattern (2147483647) as long as it's possible
2. When it's not possible, put the maximum number you can do and continue doing the business as usual for the remaining digits.

For instance, given 1234567890

  1234567890 <- initial value
  2147483647 <- int.MaxValue pattern
  2147398650 <- solution
      ^
      |
      Here we can't put another 4, we put maximum available - 3

  Remaining digits [56890] we order by descending - "98650" - business as usual

Implementation

private static int Biggest(int value) {
  // Special MinValue case; 
  // we can't do Math.Abs() because of integer overflow
  if (value == int.MinValue)
    return 2147483486;

  string st = value.ToString().Trim('-');

  if (value <= 1000000000 && value >= -1000000000)
    return int.Parse(string.Concat(st.OrderByDescending(c => c)));

  string max = int.MaxValue.ToString();

  List<int> digits = st.Select(c => c - '0').ToList();

  StringBuilder sb = new StringBuilder(9);

  bool exact = true;

  while (digits.Any()) {
    for (int i = 0; i < max.Length; ++i) {
      int digitToFind = max[i] - '0';

      int digitActual;

      digitActual = digits
        .Where(d => !exact || d <= digitToFind)
        .OrderByDescending(d => d)
        .First();

      if (exact)
        exact = digitActual == digitToFind;

      sb.Append(digitActual);

      digits.Remove(digitActual);
    }
  }

  return int.Parse(sb.ToString());
}

Test:

// 2147398650 (for reference: int.MaxValue == 2147483647)
Console.WriteLine(Biggest(1234567890));

Answer 2

I suggest this:

int number = 587;
int maximum = Int32.MaxValue;
var result = "";
if(number == Int32.MinValue)
{
    result = "2147483486";
}
else
{ 
    // create list of available digits removing - sign from the string
    var inputDigits = number.ToString().Replace("-", String.Empty).Select(c => Int32.Parse(new string(c, 1))).ToList();
    var limitDigits = maximum.ToString().Select(c => Int32.Parse(new string(c, 1))).ToList();
    var orderedDigits = inputDigits.OrderByDescending(c => c).ToList();
    int position = 0;
    // we only have to compare to the maximum if we have at least the same amount of digits in the input.
    bool compareValues = limitDigits.Count <= inputDigits.Count;
    // while we have not used all of the digits
    while (orderedDigits.Count > 0)
    {
        // loop over the remaining digits from high to low values
        for (int i = 0; i < orderedDigits.Count; i++)
        {
            // if it is above the digit in the maximum at the corresponding place we may only use it if input is shorter than maximum or if we have already used a lower value in a previous digit.
            if (orderedDigits[i] > limitDigits[position])
            {
                if (compareValues)
                {
                    continue;
                }
            }
            else if (orderedDigits[i] < limitDigits[position])
            {
                // remember that we have already used a lower value
                compareValues = false;
            }
            result += (orderedDigits[i].ToString());
            orderedDigits.RemoveAt(i);
            break;
        }
        position++;
    }
}
var intResult = Int32.Parse(result);

EDIT:

inserted .Replace("-", String.Empty) when defining inputDigits to support negative numbers