All Permutations Of String Without Using Itertools

All possible strings of any length that can be formed from a given string Input: abc Output: a b c abc ab ac bc bac bca cb ca ba cab cba acb I have tried using this bu

Solution 1:

You may not need itertools, but you have the solution in the documentation, where itertools.permutations is said to be roughly equivalent to:

defpermutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC# permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r isNoneelse r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yieldtuple(pool[i] for i in indices[:r])
    while n:
        for i inreversed(range(r)):
            cycles[i] -= 1if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yieldtuple(pool[i] for i in indices[:r])
                breakelse:
            return

Or using product:

defpermutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r isNoneelse r
    for indices in product(range(n), repeat=r):
        iflen(set(indices)) == r:
            yieldtuple(pool[i] for i in indices)

They are both generators so you will need to call list(permutations(x)) to retrieve an actual list or substitute the yields for l.append(v) where l is a list defined to accumulate results and v is the yielded value.

For all the possible sizes ones, iterate over them:

from itertools import chain
check_string = "abcd"all = list(chain.from_iterable(permutations(check_string , r=x)) for x inrange(len(check_string )))

Solution 2:

Partial recursive solution. You just need to make it work for different lengths:

defpermute(pre, str):
    n = len(str)
    if n == 0:
        print(pre)
    else:
        for i inrange(0,n):
            permute(pre + str[i], str[0:i] + str[i+1:n])

You can call it using permute('', 'abcd'), or have another method to simplify things

defpermute(str):
    permute('', str)

Answer borrowed from here.

In general, you will have better luck translating code from C/Cpp/Java solutions to Python because they generally implement things from scratch and do things without much need of libraries.

UPDATE

Full solution:

defall_permutations(given_string):
    for i inrange(len(given_string)):
        permute('', given_string, i+1)

defpermute(prefix, given_string, max_len):
    iflen(given_string) <= 0orlen(prefix) >= max_len:
        print(prefix)
    else:
        for i inrange(len(given_string)):
            permute(prefix + given_string[i], given_string[:i] + given_string[i+1:], max_len)

>>> all_permutations('abc')
abcabacbabccacbabcacbbacbcacabcba