CODEWITHSUNDEEP
pythonpermutationpython-itertools
genclik27
genclik27

Reputation: 323

Generating r-length permutations of list with repeated elements python

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?

Upvotes: 0

Views: 1577

Answers (1)

idbrii
idbrii

Reputation: 11966

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

Upvotes: 1

Related Questions