Generating r-length permutations of list with repeated elements python

Question

My problem is similar to the quesiton asked here. Differing from this question, I need an algorithm which generates r-tuple permutations of a given list with repeated elements.

On an example:

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]

It seems that itertools.permutations will work fine here with adding a simple filtering to remove the repeated ones. However in my real cases, lists are much longer than this example and as you already know complexity of itertools.permutations increases exponential as the length of list increases.

So far, what I have is below. This code does the described job, but it is not efficient.

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

In first for loop, I need to generate all possible r-length tuples which makes algorithm slower. There is a good solution for permutation without using r-length in above link. How can I adopt this algorithm to mine? Or is there any better ways?

You mentioned you used itertools.permutations but did you try itertools.combinations_with_replacement? — Pablo Francisco Pérez Hidalgo
@PabloFranciscoPérezHidalgo Yes, I have tried. The problem with itertools in my case, it does not compare the values -does not look whether the elemnts in list are equal-, thats the problem actually. itertools.combinations_with_replacement returns also repetaed elements. — genclik27
@PabloFranciscoPérezHidalgo combinations_with_replacement is different from what I have asked. It repeats the all elements of list, in my case I need to filter them — genclik27
Then I guess a simpler (not necessarily efficient, though) approach would be to generate the combinations via the itertools module and display only the combinations different from their neighbors (what I mean is that duplicate will be contiguous). — user189

idbrii idbrii · Accepted Answer · 2014-07-17T21:28:30

I haven't thought this through very well for your case, but here's another approach.

Instead of giving large lists to permutations, you could give a small list that has no duplicates. You can use combinations_with_replacement to generate these smaller lists (you'll need to filter them to match the quantities of duplicates from your original input) and then get the permutations of each combination.

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

Generating r-length permutations of list with repeated elements python

1 Answers