制限より小さい数字の順列で可能な最大数を見つける

Question

結果が最大の置換であるようにintの数字を並べ替える必要があります。これは、簡単に次のように行われます。

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

しかし、入力がInt32.MaxValueと同じ桁数を持ち、少なくとも1つの高数字が含まれている場合、この数字は、最初の位置は結果>Int32.MaxValueを作り、大手に行きますintに変換するときに例外になります。

結果を< = Int32.MaxValueに制限するにはどうすればよいでしょうか？この制限内でも最大限の順列が可能ですか？

N.B.ネガティブ番号-1234567890が可能である。 負入力の場合に、-符号は廃棄されるべきである：-1234567890は2147398650出力

Answer 1

数字が小さい場合は（1000000000以下）、d o通常どおりの事業。 10億 よりも多い数のために、あなたは以下のアプローチを試すことができます。

1. あなたが行うとやって続けることができる最大数を入れて、限り、それが不可能な場合には、それは
2. 可能だとしてint.MaxValueパターン（2147483647）に追従してみ残りの桁の通常のビジネス。 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 
   

   実装与え例えば

、

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

テスト：

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

Answer 2

を生成する必要があり、私はこれを示唆している：

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：

を負の数をサポートするために、inputDigitsを定義するとき.Replace("-", String.Empty)挿入