How to print all possible permutations of different lengths in python?

Question

I am trying to print all possible permutations of a string of different lengths

I am doing

def toString(List):
    return ''.join(List)


def permute(string1, l, r):
    if l == r:
        print(toString(string1))
    else:
        for i in range(l, r + 1):
            string1[l], string1[i] = string1[i], string1[l]
            permute(string1, l + 1, r)
            string1[l], string1[i] = string1[i], string1[l] 


string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n-1)

but it returns ABC ACB BAC BCA CBA CAB

I want it to return A, B, C, AB, BC, AC, ABC, ACB, BAC etc.

I am unable to achieve that

I am trying to do it without using any modules but i'll try it with that too, Thanks — RISHABH AGRAWAL, Nov 25 '20 at 17:10
Does this answer your question? [How to get all possible combinations of a list’s elements?](https://stackoverflow.com/questions/464864/how-to-get-all-possible-combinations-of-a-list-s-elements) — mkrieger1, Nov 25 '20 at 17:12
@RISHABHAGRAWAL I guess you actually need all subsets of the string, not permutations — Souvik Nandi, Nov 25 '20 at 17:38

Souvik Nandi · Accepted Answer · 2020-11-25T17:42:22.193

I guess you are looking for all possible subsets of the string and not permutations if so then you can use any one of the following approaches which look intuitive to you

def permute(string1):
    n = len(string1)
    finalSet = ['']

    def permutation(size, cur, k):
        if len(cur) == size:
            finalSet.append(''.join(cur))
            return

        for j in range(k, n):
            permutation(size, cur + [string1[j]], j+1)

    for i in range(1, n):
        permutation(i, [], 0)

    finalSet.append(string1)

    return finalSet


print(permute("ABC"))
# Output : ['', 'A', 'B', 'C', 'AB', 'AC', 'BC', 'ABC']

Another approach which uses binary data to create subsets

# Short and simple approach
def permute(string1):
    superSet = []
    n = len(string1)

    for i in range(2**n, 2**(n+1)):
        seq = [x for x in bin(i)[3:]]
        superSet.append(''.join([string1[j]
                                 for j in range(n) if seq[j] == '1']))

    return superSet


print(permute("ABC"))
# Output : ['', 'C', 'B', 'BC', 'A', 'AC', 'AB', 'ABC']

Patrik · Answer 2 · 2020-11-25T17:53:42.813

You are close, you just have to wrap one more for loop around permutate and use your function to calculate permutation of all substrings:

def toString(List):
    return ''.join(List)


def permute(string1, l, r):
    if l == r and r != 0:
        print(toString(string1))
    else:
        for i in range(l, r + 1):
            string1[l], string1[i] = string1[i], string1[l]
            permute(string1, l + 1, r)
            string1[l], string1[i] = string1[i], string1[l]


my_string = "ABC"
for s in my_string:
    print(s)
for i,_ in enumerate(my_string):
    n = len(my_string[:i+1])
    a = list(my_string[:i+1])
    permute(a, 0, n-1)

but this prints A AB BA ABC ACB BAC BCA CBA CAB – RISHABH AGRAWAL Nov 25 '20 at 17:19 — RISHABH AGRAWAL, Nov 25 '20 at 17:19

How to print all possible permutations of different lengths in python?

2 Answers2