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

Ответ 1

Функциональная функция Python обеспечивает это set.issubset. У этого есть несколько ограничений, которые не позволяют понять, действительно ли это ответ на ваш вопрос.

Список может содержать элементы несколько раз и имеет определенный порядок. В наборе нет. Для достижения высокопроизводительных наборов работают только объекты hashable.

Вы спрашиваете о подмножестве или подпоследовательности (что означает, что вам нужен алгоритм строкового поиска)? Будет ли один из списков одинаковым для многих тестов? Каковы типы данных, содержащиеся в списке? И в этом отношении, нужно ли быть списком?

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

Ответ 2

>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>> 
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

Ответ 3

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

all(x in two for x in one)

Объяснение: Генератор, создающий логические значения, путем циклического перехода по списку one, проверяя, находится ли этот элемент в списке two. all() возвращает True, если каждый элемент правдивый, else False.

Также существует преимущество, заключающееся в том, что all возвращает False в первом экземпляре отсутствующего элемента, а не обрабатывать каждый элемент.

Ответ 4

Предполагая, что элементы хешируются

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

Если вам не нужны повторяющиеся элементы, например. [1, 2, 2] и [1, 2], то просто используйте:

>>> set([1, 2, 2]).issubset([1, 2])
True

Является ли тестирование равенства в меньшем списке после пересечения самым быстрым способом для этого?

.issubset будет самым быстрым способом сделать это. Проверка длины перед тестированием issubset не улучшит скорость, потому что у вас все еще есть элементы O (N + M) для повторения и проверки.

Ответ 5

Еще одно решение - использовать intersection.

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one).intersection(set(two)) == set(one)

Пересечение множеств будет содержать set one

(ИЛИ)

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one) & (set(two)) == set(one)

Ответ 6

Я знаю, что уже поздно, но просто хотел обновить ответ тем, что у меня сработало (Python 3)

# var 1
x = [1,2,3,4]
#  var 2
y = [1,2]

# check if var2 is subset of var1
all([z in x for z in y])

Приветствия.

Ответ 7

Попробуйте побитовое И

>>> set([1,2]) & set([1,2,3])
set([1, 2])
>>> set([0]) & set([1,2,3])
set([])

Пока не профилировал его.

Ответ 8

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(x in two for x in one) == set([True])

Если list1 находится в списке 2:

• (x in two for x in one) генерирует список True.

• когда мы делаем set(x in two for x in one), имеет только один элемент (True).

Ответ 9

Теория множеств не подходит для списков, поскольку дубликаты приводят к неправильным ответам с использованием теории множеств.

Например:

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
set(b) > set(a)

не имеет значения. Да, это дает ложный ответ, но это неверно, поскольку теория множеств просто сравнивает: 1,3,5 против 1,3,4,5. Вы должны включить все дубликаты.

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

#!/usr/bin/env python

from collections import Counter

def containedInFirst(a, b):
  a_count = Counter(a)
  b_count = Counter(b)
  for key in b_count:
    if a_count.has_key(key) == False:
      return False
    if b_count[key] > a_count[key]:
      return False
  return True


a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

a = [1, 3, 3, 3, 4, 4, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

Затем запустите это:

$ python contained.py 
b in a:  False
b in a:  True

Ответ 10

Простите меня, если я опаздываю на вечеринку.;)

Чтобы проверить, является ли один set A подмножеством set B, Python имеет A.issubset(B) и A <= B. Он работает только с set и отлично работает НО, сложность внутренней реализации неизвестна. Ссылка: https://docs.python.org/2/library/sets.html#set-objects

Я придумал алгоритм для проверки, является ли list A подмножеством list B со следующими замечаниями.

• Чтобы уменьшить сложность поиска подмножества, я считаю sort оба списка сначала перед сопоставлением элементов для квалификации подмножество.
• Это помогло мне break loop, когда значение элемента второго списка B[j] больше значения элемента первого списка A[i].
• last_index_j используется для запуска loop над list B, где он последний раз останавливался. Это помогает избежать начальных сравнений с начала list B (который, как вы можете предположить, не нужно, начинать list B с index 0 в последующем iterations.)

• Сложность будет O(n ln n) для сортировки обоих списков и O(n) для проверки подмножества.
  O(n ln n) + O(n ln n) + O(n) = O(n ln n).

• В коде есть много операторов print, чтобы узнать, что происходит на каждом iteration loop. Они предназначены для понимания только.

Проверить, является ли один список подмножеством другого списка

is_subset = True;

A = [9, 3, 11, 1, 7, 2];
B = [11, 4, 6, 2, 15, 1, 9, 8, 5, 3];

print(A, B);

# skip checking if list A has elements more than list B
if len(A) > len(B):
    is_subset = False;
else:
    # complexity of sorting using quicksort or merge sort: O(n ln n)
    # use best sorting algorithm available to minimize complexity
    A.sort();
    B.sort();

    print(A, B);

    # complexity: O(n^2)
    # for a in A:
    #   if a not in B:
    #       is_subset = False;
    #       break;

    # complexity: O(n)
    is_found = False;
    last_index_j = 0;

    for i in range(len(A)):
        for j in range(last_index_j, len(B)):
            is_found = False;

            print("i=" + str(i) + ", j=" + str(j) + ", " + str(A[i]) + "==" + str(B[j]) + "?");

            if B[j] <= A[i]:
                if A[i] == B[j]:
                    is_found = True;
                last_index_j = j;
            else:
                is_found = False;
                break;

            if is_found:
                print("Found: " + str(A[i]));
                last_index_j = last_index_j + 1;
                break;
            else:
                print("Not found: " + str(A[i]));

        if is_found == False:
            is_subset = False;
            break;

print("subset") if is_subset else print("not subset");

Выход

[9, 3, 11, 1, 7, 2] [11, 4, 6, 2, 15, 1, 9, 8, 5, 3]
[1, 2, 3, 7, 9, 11] [1, 2, 3, 4, 5, 6, 8, 9, 11, 15]
i=0, j=0, 1==1?
Found: 1
i=1, j=1, 2==1?
Not found: 2
i=1, j=2, 2==2?
Found: 2
i=2, j=3, 3==3?
Found: 3
i=3, j=4, 7==4?
Not found: 7
i=3, j=5, 7==5?
Not found: 7
i=3, j=6, 7==6?
Not found: 7
i=3, j=7, 7==8?
not subset

Ответ 11

Ниже код проверяет, является ли данный набор "правильным подмножеством" другого набора

 def is_proper_subset(set, superset):
     return all(x in superset for x in set) and len(set)<len(superset)

Ответ 12

В Python 3.5 вы можете сделать [*set()][index] чтобы получить элемент. Это гораздо более медленное решение, чем другие методы.

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

result = set(x in two for x in one)

[*result][0] == True

или просто с лен и установить

len(set(a+b)) == len(set(a))

Ответ 13

issubset и все другие операции над множествами здесь, где "s" и "t" представляют два набора.

Ответ 14

Вот как я узнаю, если один список является подмножеством другого, в моем случае последовательность имеет значение для меня.

def is_subset(list_long,list_short):
    short_length = len(list_short)
    subset_list = []
    for i in range(len(list_long)-short_length+1):
        subset_list.append(list_long[i:i+short_length])
    if list_short in subset_list:
        return True
    else: return False

Ответ 15

Если вы спрашиваете, содержится ли один список в другом списке, выполните следующие действия:

>>>if listA in listB: return True

Если вы спрашиваете, имеет ли каждый элемент в списке A равное количество совпадающих элементов в listB, выполните следующие действия:

all(True if listA.count(item) <= listB.count(item) else False for item in listA)

Ответ 16

Если a2 is subset of a1, то Length of set(a1 + a2) == Length of set(a1)

a1 = [1, 2, 3, 4, 5];
a2 = [1, 2, 3];

len(set(a1)) == len(set(a1 + a2))