반복 요소 python을 사용하여 목록의 r- 길이 순열 생성

Question

내 질문은 질문과 비슷합니다. here. 이 질문과 다른 점은 반복 된 원소로 주어진리스트의 r- 튜플 순열을 생성하는 알고리즘이 필요하다는 것입니다. 예에

는 :

list1 = [1,1,1,2,2] 

for i in permu(list1, 3): 
    print i 

[1,1,1] 
[1,1,2] 
[1,2,1] 
[2,1,1] 
[1,2,2] 
[2,1,2] 
[2,2,1] 

이 itertools.permutations이 반복되는 사람을 제거하는 간단한 필터링을 추가로 여기에 잘 작동 것으로 보인다. 그러나 실제로는리스트가이 예제보다 훨씬 길고 목록 길이가 길어질수록 itertools.permutations의 복잡성이 지수 적으로 증가한다는 것을 이미 알고 있습니다.

지금까지 내가 가지고있는 것은 아래에 있습니다. 이 코드는 설명 된 작업을 수행하지만 효율적이지 않습니다.

def generate_paths(paths, N = None): 
    groupdxs = [i for i, group in enumerate(paths) for _ in range(len(group))] 
    oldCombo = [] 
    result = [] 
    for dxCombo in itertools.permutations(groupdxs, N): 
     if dxCombo <= oldCombo: # as simple filter 
      continue 
     oldCombo = dxCombo 
     parNumbers = partialCombinations(dxCombo, len(paths)) 
     if not parNumbers.count(0) >= len(paths)-1: # all of nodes are coming from same path, same graph 
      groupTemps = [] 
      for groupInd in range(len(parNumbers)): 
       groupTemp = [x for x in itertools.combinations(paths[groupInd], parNumbers[groupInd])] 
       groupTemps.append(groupTemp) 
      for parGroups in itertools.product(*groupTemps): 
       iters = [iter(group) for group in parGroups] 
       p = [next(iters[i]) for i in dxCombo] 
       result.append(p) 
    return result 


def partialCombinations(combo, numGruops): 
    tempCombo = list(combo) 
    result = list([0] * numGruops) 
    for x in tempCombo: 
     result[x] += 1 
    return result 

첫 번째 for 루프에서 알고리즘을 느리게 만드는 모든 가능한 r-length 튜플을 생성해야합니다. 위의 링크에서 r 길이를 사용하지 않고 순열에 대한 좋은 해결책이 있습니다. 어떻게이 알고리즘을 채택 할 수 있습니까? 아니면 더 좋은 방법이 있습니까?

Answer 1

저는이 사실을 귀하의 경우에 대해 매우 잘 생각하지 않았지만 여기에는 또 다른 접근 방법이 있습니다.

순열에 큰 목록을 제공하는 대신 중복이없는 작은 목록을 제공 할 수 있습니다. combine_with_replacement를 사용하여 이러한 작은 목록을 생성 할 수 있습니다 (원본 입력과 중복되는 항목의 양을 일치시켜야 함). 그런 다음 각 조합의 순열을 가져옵니다.

possible_values = (1,2) 
n_positions = 3 

sorted_combinations = itertools.combinations_with_replacement(possible_values, n_positions) 
unique_permutations = set() 
for combo in sorted_combinations: 
    # TODO: Do filtering for acceptable combinations before passing to permutations. 
    for p in itertools.permutations(combo): 
     unique_permutations.add(p) 


print "len(unique_permutations) = %i. It should be %i^%i = %i.\nPermutations:" % (len(unique_permutations), len(possible_values), n_positions, pow(len(possible_values), n_positions)) 
for p in unique_permutations: 
    print p