Сравнение двух наборов кортежей A и B для определения совместимости по размеру - PullRequest
Новая
       6

Сравнение двух наборов кортежей A и B для определения совместимости по размеру

2 голосов
/ 02 апреля 2019

Предположим, у нас есть n типов кроватей, и было опрошено n человек.Пусть B = {b1,.,,, bn} - набор из n точек в 2-мерном пространстве, представляющий размеры типов слоев.Запишем bi = (bi (x), bi (y)), где bi (x) представляет длину слоя типа i, а bi (y) его ширину.Точно так же мы представляем требования n человек с P = {p1,.,,, pn}, набор из n точек в 2-мерном пространстве, и мы также пишем pj = (pj (x), pj (y)), где pj (x) и pj (y) являются требованиями длины и ширины человека j,соответственно.Точка bi совместима с точкой pj тогда и только тогда, когда bi (x) ≥ pj (x) и bi (y) ≥ pj (y).Совместимость bi - это число точек P, с которыми оно совместимо, и мы пишем comp (bi) = k, если оно совместимо с k точками p.

Начнем с более простого 1-мерногослучай, то есть P = {p1,.,,, pn} и B = {b1,.,,, bn} - точки в одномерном пространстве (несколько точек могут иметь одинаковое значение).Ваша задача - разработать алгоритм времени O (n log n), который вычисляет совместимость каждой точки в B с P.

Я думал об использовании бинарного поиска, чтобы найти индекс, значение которого Bбольше, чем значения P (отсортировано), и это местоположение индекса +1 должно быть числом людей, совместимых с кроватью, которую я ищу.Я использую цикл for для перебора наборов кортежей, представляющих слои, и двоичного поиска по каждому набору P, чтобы найти индекс и распечатать на каждом последнем шаге для вывода.

def binarySearch(arr,l,r,x):

    if r >= 1: #base case size must be greater or equal to 1

        mid = (r-1)//2 + 1
        if float(arr[mid][1] == float(x)) and float(arr[mid+1][1] == float(x)) and mid <= r-1:
            mid += 1    
        elif float(arr[mid][1]) <= float(x) and float(arr[mid+1][1]) > float(x):
            return mid
        if float(arr[mid][1]) >= float(x):
    #   if arr[mid][1] <= x:
            return binarySearch(arr,l,mid-1,x)
        else:
            return binarySearch(arr,mid+1,r,x)
    else:
        return -1


for i in range(len(b)): #p is set of sorted persons and b is set of beds

    x = b[i][1]

    numCompatible = binarySearch(p,0,len(p),x) + 1

    print(b[i][0],numCompatible)

Я получаю сообщение об ошибке:

"RecursionError: превышена максимальная глубина рекурсии по сравнению" с ожидаемым выходным значением, равным b1 10 b10 5 b11 11 b12 5 b13 5 b14 15b15 13 b16 5 b2 3 b3 9 b4 10 b5 12 b6 9 b7 10 b8 4 b9 3

...