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

Существует хорошо известная алгоритмическая проблема с заданным массивом чисел, например. [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 есть один ответ, но я бы не назвал его формальным доказательством.

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

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


algorithm proof
person csharpfolk    schedule 05.01.2016    source источник
comment
ответ на квору кажется мне довольно формальным, хотя на самом деле это всего лишь набросок. что еще ты хочешь?   -  person cobarzan    schedule 05.01.2016
comment
cobarzan Я пытался следовать quora proof, но не могу получить некоторые шаги, может быть, мне нужно что-то более формальное или с небольшими шагами.   -  person csharpfolk    schedule 05.01.2016

Ответы (2)


arrow_upward
3
arrow_downward

Относительно обозначений: я буду использовать вертикальные черты для разделения чисел, чтобы было легче одновременно видеть последовательность чисел и результирующее число: 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‹=b, то x|a|b|y ‹= x|b|a|y

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

Пример: 3|14|20|1 ‹= 3|20|14|1, потому что 14 ‹= 20

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

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

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

person lex82    schedule 06.01.2016
comment
Спасибо, простое и понятное доказательство, хотел именно такое! - person csharpfolk; 06.01.2016

arrow_upward
2
arrow_downward

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

[1, 20, 3, 14]

подумайте, как бы вы нашли наибольшее составное число.

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

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

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

person rajah9    schedule 05.01.2016
comment
rajah9 Я попросил доказательство алгоритма, а не объяснение того, как он работает - person csharpfolk; 06.01.2016
comment
Извините, я отвечал на ваше не совсем понятное решение. - person rajah9; 06.01.2016