파이썬에서 주어진 방법으로리스트를 나누는 방법

Question

정수리스트를 주면, 또 다른 정수리스트를 출력하는 함수를 작성하는 것입니다. 이 단어에서 원하는 출력의 성격을 알려 어렵다, 나는 몇 가지 예제를 쓰고 :

# list with one element will be returned 
>>> func([[1, 2, 3, 4]]) 
[[1, 2, 3, 4]] 

>>> func([[1], [1, 2]]) 
[[1], [2]] 

>>> func([[1, 2], [1]]) 
[[1], [2]] 

>>> func([[1], [1, 2, 3]]) 
[[1], [2, 3]] 

>>> func([[1], [1, 2, 3], [1, 4]]) 
[[1], [2, 3], [4]] 

>>> func([[1, 2], [2, 3]]) 
[[1], [2], [3]] 

>>> func([[1], [2], [1, 2, 3]]) 
[[1], [2], [3]] 

>>> func([[1, 2], [1, 2, 3]]) 
[[1, 2], [3]] 

>>> func([[1], [1, 2], [1, 2, 3]]) 
[[1], [2], [3]] 

(UPDATE) 다음과 같은 전제 조건 사용할 수 있습니다

1. 각 내부 목록에 이미 정렬 정수를 포함을 중복 입력이 없습니다.

2. 외부 목록에는 중복 된 항목이 없습니다.

, 여기에 내가와 붙어있어 생각입니다 (UPDATE) 당신이 요청으로 :이 감독 그래프에 대한 몇 가지 최적화에 문제가 시작 지점과 같은 노드로 번호 및 내부 목록과,

입니다 (외부 목록은 모든 가장자리의 시작점 집합입니다). 이제 "단일 에지에 대한 시작점이 여러 개있는 경우 어떤 테스트 케이스에 표시 되는가?"라는 질문을 할 수 있습니다.

이것은 내가하려고하는 것입니다. func ([1, 2])의 경우 노드 1 & 노드 2는 단일 노드에 병합 할 수 있습니다. [1, 2] 출력은이 두 가지를 병합 할 수 있음을 보여줍니다.

이제 func ([[1], [1, 2]])을 확인하십시오. 두 번째 내부 목록은 노드 1 & 2를 병합하려고 시도하지만 첫 번째 내부 목록은 노드 1을 병합 할 수 없다고 말합니다. 따라서 출력은 [[1], [2]]이며 노드 1 & 노드 2가 분리되어 유지됨을 나타냅니다.

func ([[1], [2, 3], [1, 2, 3]])의 경우 노드 1은 분리되지만 노드 2 & 3은 병합 할 수 있습니다. 그래서 출력 func ([[1, 2], [2, 3]]) 경우 [[1], [2, 3]]

될 것이며,도 2의 노드 1 & &도 2 3 3 노드 1 &로 병합 될 수 병합 될 수 있으므로, 예상 결과 [[1], [2], [3]]이다.

꼭지점의 끝점으로 구성된 정수 목록이 있습니다. 각 정수는 각 내부 목록에 해당합니다. 내부 목록의 요소를 하나로 병합 할 때 가장자리가 하나만 남습니다. 그들이 분리되면, 싱글 톤 목록이 있으며, 각 요소는 출발점으로 사용됩니다. 그에 따라 종점 목록이 업데이트됩니다.

내 생각을 이해하는 데 도움이 될 것 같습니다.

Answer 1

이것은 오름차순으로 정렬되는 목록 (출력은 정렬이 필요함)에 의존하지만 게시 시점에 제공된 모든 입력과 함께 작동합니다.

def removeFromList(elementsToRemove): 
    def closure(list): 
     for element in elementsToRemove: 
      if list[0] != element: 
       return 
      else: 
       list.pop(0) 
    return closure 

def func(listOfLists): 
    result = [] 
    for i, thisList in enumerate(listOfLists): 
     result.append(thisList) 
     map(removeFromList(thisList), listOfLists[i+1:]) 
    return result 

당신은 루프에 대한 이상을 사용하여 폐쇄를 제거 할 수 있습니다,하지만 너무 추한, 너무 깊게 중첩 보았다.

편집 :이 최적화하거나 개선 할 수있는 방법의 수는 아마 있습니다

from itertools import combinations 

def isSubsetOrDisjointTo(listA, listB): 
    return all(item in listB for item in listA) or all(item not in listB for item in listA) 

def func(nodesToJoin): 
    #flatten list, extracting duplicates 
    allNodes = sorted(set(itertools.chain(*nodesToJoin))) 

    result = [] 

    seen = set() 

    for length in xrange(max(map(len, nodesToJoin)), 0, -1): 
     #start with longest possible, work to shortest 
     for sublist in combinations(allNodes, length): 
      if any(item in seen for item in sublist): 
       #skip possible sublists with options we've already seen in the result 
       continue 

      if all(isSubsetOrDisjointTo(sublist, node) for node in nodesToJoin): 
       result.append(sublist) 
       seen.update(sublist) 

    return result 

: 업데이트에 따라,이 실제 문제에 대한 순진 솔루션입니다.

Answer 2

def func(L): 
    r = [L[0]] 
    for i in range(1, len(L)): 
     r.append(list(set(L[i]) - set(L[i-1]))) 
    return r 

Answer 3

def f (L): 
    return [[l for l in L[i] if l not in sum(L[:i], [])] for i in range(len(L))] 

편집 : OP는 테스트 결과가 될 운명이 무엇 계속 변화는 그래서 난 몰라,이 내가 쓴이 있었다 모든 테스트에 대한 정확한 답변을 제공합니다.