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

Мне нужно проверить, является ли список подмножеством другого - булево возвращение - это все, что я ищу.

Является ли тестирование равенства в меньшем списке после пересечения самым быстрым способом сделать это? Производительность имеет первостепенное значение, учитывая количество наборов данных, которые необходимо сравнить.

Добавление дополнительных фактов на основе обсуждений:

1. Будет ли один из списков одинаковым для многих тестов? Это как статическая таблица поиска.

2. Это должен быть список? Это не так - статическая таблица поиска может быть любой, которая работает лучше всего. Динамический - это диктовка, из которой мы извлекаем ключи для статического поиска.

Каково было бы оптимальное решение с учетом сценария?

Исполнительная функция Python обеспечивает это set.issubset. Однако у него есть несколько ограничений, из-за которых неясно, является ли это ответом на ваш вопрос.

Список может содержать элементы несколько раз и имеет определенный порядок. Набор не делает. Кроме того, наборы работают только с хэшируемыми объектами.

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

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

>>> 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

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

all(x in two for x in one)

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

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

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

>>> 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) элементов для итерации и проверки.

Еще одним решением будет использование 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)

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).

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

Например:

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

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

Вы, конечно, можете проверить, не является ли труба («|») частью обоих списков, и, возможно, автоматически выбрали другой символ, но вы поняли идею.

Использование пустой строки в качестве разделителя не является решением, поскольку числа могут иметь несколько цифр ([12,3]! = [1,23])

def issublist(l1,l2):
    return '|'.join([str(i) for i in l1]) in '|'.join([str(i) for i in l2])

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

Чтобы проверить, является ли один 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сначала оба списка, прежде чем сравнивать элементы, чтобы претендовать на подмножество.
• Это помогло мне , когда значение элемента второго списка больше , чем значение элемента из первого списка .breakloopB[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

Код ниже проверяет, является ли данный набор «правильным подмножеством» другого набора

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

В 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))

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

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

Большинство решений считают, что списки не имеют дубликатов. Если в ваших списках есть дубликаты, вы можете попробовать это:

def isSubList(subList,mlist):
    uniqueElements=set(subList)
    for e in uniqueElements:
        if subList.count(e) > mlist.count(e):
            return False     
    # It is sublist
    return True

Это гарантирует, что подсписок никогда не имеет элементов, отличных от списка, или большего количества общего элемента.

lst=[1,2,2,3,4]
sl1=[2,2,3]
sl2=[2,2,2]
sl3=[2,5]

print(isSubList(sl1,lst)) # True
print(isSubList(sl2,lst)) # False
print(isSubList(sl3,lst)) # False

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

>>>if listA in listB: return True

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

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

Если 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))