2017-03-16 11 views
1

그래서 두 개의 문자열 목록이 있습니다. 이러한 문자열은 하나 이상의 다른 문자의 정렬 된 조합으로 구성됩니다. 문자는 모두 알파벳에있는 것이 아니라 주어진 것입니다.문자열 목록에있는 문자의 하위 집합이 다른 문자열 목록에 포함되어 있는지 확인하십시오.

가능한 모든 문자가 [A, B, C, D, E] 인 경우 두 목록에는 이러한 요소의 조합이 있습니다 (이 경우 1에서 5까지).

예 :

I가 원하는
list1 = [AB, AB, C] 
list2 = [ABC, CD, ABCDE, E] 

각리스트의 요소 수는 일반적인 경우 지금 주변

10 인으로 정의되지 않으며, 1 내지 30 범위 일 수있다, 순서에 관계없이 list2에도 존재하는 list1에 문자열 당 고유 한 문자 조합이 하나 이상 있는지 확인합니다. 이 예에서 [A, A, C]는 [A, C, A, E]로 list2에 포함됩니다.

순진한 방법은 각 목록에서 가능한 모든 문자 조합을 수행하고 list2list1이 들어있는 적어도 하나의 사례가 존재하는지 확인하는 것입니다. 그러나 이것은 5 문자 문자열의 10 요소 목록의 가능한 모든 조합이 거대 할 수 있기 때문에 기하 급수적으로 증가 할 수 있습니다 (그리고 이는 일반적인 경우에 불과합니다).

정규 표현식이나 그와 비슷한 것을 사용하려고 생각했지만 실제로는 더 효율적인 해결책을 제시하지 못했습니다.

저는 이것을 위해 Python을 사용하고 있습니다. 기존 솔루션이나 라이브러리로 인해 관련성이 있습니다.

도움 주셔서 감사합니다.

+0

각 목록에 대해 조합의 각 요소가 목록의 개별 항목에서 나오는 조합 집합을 만들고 싶습니까?목록의 항목이 조합에 기여하지 않을 수 있습니까? (예를 들어'list1'은'{A, C}'를 포함합니까?) –

+0

첫 번째 질문은 yes입니다. 조합은 목록의 각 문자열에서 하나의 요소로 구성됩니다. 나는 두 번째 질문을 이해하지 못한다. 나는'list2'의 하나의 조합에 들어있는'list1'과 적어도 하나의 조합을 찾고 싶습니다. – crscardellino

답변

5

이것은 집합 연산의 주요 후보가 될 수 있습니다. 예를 들어 보겠습니다 (예를 들어 문자열을 만들기 위해 따옴표를 추가해야 함).

list1 = ["AB", "AB", "C"] 
list2 = ["ABC", "CD", "ABCDE", "E"] 

우리는 모두 list1

print(set(list1) | set(list2)) 
#OUTPUT: {'C', 'AB', 'ABCDE', 'CD', 'ABC', 'E'} 

우리가 (우리가 "C"를 추가한다면 모두 list1list2에서 일반적으로 어떤 요소를 확인하려면 list2에서 독특한 요소 세트를 원하는 경우 list2으로 설정하면 {'C'}의 출력을 가지게되고, 공유되는 공통 요소가 없으므로 set()이됩니다.

print(set(list1) & set(list2)) 
#OUTPUT: set() 

우리는 list1에있는 요소이지만

print(set(list1) - set(list2)) 
#OUTPUT: {'C', 'AB'} 

우리가 하나 list1 또는 list2

print(set(list1)^set(list2)) 
#OUTPUT: {'E', 'CD', 'AB', 'ABC', 'C', 'ABCDE'} 

에있는 요소 세트를 원하는 경우 list2에 대한 자세한 내용은 확인할 수 없습니다를 원하는 경우 out https://docs.python.org/2/library/sets.html

이 도움이 되었기를 바랍니다.