어떤 리스트가 다른 리스트의 서브셋인지 확인하려면 어떻게 해야 합니까?

어떤 리스트가 다른 리스트의 서브셋인지 확인하려면 어떻게 해야 합니까?

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

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

논의를 바탕으로 추가 사실 추가:

1. 많은 테스트에서 어느 하나의 리스트가 같습니까?그 중 하나가 스태틱룩업 테이블입니다

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

사용

예제:

a = {1,2}
b = {1,2,3}
a.issubset(b) # True

a = {1,2,4}
b = {1,2,3}
a.issubset(b) # False

---

Python이 제공하는 퍼포먼스 함수는 입니다.다만, 몇 가지 제한이 있기 때문에, 그것이 당신의 질문에 대한 답변인지 아닌지는 불명확합니다.

목록에는 항목이 여러 번 포함될 수 있으며 특정 순서가 지정됩니다.세트에는 없습니다.또한 세트는 해시 가능한 개체에서만 작동합니다.

서브셋과 서브시퀀스 중 어느 쪽을 원하십니까(문자열 검색 알고리즘을 원하십니까)?많은 테스트에서 어느 하나의 리스트가 같습니까?목록에 포함된 데이터 유형은 무엇입니까?그리고 그 문제는 리스트가 필요합니까?

다른 게시물은 dict와 목록과 교차하여 유형이 명확해졌고 사전 키 뷰를 사용하여 집합과 같은 기능을 사용할 것을 권장합니다.이 경우 사전 키가 세트처럼 작동하기 때문에 작동하는 것으로 알려져 있습니다(그래서 Python에 세트가 있기 전에는 사전을 사용했습니다.어떻게 3시간 만에 그 문제가 덜 구체화 되었는지 궁금하다.

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

all(x in two for x in one)

설명:목록을 루핑하여 부울을 생성하는 제너레이터one 이 목록에 two. 반환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을 사용하다 전 issubsetO(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)

집합이론은 중복되면 집합이론을 사용하여 오답이 발생하므로 목록에 적합하지 않습니다.

예를 들어 다음과 같습니다.

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

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

파티에 늦었다면 죄송합니다.;)

를 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둘 다 서브셋에 적합한 요소를 비교하기 전에 먼저 나열됩니다.
• 에게 도움이 .breakloop list 이 「」인 .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 일이 있는지 위한 iterationloop이것들은 단지 이해를 위한 것입니다.

한 목록이 다른 목록의 하위 집합인지 확인합니다.

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)

3.에서는 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

아무도 두 줄을 비교할 생각을 하지 않았기 때문에, 제 제안은 이렇습니다.

물론 파이프("|")가 두 목록의 일부가 아닌지 확인하고 자동으로 다른 문자를 선택할 수도 있지만, 이미 알고 있습니다.

숫자에는 여러 자리([12,3]!= [1,23])가 있을 수 있으므로 빈 문자열을 구분 기호로 사용하는 것은 해결책이 아닙니다.

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

한 목록이 다른 목록에 "포함"되어 있는지 여부를 묻는 경우:

>>>if listA in listB: return True

listA의 각 요소에 listB의 일치하는 요소 수가 동일한지 여부를 확인하는 경우 다음을 수행합니다.

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

대부분의 솔루션은 목록에 중복이 없는 것으로 간주합니다.목록에 중복이 있는 경우 다음을 시도할 수 있습니다.

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

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