Количество Сравнений с помощью сортировки слиянием
Я не программист asp, очень жаль если я отчитаю что-то: на атрибут маркировки P
для ссылаются к идентификатору входа. Таким образом, необходимо будет сделать что-то как
<input type="radio" name="rad1" id="rad1_1"><label for="rad1_1">Rad1</label>
<input type="radio" name="rad1" id="rad1_2"><label for="rad1_2">Rad2</label>
5 ответов
Мне этот вопрос интересен, поэтому я решил тщательно его изучить (немного поэкспериментировав с Python).
Я загрузил mergesort.py из здесь и модифицировал его, добавив аргумент cmp для функции компаратора. Затем:
import collections
import itertools
import mergesort
import sys
class CountingComparator(object):
def __init__(self):
self.count = 0
def __call__(self, a, b):
self.count += 1
return cmp(a, b)
ms_histo = collections.defaultdict(int)
for perm in itertools.permutations(range(int(sys.argv[1]))):
cc = CountingComparator()
lperm = list(perm)
mergesort.mergesort(lperm, cmp=cc)
ms_histo[cc.count] += 1
for c in sorted(ms_histo):
print "%d %2d" % (c, ms_histo[c])
Результирующая простая гистограмма (начиная с длины 4, как я делал для ее разработки и отладки):
4 8
5 16
Для проблемы, как написано, с длиной 5 вместо 4 я получаю:
5 4
6 20
7 48
8 48
и длиной 6 (и более широким форматом; -):
7 8
8 56
9 176
10 288
11 192
Наконец, длиной 7 (и даже более широким форматом; -):
9 16
10 128
11 480
12 1216
13 1920
14 1280
Конечно, здесь скрывается какая-то совершенно правильная комбинаторная формула, но я Мне трудно оценить, что это может быть, аналитически или внимательно изучая цифры. Есть предложения?
Что мешает вам кодировать сортировку слиянием, сохраняя счетчик для количества сравнений в нем и опробовать его на всех перестановках [0,1,2,3,4]?
Согласно Википедия : В худшем случае сортировка слиянием выполняет количество сравнений, равное или немного меньшее, чем (n lg n⌉ - 2 ^ ⌈lg n⌉ + 1)
При сортировке слиянием двух списков длины L1 и L2, я полагаю, что наихудшее количество сравнений будет L1 + L2-1.
- Изначально у вас есть пять списков длиной 1.
- Вы можете объединить две пары списков с помощью 2 сравнений , в результате чего получатся списки длиной 2,2 и 1.
- Затем вы можете объединить длинный список из 2 и 1 максимум с другим 1 + 2 -1 = 2 сравнения , что дает длинный список из 2 и 3.
- Наконец, вы объединяете эти списки максимум с 2 + 3-1 = 4 сравнениями .
Итак Думаю, ответ - 8.
Эта последовательность чисел приводит к следующему: [2], [4], [1], [3], [5] -> [2,4], [1,3], [5] -> [2,4], [1,3,5] ] -> [1,2,3,4,5]
Изменить:
Вот наивная реализация Erlang. Исходя из этого, количество сравнений составляет 5,6,7 или 8 для перестановок 1..5.
-module(mergesort).
-compile(export_all).
test() ->
lists:sort([{sort(L),L} || L <- permutations()]).
sort([]) -> {0, []};
sort([_] = L) -> {0, L};
sort(L) ->
{L1, L2} = lists:split(length(L) div 2, L),
{C1, SL1} = sort(L1), {C2, SL2} = sort(L2),
{C3, RL} = merge(SL1, SL2, [], 0),
{C1+C2+C3, RL}.
merge([], L2, Merged, Comps) -> {Comps, Merged ++ L2};
merge(L1, [], Merged, Comps) -> {Comps, Merged ++ L1};
merge([H1|T1], [H2|_] = L2, Merged, Comps) when H1 < H2 -> merge(T1, L2, Merged ++[H1], Comps + 1);
merge(L1, [H2|T2], Merged, Comps) -> merge(L1, T2, Merged ++[H2], Comps + 1).
permutations() ->
L = lists:seq(1,5),
[[A,B,C,D,E] || A <- L, B <- L, C <- L, D <- L, E <- L, A =/= B, A =/= C, A =/= D, A =/= E, B =/= C, B =/= D, B =/= E, C =/= D, C =/= E, D =/= E].