Как найти эффективно, если кортеж является подмножеством другого - PullRequest
Новая
       7

Как найти эффективно, если кортеж является подмножеством другого

0 голосов
/ 12 июня 2018

Я знаю о реализации set, и это здорово.Тем не менее, он имеет огромное ограничение: он не может иметь дело с повторением элемента.

Давайте работать с целыми числами: 

tuple1 = (100, 100, 375)
layer = [(100, 100, 100, 375), (20, 100, 100, 375), (20, 20, 100, 375), (20, 20, 20, 375), (20, 20, 30, 375), (20, 20, 40, 375), (20, 20, 50, 375), (20, 20, 60, 375), (20, 20, 70, 375), (20, 20, 80, 375), (20, 30, 100, 375), (20, 30, 30, 375), (20, 30, 40, 375), (20, 30, 50, 375), (20, 30, 60, 375), (20, 30, 70, 375), (20, 30, 80, 375), (20, 40, 100, 375), (20, 40, 40, 375), (20, 40, 50, 375), (20, 40, 60, 375), (20, 40, 70, 375), (20, 40, 80, 375), (20, 50, 100, 375), (20, 50, 50, 375), (20, 50, 60, 375), (20, 50, 70, 375), (20, 50, 80, 375), (20, 60, 100, 375), (20, 60, 60, 375), (20, 60, 70, 375), (20, 60, 80, 375), (20, 70, 100, 375), (20, 70, 70, 375), (20, 70, 80, 375), (20, 80, 100, 375), (20, 80, 80, 375), (30, 100, 100, 375), (30, 30, 100, 375), (30, 30, 30, 375), (30, 30, 40, 375), (30, 30, 50, 375), (30, 30, 60, 375), (30, 30, 70, 375), (30, 30, 80, 375), (30, 40, 100, 375), (30, 40, 40, 375), (30, 40, 50, 375), (30, 40, 60, 375), (30, 40, 70, 375), (30, 40, 80, 375), (30, 50, 100, 375), (30, 50, 50, 375), (30, 50, 60, 375), (30, 50, 70, 375), (30, 50, 80, 375), (30, 60, 100, 375), (30, 60, 60, 375), (30, 60, 70, 375), (30, 60, 80, 375), (30, 70, 100, 375), (30, 70, 70, 375), (30, 70, 80, 375), (30, 80, 100, 100), (30, 80, 100, 375), (30, 80, 80, 375), (40, 100, 100, 375), (40, 40, 100, 375), (40, 40, 40, 375), (40, 40, 50, 375), (40, 40, 60, 375), (40, 40, 70, 375), (40, 40, 80, 375), (40, 50, 100, 375), (40, 50, 50, 375), (40, 50, 60, 375), (40, 50, 70, 375), (40, 50, 80, 375), (40, 60, 100, 375), (40, 60, 60, 375), (40, 60, 70, 375), (40, 60, 80, 375), (40, 70, 100, 375), (40, 70, 70, 375), (40, 70, 80, 375), (40, 80, 100, 375), (40, 80, 80, 375), (50, 100, 100, 375), (50, 50, 100, 375), (50, 50, 50, 375), (50, 50, 60, 375), (50, 50, 70, 375), (50, 50, 80, 375), (50, 50, 80, 80), (50, 60, 100, 375), (50, 60, 60, 375), (50, 60, 70, 375), (50, 60, 80, 375), (50, 70, 100, 375), (50, 70, 70, 375), (50, 70, 70, 80), (50, 70, 80, 375), (50, 80, 100, 375), (50, 80, 80, 375), (50, 80, 80, 80), (60, 100, 100, 375), (60, 60, 100, 375), (60, 60, 60, 375), (60, 60, 70, 375), (60, 60, 80, 375), (60, 70, 100, 375), (60, 70, 70, 375), (60, 70, 80, 375), (60, 80, 100, 375), (60, 80, 80, 375), (60, 80, 80, 80), (70, 100, 100, 375), (70, 70, 100, 375), (70, 70, 70, 375), (70, 70, 80, 375), (70, 80, 100, 100), (70, 80, 100, 375), (70, 80, 80, 375), (80, 100, 100, 375), (80, 80, 100, 375), (80, 80, 80, 100), (80, 80, 80, 375)]

Я хочу сохранить элементы в layer, чтоне сделаны из подмножества tuple1.то есть, например, 2 первых должны быть пропущены.

Прямо сейчас я использую цикл for: 

new_layer = list()
for elt in layer:
    copy = list(elt)
    for x in tuple1:
        if x in copy:
            copy.remove(x)
    if len(copy) == 1:
        continue
    else:
        new_layer.append(elt)

Там будет лучшее решение, чем это ..Более того, последняя проблема на самом деле более сложная.

У меня есть 5 слоев:

  • layer1: элементы len: 2
  • layer2: элементы len: 3
  • layer3: элементы len: 4
  • layer4: элементы len: 5
  • layer5: элементы len: 6

Цель состоит в том, чтобы избавиться в слое N от элементов, которые являются производными (сделаны из подмножества) слоя N-k.

Спасибо за помощь:)

1 Ответ

0 голосов
/ 12 июня 2018

Вот один из способов: создать подкласс Counter и реализовать __contains__ (для оператора in): 

from collections import Counter
class TupleCounter(Counter):
    def __init__(self, t):
        super().__init__(t)

    def __contains__(self, other):
        if not isinstance(other, self.__class__):
            other = self.__class__(other)

        for (v,c) in other.items():
            if self.get(v,0) < c:
                return False

        return True

Пример: 

needle = (100, 100, 375)
layer = [(100, 100, 100, 375), (20, 100, 100, 375), (20, 20, 100, 375), (20, 20, 20, 375), (20, 20, 30, 375), (20, 20, 40, 375), (20, 20, 50, 375), (20, 20, 60, 375), (20, 20, 70, 375), (20, 20, 80, 375), (20, 30, 100, 375), (20, 30, 30, 375), (20, 30, 40, 375), (20, 30, 50, 375), (20, 30, 60, 375), (20, 30, 70, 375), (20, 30, 80, 375), (20, 40, 100, 375), (20, 40, 40, 375), (20, 40, 50, 375), (20, 40, 60, 375), (20, 40, 70, 375), (20, 40, 80, 375), (20, 50, 100, 375), (20, 50, 50, 375), (20, 50, 60, 375), (20, 50, 70, 375), (20, 50, 80, 375), (20, 60, 100, 375), (20, 60, 60, 375), (20, 60, 70, 375), (20, 60, 80, 375), (20, 70, 100, 375), (20, 70, 70, 375), (20, 70, 80, 375), (20, 80, 100, 375), (20, 80, 80, 375), (30, 100, 100, 375), (30, 30, 100, 375), (30, 30, 30, 375), (30, 30, 40, 375), (30, 30, 50, 375), (30, 30, 60, 375), (30, 30, 70, 375), (30, 30, 80, 375), (30, 40, 100, 375), (30, 40, 40, 375), (30, 40, 50, 375), (30, 40, 60, 375), (30, 40, 70, 375), (30, 40, 80, 375), (30, 50, 100, 375), (30, 50, 50, 375), (30, 50, 60, 375), (30, 50, 70, 375), (30, 50, 80, 375), (30, 60, 100, 375), (30, 60, 60, 375), (30, 60, 70, 375), (30, 60, 80, 375), (30, 70, 100, 375), (30, 70, 70, 375), (30, 70, 80, 375), (30, 80, 100, 100), (30, 80, 100, 375), (30, 80, 80, 375), (40, 100, 100, 375), (40, 40, 100, 375), (40, 40, 40, 375), (40, 40, 50, 375), (40, 40, 60, 375), (40, 40, 70, 375), (40, 40, 80, 375), (40, 50, 100, 375), (40, 50, 50, 375), (40, 50, 60, 375), (40, 50, 70, 375), (40, 50, 80, 375), (40, 60, 100, 375), (40, 60, 60, 375), (40, 60, 70, 375), (40, 60, 80, 375), (40, 70, 100, 375), (40, 70, 70, 375), (40, 70, 80, 375), (40, 80, 100, 375), (40, 80, 80, 375), (50, 100, 100, 375), (50, 50, 100, 375), (50, 50, 50, 375), (50, 50, 60, 375), (50, 50, 70, 375), (50, 50, 80, 375), (50, 50, 80, 80), (50, 60, 100, 375), (50, 60, 60, 375), (50, 60, 70, 375), (50, 60, 80, 375), (50, 70, 100, 375), (50, 70, 70, 375), (50, 70, 70, 80), (50, 70, 80, 375), (50, 80, 100, 375), (50, 80, 80, 375), (50, 80, 80, 80), (60, 100, 100, 375), (60, 60, 100, 375), (60, 60, 60, 375), (60, 60, 70, 375), (60, 60, 80, 375), (60, 70, 100, 375), (60, 70, 70, 375), (60, 70, 80, 375), (60, 80, 100, 375), (60, 80, 80, 375), (60, 80, 80, 80), (70, 100, 100, 375), (70, 70, 100, 375), (70, 70, 70, 375), (70, 70, 80, 375), (70, 80, 100, 100), (70, 80, 100, 375), (70, 80, 80, 375), (80, 100, 100, 375), (80, 80, 100, 375), (80, 80, 80, 100), (80, 80, 80, 375)]

needle = TupleCounter(needle)
filtered = [t for t in layer if needle in TupleCounter(t)]
print(filtered)

Вывод: 

[(100, 100, 100, 375), 
 (20, 100, 100, 375), 
 (30, 100, 100, 375), 
 (40, 100, 100, 375), 
 (50, 100, 100, 375), 
 (60, 100, 100, 375), 
 (70, 100, 100, 375), 
 (80, 100, 100, 375)
]

Редактировать: Обратите внимание, что это касается только частоты значений в кортеже, а не их относительного положения внутри него.Таким образом, он также будет соответствовать (375 100 100), даже если элементы кортежа расположены в обратном порядке.

...