упорядочить числа, чтобы сформировать наибольшее число-доказательство алгоритма

Существует хорошо известная алгоритмическая Задача , заданная массивом чисел, например[1, 20, 3, 14] упорядочить числа таким образом, чтобы они образовывали наибольшее возможное число, в данном случае 320141.

Существует множество решений на SO и других сайтах, использующих следующий алгоритм: 

String[] strs = new String[nums.length];
for(int i=0; i<nums.length; i++){
    strs[i] = String.valueOf(nums[i]);
}

Arrays.sort(strs, new Comparator<String>(){
    public int compare(String s1, String s2){
        String leftRight = s1+s2;
        String rightLeft = s2+s1;
        return -leftRight.compareTo(rightLeft);

    }
});

StringBuilder sb = new StringBuilder();
for(String s: strs){
    sb.append(s);
}

return sb.toString();
Это, конечно, работает, но я не могу найти формального доказательства этого алгоритма. Есть один ответ наquora , но я бы не назвал его формальным доказательством.

Может ли кто-нибудь дать мне набросок доказательство или ссылка на какую-нибудь книгу или статью? Как можно выйти на это решение из исходной задачи?

Я пытался решить исходную задачу, но мое решение было неправильным, я не мог получить его правильно, и теперь я не мог полностью понять решение.
2 4
algorithm proof

2 ответа:

Что касается нотации: я буду использовать трубы для разделения чисел, так что это легче увидеть последовательность чисел и результирующее число на то же время: 3/20/14/1

Предположим на данный момент, что отношение-назовем его R представлен оператором <=, который определяется сравнением функция-это тотальный порядок. Она определяется выражением 

-(a+b).compareTo(b+a)
Интуитивно он говорит, что если у нас есть два числа a и b и b / a является больше, чем a|b, b должен получить более высокий ранг, чем a , т. е. встречаются слева от a в решении. Если a|b больше, чем b / a, то все наоборот круглый. Если a|b = b / a , Порядок не имеет значения.

Важно отметить, что это отношение не только влияет на два числа a и b рассматриваются изолированно, но также говорят нам кое-что о получившемся числе два числа встроены в:

Если a, то x|a / b / y x / b / a / y

С x и y , являющимися числами произвольные длины. Другими словами: если у нас есть последовательность чисел и мы поменяем местами два соседних числа a и b с a, в результате чего число будет больше или равно впоследствии.

Пример: 3/14/20/1 потому что 14

Теперь мы можем возглавить предположение, что решение не является единственным подразумевается нашим отношением R к противоречию: предположим, что решением является некоторая определенная последовательность, не соответствующая R . Так как R является полный порядок, мы можем переставить числа, чтобы соответствовать R путем замены соседние элементы до тех пор, пока порядок не будет соответствовать R. Такое изменение может можно сравнить с видом пузыря. Однако в каждой операции подкачки это приводит нас к новому порядку, в результате число увеличивается! Этот является очевидно противоречие, поэтому первоначальный порядок не может быть решение.

Остается только показать, что R является полным порядком, т. е. транзитивным, антисимметричным и общая. С тех пор, как вы попросили эскиз доказательство, я опущу эту часть. Существенной частью является доказательство транзитивность, то есть что

a и b подразумевает a .

2

Вот набросок алгоритма. Для вашего данного списка: 

[1, 20, 3, 14]
Подумайте о том, как бы вы нашли наибольшее сцепленное число.

Для наиболее значимой цифры выберите число с наибольшей начальной цифрой. (В Примере выберите 3, а затем 20. Таким образом, ответ начинается с 320.)

Остальные числа, 1 и 14, начинаются с той же начальной цифры (а именно 1). Что выбрать дальше? Именно здесь вступает в действие сердце алгоритма-функция compare. играть. Он будет строить числа и сравнивать, какое из них лексически больше, то есть 114 против 141. Отрицательный знак в выражении return гарантирует, что большее число идет первым. Таким образом, ответ будет 320141.

(На самом деле алгоритм не сравнивает начальные цифры, а, скорее, сортирует строки от лексически наибольших до наименьших.)

2