Python More efficient permutation-CodePudding

I have a string that consists of x amount of the letter 'r' and y amount of 'u'. And my goal is two print all possible combinations of that same amount of x,y with different orders. This my example of a working code.

import itertools
RIGHT = 'r'
UP = 'u'
def up_and_right(n, k, lst):
    case = RIGHT*n   UP*k
    return [''.join(p) for p in set(itertools.permutations(case))]

Example input and output:

input:
lst1 = []
up_and_right(2,2,lst1)
lst1 => output:['ruru', 'urur', 'rruu', 'uurr', 'urru', 'ruur']

My problem is when the input is an integer more than 10 the code takes a minute to compute. How can I improve the compute time? Thanks in advance!

CodePudding user response：

Try itertools.combinations:

import itertools

RIGHT = "r"
UP = "u"


def up_and_right(n, k):
    out = []
    for right_idxs in itertools.combinations(range(n   k), r=n):
        s = ""
        for idx in range(n   k):
            if idx in right_idxs:
                s  = RIGHT
            else:
                s  = UP
        out.append(s)
    return out


print(up_and_right(2, 2))

Prints:

['rruu', 'ruru', 'ruur', 'urru', 'urur', 'uurr']

With one-liner:

def up_and_right(n, k):
    return [
        "".join(RIGHT if idx in right_idxs else UP for idx in range(n   k))
        for right_idxs in itertools.combinations(range(n   k), r=n)
    ]

CodePudding user response：

Your problem is about finding permutations of multisets. sympy has a utility method that deals with it.

from sympy.utilities.iterables import multiset_permutations
def up_and_right2(n,k):
    case = RIGHT*n   UP*k
    return list(map(''.join, multiset_permutations(case)))

Test:

y = up_and_right(n,k)
x = up_and_right2(n,k)
assert len(x) == len(y) and set(y) == set(x)

Timings:

n = 5
k = 6
%timeit up_and_right(n,k)
3.57 s ± 52.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit up_and_right2(n,k)
4.17 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)