Как найти все подмножества из массива, что все элементы в подмножестве, что их абсолютное значение взаимного вычитания меньше, чем 8 в Python?

Question

У меня есть массив или список вроде {17, 24, 25, 33, 38, 42, 50}. Как найти все подмножества из массива или списка, чтобы у всех элементов в подмножестве их абсолютное значение взаимного вычитания было меньше 8? Например, {17, 24, 25}, {38, 42}, {42, 50} являются правильными подмножествами, потому что для всех элементов в подмножестве их абсолютное значение взаимного вычитания меньше 8, но {17, 24,25, 33} не потому что | 33 -17 | больше 8.

Answer 1

Если мы сначала отсортируем массив, то сможем установить стиль скользящего окна.В зависимости от фактического распределения данных, для перечисления требуется квадратичное время.

def subsets(l, max_diff):
    sorted_list = sorted(l)
    for i, low in enumerate(sorted_list):
        for j, high in enumerate(sorted_list[i:], start=i+1):
            if high - low > max_diff:
                break
            yield sorted_list[i:j]

Обратите внимание, что max_diff здесь должно быть 7, если вы хотите установить 8 в качестве отсечки.