Сортировка перед сравнением двух списков

Question

Ну, я не могу понять это неправильное поведение с помощью python.

Я написал код для проверки количества комбинаций в двух массивах, разница которых меньше или равна 1.

Каждый элемент может использоваться только один раз.

c список предназначен для хранения комбинаций для лучшего понимания.

for k in range(0,len(bs)):
    c.append([])
    for l in range(0,len(gs)) :
       if abs(bs[k]-gs[l])<=1 and bs[k]!=-1000 and gs[l]!=-1000:
           c[k].append(bs[k])
           c[k].append(gs[l])
           bs[k]=-1000
           gs[l]=-1000
           count+=1

Для некоторых входов (больших входов) он пропускает несколько комбинаций, нокогда я сортирую массивы перед сравнением, это дает точные результаты.В конце концов, это компьютер, и он не должен пропустить комбинацию, если код верен, что я чувствую.

Пример ввода:

4 1 1 1 3 3 2 5 1 2 1 21 1 1 6 1 3 1 1 1 1 2 4 1 1 4 2 2 8 2 2 1 8 2 4 3 3 8 1 3 2 3 2 1 3 8 2 2 3 1 1 2 2 5 1 4 3 1 1 3 13 1 7 1 1 1 3 2 1 2 2 3 7 2 1 4 3 2 1 1 3 4 1 1 3 5 1 8 4 1 1 1 3 10 2 2 1 2

1 1 5 2 13 22 3 6 12 1 13 8 1 1 16 1 1 5 6 2 4 6 4 2 7 4 1 7 3 3 9 5 3 1 7 4 1 6 6 8 2 2 5 2 3 16 3 6 3 8 6 1 8 1 26 5 3 4 11 3 4 8 2 13 2 5 2 7 3 3 1 8 1 4 4 2 4 7 7 1 5 7 6 3 6 9 1 1 1 3 1 11 5 2 5 11 13 1

без сортировки: 74 с сортировкой: 76

комбинаций без сортировки: т.е. 74 [[4, 5], [1, 1], [1, 1], [1, 2], [3,2], [3, 2], [2, 3], [5, 6], [1, 1], [2, 1], [1, 1], [2, 1], [1, 1], [1, 2], [1, 2], [6, 5], [1, 1], [3, 4], [1, 1], [1, 1], [1, 2], [1, 2], [2, 3], [4, 4], [1, 2], [1, 1], [4, 4], [2, 3], [2, 3], [8,8], [2, 3], [2, 3], [1, 1], [8, 7], [2, 3], [4, 5], [3, 4], [3, 2], [8, 7], [1, 2], [3, 3], [2, 3],[3, 4], [2, 2], [1, 2], [3, 4], [8, 9], [2, 3], [2, 3], [3, 4], [1, 1], [1, 1], [2, 2], [2, 1], [5, 6], [1, 1], [4, 5], [3, 4], [1, 1], [1, 1], [3, 4], [1, 1], [3, 3], [1, 2], [7, 6], [1, 1], [], [],[3, 3], [], [], [], [], [], [7, 7], [], [], [4, 5], [], [], [], [], [], [4, 5], [], [], [], [5, 6], [], [8, 8], [4, 5], [], [], [], [], [10, 11], [], [], [], []]

комбинаций с сортировкой: например, 76 [[1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1, 1], [1,1], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [1, 2], [], [], [], [], [], [2, 3], [2, 3], [2, 3], [2, 3], [2, 3], [2, 3], [2, 3], [2, 3],[2, 3], [2, 3], [2, 3], [2, 3], [2, 3], [], [], [], [], [], [], [], [], [], [], [3, 4], [3, 4], [3, 4], [3, 4], [3, 4], [3, 4], [3, 4], [3, 4], [3, 4], [], [], [], [], [], [], [], [], [], [4, 5], [4,5], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [5, 5], [5, 6], [5, 6], [6, 6], [7, 6], [7, 6], [8, 7], [8, 7], [8, 7], [8, 7], [8, 7], [10, 9]]

Спасибо за любые советы.

Answer 1

Вывод вашего алгоритма зависит от порядка, в котором представлены элементы. Например, он разбивается на:

bs = [2, 4]
gs = [3, 1]

Что здесь происходит, так это то, что 2 забирают 3, в результате чего получается только одно совпадение.

Если, с другой стороны, 2 были сопоставлены с 1, то 3 можно сопоставить с 4, что дает два совпадения.

Сортировка по крайней мере в некоторой степени заботится об этом, следя за тем, чтобы вначале использовались наименьшие подходящие числа. Для меня не совсем очевидно, что этого достаточно, чтобы гарантировать оптимальность (хотя, скорее всего, так и есть); об этом нужно немного подумать.

Answer 2

Просто примените стандартную технику отладки: уменьшайте и уменьшайте списки, следя за тем, чтобы вывод оставался неожиданным.

Это неожиданное поведение можно воспроизвести с помощью списков размера 2.

Сравните [2,1] с [2,3].

Кроме того, запустите ваш алгоритм вручную, используя ручку и бумагу. Убедитесь, что вы точно придерживаетесь алгоритма. А если вы хотите сделать что-то другое, выясните, почему и в каких ситуациях.