목록에 Python으로 다른 목록이 포함되어 있는지 테스트하기

목록에 다른 목록이 포함되어 있는지 테스트하려면 어떻게해야합니까 (즉, 인접한 하위 순서). contains라는 함수가 있다고 가정 해보십시오.

contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end])
contains([1,3], [-1, 0, 1, 2]) # Returns False
contains([1, 2], [[1, 2], 3]) # Returns False
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0]

편집하다:

contains([2, 1], [-1, 0, 1, 2]) # Returns False
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]

해결법

==============================
1.여기 내 버전입니다 :

여기 내 버전입니다 :
```
def contains(small, big):
    for i in xrange(len(big)-len(small)+1):
        for j in xrange(len(small)):
            if big[i+j] != small[j]:
                break
        else:
            return i, i+len(small)
    return False
```
그것은 Andrew Jaffe가 그의 코멘트에서 지적한 것처럼 내가 더 pythonic하다고 생각하기 때문에 (시작, 끝 + 1)의 튜플을 반환합니다. 하위 목록을 분할하지 않기 때문에 합리적으로 효율적이어야합니다.

초보자들에게 흥미로운 점 중 하나는 for 문에서 else 절을 사용한다는 것입니다. 이것은 매우 자주 사용하지만 이와 같은 상황에서는 매우 중요 할 수 있습니다.

이것은 문자열에서 하위 문자열을 찾는 것과 동일하므로 큰 목록의 경우 Boyer-Moore 알고리즘을 구현하는 것이 더 효율적일 수 있습니다.
==============================
2.모든 항목이 고유 한 경우 집합을 사용할 수 있습니다.

모든 항목이 고유 한 경우 집합을 사용할 수 있습니다.
```
>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False
```
==============================
3.큰 목록이 정말 큰 경우 Rabin-Karp 알고리즘을 겸허하게 제안해도 될까요? 이 링크는 거의 파이썬에서 거의 쓸만한 코드를 포함합니다.

큰 목록이 정말 큰 경우 Rabin-Karp 알고리즘을 겸허하게 제안해도 될까요? 이 링크는 거의 파이썬에서 거의 쓸만한 코드를 포함합니다.

==============================

4.OP 편집 후 :

OP 편집 후 :

def contains(small, big):
    for i in xrange(1 + len(big) - len(small)):
        if small == big[i:i+len(small)]:
            return i, i + len(small) - 1
    return False

==============================

5.다음은 목록 메서드를 사용하는 간단한 알고리즘입니다.

다음은 목록 메서드를 사용하는 간단한 알고리즘입니다.

#!/usr/bin/env python

def list_find(what, where):
    """Find `what` list in the `where` list.

    Return index in `where` where `what` starts
    or -1 if no such index.

    >>> f = list_find
    >>> f([2, 1], [-1, 0, 1, 2])
    -1
    >>> f([-1, 1, 2], [-1, 0, 1, 2])
    -1
    >>> f([0, 1, 2], [-1, 0, 1, 2])
    1
    >>> f([1,2], [-1, 0, 1, 2])
    2
    >>> f([1,3], [-1, 0, 1, 2])
    -1
    >>> f([1, 2], [[1, 2], 3])
    -1
    >>> f([[1, 2]], [[1, 2], 3])
    0
    """
    if not what: # empty list is always found
        return 0
    try:
        index = 0
        while True:
            index = where.index(what[0], index)
            if where[index:index+len(what)] == what:
                return index # found
            index += 1 # try next position
    except ValueError:
        return -1 # not found

def contains(what, where):
    """Return [start, end+1] if found else empty list."""
    i = list_find(what, where)
    return [i, i + len(what)] if i >= 0 else [] #NOTE: bool([]) == False

if __name__=="__main__":
    import doctest; doctest.testmod()

==============================

6.이것은 내장 list.index () 메서드와 == 연산자를 사용하여 선형 검색을 수행하기 때문에 매우 빠르게 작동합니다.

이것은 내장 list.index () 메서드와 == 연산자를 사용하여 선형 검색을 수행하기 때문에 매우 빠르게 작동합니다.

def contains(sub, pri):
    M, N = len(pri), len(sub)
    i, LAST = 0, M-N+1
    while True:
        try:
            found = pri.index(sub[0], i, LAST) # find first elem in sub
        except ValueError:
            return False
        if pri[found:found+N] == sub:
            return [found, found+N-1]
        else:
            i = found+1

==============================
7.목록에 시퀀스와 함께 다른 목록이 포함되어 있는지 테스트하는 문제를 해결하면 대답은 다음 한 줄 일 수 있습니다.

목록에 시퀀스와 함께 다른 목록이 포함되어 있는지 테스트하는 문제를 해결하면 대답은 다음 한 줄 일 수 있습니다.
```
def contains(subseq, inseq):
    return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1))
```
여기이 단선을 조정하는 데 사용한 단위 테스트 :

https://gist.github.com/anonymous/6910a85b4978daee137f
==============================
8.최소 코드 :

최소 코드 :
```
def contains(a,b):
    str(a)[1:-1].find(str(b)[1:-1])>=0
```
==============================
9.이를 수행하는 all () 및 any () 함수가 있습니다. list1에 list2의 모든 요소가 들어 있는지 확인하려면

이를 수행하는 all () 및 any () 함수가 있습니다. list1에 list2의 모든 요소가 들어 있는지 확인하려면
```
result = all(elem in list1 for elem in list2)
```
list1에 list2에있는 모든 요소가 들어 있는지 확인하려면
```
result = any(elem in list1 for elem in list2)
```
변수 결과는 부울 (TRUE / FALSE)이됩니다.
==============================
10.여기 내 대답이다. 이 함수는 B가 A의 하위 목록인지 여부를 찾는 데 도움이됩니다. 시간 복잡도는 O (n)입니다.

여기 내 대답이다. 이 함수는 B가 A의 하위 목록인지 여부를 찾는 데 도움이됩니다. 시간 복잡도는 O (n)입니다.
```
`def does_A_contain_B(A, B): #remember now A is the larger list
    b_size = len(B)
    for a_index in range(0, len(A)):
        if A[a_index : a_index+b_size]==B:
            return True
    else:
        return False`
```
==============================
11.나는 이것을 가능한 한 효율적으로 만들려고 노력했다.

나는 이것을 가능한 한 효율적으로 만들려고 노력했다.

그것은 발전기를 사용합니다; 이 짐승들에게 익숙하지 않은 사람들은 그들의 문서와 수확량 표를 확인하는 것이 좋습니다.

기본적으로 하위 시퀀스에서 값의 생성기를 생성하며이 시퀀스는 실제 값을 전송하여 재설정 할 수 있습니다. 발전기가 리셋되면, 서브의 시작부터 다시 항복하기 시작합니다.

그런 다음 시퀀스의 연속 값을 생성기 출력량과 비교하고 일치하지 않으면 생성기를 재설정합니다.

발전기의 값이 다되었을 때, 즉 리셋되지 않고 서브의 끝까지 도달하면, 우리는 우리가 찾은 것을 의미합니다.

모든 시퀀스에서 작동하므로 문자열에서도 사용할 수 있습니다.이 경우 str.find와 유사하게 동작합니다. 단, -1 대신 False를 반환한다는 점이 다릅니다.

추가 정보 : 리턴 된 튜플의 두 번째 값은 파이썬 표준에 따라 일반적으로 하나 더 높아야한다고 생각합니다. 즉 "string"[0 : 2] == "st"입니다. 그러나 사양은 다르게 말합니다. 그래서 이것이 어떻게 작동하는지에 대한 것입니다.

이것이 범용 루틴인지 또는 특정 목표를 구현하는지 여부에 달려 있습니다. 후자의 경우에는 범용 루틴을 구현 한 다음 사양에 맞게 반환 값을 twiddles하는 함수로 래핑하는 것이 좋습니다.
```
def reiterator(sub):
    """Yield elements of a sequence, resetting if sent ``True``."""
    it = iter(sub)
    while True:
        if (yield it.next()):
            it = iter(sub)

def find_in_sequence(sub, sequence):
    """Find a subsequence in a sequence.

    >>> find_in_sequence([2, 1], [-1, 0, 1, 2])
    False
    >>> find_in_sequence([-1, 1, 2], [-1, 0, 1, 2])
    False
    >>> find_in_sequence([0, 1, 2], [-1, 0, 1, 2])
    (1, 3)
    >>> find_in_sequence("subsequence",
    ...                  "This sequence contains a subsequence.")
    (25, 35)
    >>> find_in_sequence("subsequence", "This one doesn't.")
    False

    """
    start = None
    sub_items = reiterator(sub)
    sub_item = sub_items.next()
    for index, item in enumerate(sequence):
        if item == sub_item:
            if start is None: start = index
        else:
            start = None
        try:
            sub_item = sub_items.send(start is None)
        except StopIteration:
            # If the subsequence is depleted, we win!
            return (start, index)
    return False
```

==============================

12.나는 이것이 빠르다고 생각한다.

나는 이것이 빠르다고 생각한다.

def issublist(subList, myList, start=0):
    if not subList: return 0
    lenList, lensubList = len(myList), len(subList)
    try:
        while lenList - start >= lensubList:
            start = myList.index(subList[0], start)
            for i in xrange(lensubList):
                if myList[start+i] != subList[i]:
                    break
            else:
                return start, start + lensubList - 1
            start += 1
        return False
    except:
        return False

==============================
13.대부분의 해답은 목록에있는 고유 항목에 적합하다는 것입니다. 항목이 고유하지 않고 여전히 교차가 있는지 여부를 알고 싶다면 항목을 계산해야합니다.

대부분의 해답은 목록에있는 고유 항목에 적합하다는 것입니다. 항목이 고유하지 않고 여전히 교차가 있는지 여부를 알고 싶다면 항목을 계산해야합니다.
```
from collections import Counter as count

def listContains(l1, l2):
  list1 = count(l1)
  list2 = count(l2)

  return list1&list2 == list1

print( listContains([1,1,2,5], [1,2,3,5,1,2,1]) ) # Returns True
print( listContains([1,1,2,8], [1,2,3,5,1,2,1]) ) # Returns False
```
'.join (list1 & list2)'을 사용하여 교차 부분을 반환 할 수도 있습니다.

from https://stackoverflow.com/questions/3847386/testing-if-a-list-contains-another-list-with-python by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] 범위 값을 의사 색으로 (0)	2018.10.15
[PYTHON] cqlsh 연결 오류 : 'ref ()가 키워드 인수를 사용하지 않습니다.' (0)	2018.10.15
[PYTHON] 모든 고유 한 값을 갖는 2D 배열을 생성하기 위해 임의 선택 (0)	2018.10.15
[PYTHON] Python FTP는 날짜별로 최신 파일을 가져옵니다. (0)	2018.10.15
[PYTHON] 사용자 입력에서 동적으로 명명 된 변수 만들기 [duplicate] (0)	2018.10.15

복붙노트

[PYTHON] 목록에 Python으로 다른 목록이 포함되어 있는지 테스트하기

목록에 Python으로 다른 목록이 포함되어 있는지 테스트하기

해결법

1.여기 내 버전입니다 :

2.모든 항목이 고유 한 경우 집합을 사용할 수 있습니다.

3.큰 목록이 정말 큰 경우 Rabin-Karp 알고리즘을 겸허하게 제안해도 될까요? 이 링크는 거의 파이썬에서 거의 쓸만한 코드를 포함합니다.

4.OP 편집 후 :

5.다음은 목록 메서드를 사용하는 간단한 알고리즘입니다.

6.이것은 내장 list.index () 메서드와 == 연산자를 사용하여 선형 검색을 수행하기 때문에 매우 빠르게 작동합니다.

7.목록에 시퀀스와 함께 다른 목록이 포함되어 있는지 테스트하는 문제를 해결하면 대답은 다음 한 줄 일 수 있습니다.

8.최소 코드 :

9.이를 수행하는 all () 및 any () 함수가 있습니다. list1에 list2의 모든 요소가 들어 있는지 확인하려면

10.여기 내 대답이다. 이 함수는 B가 A의 하위 목록인지 여부를 찾는 데 도움이됩니다. 시간 복잡도는 O (n)입니다.

11.나는 이것을 가능한 한 효율적으로 만들려고 노력했다.

12.나는 이것이 빠르다고 생각한다.

13.대부분의 해답은 목록에있는 고유 항목에 적합하다는 것입니다. 항목이 고유하지 않고 여전히 교차가 있는지 여부를 알고 싶다면 항목을 계산해야합니다.

'PYTHON' 카테고리의 다른 글

티스토리툴바