all permutations of string without using itertools

Question

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 but it's limited to string abc, I want to generalize it like if input 'abcd' i will provide me output for the same.

def perm_main(elems):
    perm=[]
    for c in elems:
        perm.append(c)
    for i in range(len(elems)):
        for j in range(len(elems)):
            if perm[i]!= elems[j]:
                perm.append(perm[i]+elems[j])
    level=[elems[0]]
    for i in range(1,len(elems)):
        nList=[]
        for item in level:
            #print(item)
            nList.append(item+elems[i])
                #print(nList)
            for j in range(len(item)):
                #print(j)
                nList.append(item[0:j]+ elems[i] + item[j:])
                #print(nList)
        level=nList
    perm = perm + nList
    return perm

Netwave · Accepted Answer · 2019-06-03T11:05:58.297

3

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

def permutations(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 is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if 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]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Or using product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(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 in range(len(check_string )))

edited Jun 03 '19 at 11:05

answered Jun 03 '19 at 10:41

Netwave

40,134
6
50
93

thanks for the response. I am kinda new to python. The above part is not working I guess the code is not complete. it's not returning. @Netwave – shivanshu dhawan Jun 03 '19 at 10:46
@shivanshudhawan, I dont understand. What error are you having? – Netwave Jun 03 '19 at 10:50
I am not getting how to add l.append(v) in the code to get the optimal result. @netwave – shivanshu dhawan Jun 03 '19 at 10:56
@shivanshudhawan, it is better if you simply use `list(permutations("abcd"))` for retrieving the list. – Netwave Jun 03 '19 at 10:57
using `list(permutation('abc'))` gives output `[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]` – shivanshu dhawan Jun 03 '19 at 11:00
It is not what I expect, I expect all combinations of strings and their permutation. I have mentioned the input and output parameters – shivanshu dhawan Jun 03 '19 at 11:01
@shivanshudhawan, you just need to take all possible sizes and chain them. I updated the answer...but you need to read the code properly and understand the abstractions. – Netwave Jun 03 '19 at 11:07
thank you so much for your detailed response. But I am looking for something without using any function from itertools or any other package. That's why its getting difficult for me. @netwave – shivanshu dhawan Jun 03 '19 at 11:10
@shivanshudhawan, a chain is just iterating over nested lists. You need to try to split problems in small chunks, all at a time will be always really difficult. I cannot provide with more information. Sorry. – Netwave Jun 03 '19 at 11:12
Any chance of expanding the `For all the possible sizes ones,` solution without using `itertools.chain` - question restricts use of itertools. I would do it if you don't mind an edit. – wwii Sep 19 '20 at 21:22
@wwii feel free to write a new answer with your proposed solution even if it is related to this one. It is usually wise to add new flavors to old questions. Thanks for all :D – Netwave Sep 20 '20 at 08:47

MePsyDuck · Answer 2 · 2019-06-03T14:14:13.533

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

def permute(pre, str):
    n = len(str)
    if n == 0:
        print(pre)
    else:
        for i in range(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

def permute(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:

def all_permutations(given_string):
    for i in range(len(given_string)):
        permute('', given_string, i+1)

def permute(prefix, given_string, max_len):
    if len(given_string) <= 0 or len(prefix) >= max_len:
        print(prefix)
    else:
        for i in range(len(given_string)):
            permute(prefix + given_string[i], given_string[:i] + given_string[i+1:], max_len)

>>> all_permutations('abc')
a
b
c
ab
ac
ba
bc
ca
cb
abc
acb
bac
bca
cab
cba

all permutations of string without using itertools

2 Answers2

Linked

Related