CODEWITHSUNDEEP
pythonstringpermutation
RISHABH AGRAWAL
RISHABH AGRAWAL

Reputation: 27

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

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

Upvotes: 0

Views: 936

Answers (2)

Patrik
Patrik

Reputation: 499

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)

Upvotes: 1

Souvik Nandi
Souvik Nandi

Reputation: 364

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']

Upvotes: 2

Related Questions