한 목록이 다른 목록의 하위 집합인지 어떻게 확인할 수 있습니까?

한 목록이 다른 목록의 하위 집합인지 어떻게 확인할 수 있습니까?

---

목록이 다른 목록의 하위 집합인지 확인해야합니다. 부울 리턴 만 있으면됩니다.

교차 후 작은 목록에서 동등성을 테스트하는 것이 가장 빠른 방법입니까? 비교해야 할 데이터 세트의 수를 고려할 때 성능이 가장 중요합니다.

토론을 기반으로 추가 사실 추가 :

1. 많은 테스트에서 목록 중 하나가 동일합니까? 정적 조회 테이블 중 하나이므로 수행합니다.

2. 목록이어야합니까? 정적 조회 테이블은 성능이 가장 좋은 것이 될 수 있습니다. 동적은 정적 조회를 수행하기 위해 키를 추출하는 명령입니다.

시나리오를 고려할 때 최적의 솔루션은 무엇입니까?

---

파이썬이이를 위해 제공하는 수행자 함수는 set.issubset 입니다. 그러나 귀하의 질문에 대한 답변인지 확실하지 않은 몇 가지 제한 사항이 있습니다.

목록에는 항목이 여러 번 포함될 수 있으며 특정 주문이 있습니다. 세트는하지 않습니다. 고성능 세트를 달성하려면 해시 가능 오브젝트에서만 작동 합니다.

서브 세트 또는 서브 시퀀스에 대해 질문하고 있습니까 (즉, 문자열 검색 알고리즘이 필요함)? 많은 테스트에서 목록 중 하나가 동일합니까? 목록에 포함 된 데이터 유형은 무엇입니까? 그리고 그 문제에 대해 목록이 필요합니까?

다른 게시물 은 dict과 교차하고 목록 이 유형을 더 명확하게 만들고 세트와 같은 기능을 위해 사전 키보기를 사용하도록 권장했습니다. 이 경우 사전 키가 집합처럼 동작하기 때문에 작동하는 것으로 알려져 있습니다 (파이썬에서 집합을 사용하기 전에 사전을 사용 했음). 세 시간 동안 문제가 어떻게 구체적이지 않은지 궁금합니다.

---

>>> 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가 해당 항목이 list에 있는지 여부를 점검 하여 목록을 반복하여 부울을 작성 합니다 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)

---

나는 그것의 늦었지만 알았지 만 답을 업데이트하고 싶었습니다 (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])

건배.

---

비트 AND를 시도하십시오

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

아직 프로필을 작성하지 않았습니다.

---

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

---

파티에 늦었다면 용서해주세요 ;)

하나가 있는지 확인하려면 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.

• To reduce complexity of finding subset, I find it appropriate to sort both lists first before comparing elements to qualify for subset.
• It helped me to break the loop when value of element of second list B[j] is greater than value of element of first list A[i].
• last_index_j is used to start loop over list B where it last left off. It helps avoid starting comparisons from the start of list B (which is, as you might guess unnecessary, to start list B from index 0 in subsequent iterations.)

• Complexity will be O(n ln n) each for sorting both lists and O(n) for checking for subset.
  O(n ln n) + O(n ln n) + O(n) = O(n ln n).

• Code has lots of print statements to see what's going on at each iteration of the loop. These are meant for understanding only.

Check if one list is subset of another list

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");

Output

[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

---

Below code checks whether a given set is a "proper subset" of another set

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

---

In python 3.5 you can do a [*set()][index] to get the element. It is much slower solution than other methods.

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

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

[*result][0] == True

or just with len and set

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

---

Here is how I know if one list is a subset of another one, the sequence matters to me in my case.

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

---

If you are asking if one list is "contained" in another list then:

>>>if listA in listB: return True

If you are asking if each element in listA has an equal number of matching elements in listB try:

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

---

If a2 is subset of a1, then 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))

참고URL : https://stackoverflow.com/questions/16579085/how-can-i-verify-if-one-list-is-a-subset-of-another