Отфильтровать элементы списка на основе их взаимосвязи

Question

Я работаю над интересной проблемой Python:

Учитывая список целых чисел, бактерий и положительной целочисленной константы, K, если два элемента i и j соответствуют критериям, которые:

j < i <= j + K

разработать функцию, чтобы заставить меня остаться и удалить j, и вернуть минимально возможное количество элементов в списке.

Функция: micro_world(bacteria, K)

Например,,

bacteria = [101, 53, 42, 102, 101, 55, 54]
K = 1

Конечный результат должен быть

 [42,102,55] 

, и поэтому должно быть возвращено 3.

Аналогично

micro_world([101, 53, 42, 102, 101, 55, 54], 1) даст мнерезультат 3

micro_world([20, 15, 10, 15, 20, 25], 5) даст мне результат 1

Я думаю об использовании списочного понимания для фильтрации элементов, которые не соответствуют вышеуказанному критерию, следовательно, получаяэлементы я хочу.Но я не уверен, что делать с этим, так как он включает отношения между каждым элементом в списке.

result = [ i for i in bacteria if ... ]

Что я буду использовать для своего оператора if?

Если этоне очень хороший способ, что мне делать вместо этого?

Спасибо.

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

bacteria = [3, 3]

, даже если это всего лишь один фрагмент, результатом будет 2, так как 3!> 3, следовательно, ни один из них не будет удален.

Answer 1

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

bacteria = [101, 53, 42, 102, 101, 55, 54]
K = 1

Сначала мы хотим отсортировать этот список так, чтобы числа были упорядочены по величине:

[102, 101, 101, 55, 54, 53, 42]

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

[[102, 101, 101], [55, 54, 53], [42]]

Наконец, мы подсчитываем количество кусочков и, таким образом, получаем желаемый результат:3.

Код:

def micro_world(bacteria, k):
    # sort the list descendingly
    bacteria = sorted(bacteria, reverse=True)

    # loop over the list but skip all the "swallowed" bacteria
    i = 0
    result = 0
    while i < len(bacteria):
        bacterium_size = bacteria[i]

        # while the difference between the numbers is <= k, the smaller
        # bacterium is swallowed
        bigger_bacterium_exists = False
        while i+1 < len(bacteria):
            difference = bacterium_size - bacteria[i+1]

            # if the difference is too big, it can't be swallowed
            if difference > k:
                break

            # if there are two bacteria of the same size, they can't swallow
            # each other. But if a bigger bacterium exists, it can swallow
            # them both
            if difference == 0 and not bigger_bacterium_exists:
                break

            # all conditions are met, the bacterium is swallowed
            bacterium_size = bacteria[i+1]
            i += 1
            bigger_bacterium_exists = True

        # at this point, the bacterium has swallowed everything it can.
        # Increment the result counter and move on to the next bacterium.
        result += 1
        i += 1

    return result

Answer 2

Вот решение, которое использует numpy:

import numpy as np

def micro_world(bacteria, K):
    # convert bacteria list to a numpy array:
    bacteria = np.asarray(bacteria)

    # sort array and remember the indices used for sorting:
    sarg = np.argsort(bacteria)
    sortedbac = bacteria[sarg]

    # compute differences between adjacent elements:
    diff = np.ediff1d(sortedbac, K + 1)

    # throw away elements that are too close to neighbors
    # (find indices of the elements to keep):
    idx = np.flatnonzero(diff > K)

    # create a new list that meets selection criteria:
    return bacteria[np.sort(sarg[idx])]

---

Вот "чистая" реализация Python:

def micro_world(bacteria, K):
    # sort array and remember the indices used for sorting:
    sarg = [i[0] for i in sorted(enumerate(bacteria), key=lambda x: x[1])]
    sortedbac = [bacteria[i] for i in sarg]

    # compute differences between adjacent elements:
    diff = [j - i for i, j in zip(sortedbac[:-1], sortedbac[1:])] + [K + 1]

    # throw away elements that are too close to neighbors
    # (find indices of the elements to keep):
    idx = [i for i, v in enumerate(diff) if v > K]

    # create a new list that meets selection criteria:
    return [bacteria[i] for i in sorted([sarg[i] for i in idx])]

---

Если вы заинтересованытолько в числе элементов, а не в самих элементах, вы можете изменить, то есть вторую версию, следующим образом:

def micro_world(bacteria, K):
    sortedbac = sorted(bacteria)
    diff = [j - i for i, j in zip(sortedbac[:-1], sortedbac[1:])] + [K + 1]
    return sum(1 for v in diff if v > K)

Тогда версия numpy станет:

def micro_world(bacteria, K):
    return np.sum(np.ediff1d(np.sort(bacteria), K + 1) > K)