How to get all possible combinations of characters in a String

Question

So I have a string like this:

"abc"

I would need:

"abc"
"acb"
"bca"
"bac"
"cab"
"cba"

I tried:

string = "abc"

combinations = []
for i in range(len(string)):
    acc = string[i]
    for ii in range(i+1,i+len(string)):
            acc += string[ii%len(string)]
             
    combinations.append(acc)
    combinations.append(acc[::-1])
            
print(combinations)

If works for string of size 3, but I believe it is very inefficient and also doesn't work for "abcd". Is there a better approach?

Update: I would like to solve by providing an algorithm. Actually currently working in a recursive way to solve it. Would prefer a solution that is not a python function solving the problem for me

Does this answer your question? [How to generate all permutations of a list?](https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list) — Dan Simon, Jan 22 '21 at 07:18
Thanks for the clarification, however I still think the linked question applies. It has many answers that don't use built-in python functions, including some that are recursive. — Dan Simon, Jan 22 '21 at 07:30

itsDV7 · Answer 1 · 2021-01-22T07:33:19.253

For permutations:

Using Itertools Library:

from itertools import permutations
ini_str = "abc"
print("Initial string", ini_str)
permutation = [''.join(p) for p in permutations(ini_str)]
print("Resultant List", str(permutation))

Initial string abc

Resultant List ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Recursive Method:

def permutations(remaining, candidate=""):
    if len(remaining) == 0:
        print(candidate)
    for i in range(len(remaining)):
        newCandidate = candidate + remaining[i]
        newRemaining = remaining[0:i] + remaining[i+1:]
        permutations(newRemaining, newCandidate)

if __name__ == '__main__':
    s = "ABC"
    permutations(s)

Iterative Method:

def permutations(s):
    partial = []
    partial.append(s[0])
    for i in range(1, len(s)):
        for j in reversed(range(len(partial))):
            # remove current partial permutation from the list
            curr = partial.pop(j)
            for k in range(len(curr) + 1):
                partial.append(curr[:k] + s[i] + curr[k:])
    print(partial, end='')
  
if __name__ == '__main__':
    s = "ABC"
    permutations(s)

U13-Forward · Accepted Answer · 2021-01-22T07:37:23.803

Try itertools.permutations:

from itertools import permutations
print('\n'.join(map(''.join, list(permutations("abc", 3)))))

Output:

abc
acb
bac
bca
cab
cba

edit:

For an algorithm:

string = "abc"
def combinations(head, tail=''):
    if len(head) == 0:
        print(tail)
    else:
        for i in range(len(head)):
            combinations(head[:i] + head[i+1:], tail + head[i])
combinations(string)

Output:

abc
acb
bac
bca
cab
cba

score 1 · Answer 3 · answered Jan 22 '21 at 07:25

1

Your logic is correct, but you want permutation, not combination. Try:

from itertools import permutations

perms = permutations("abc", r=3)
# perms is a python generator and not a list.

You can easily create a list from that generator if you want.

answered Jan 22 '21 at 07:25

null

1,944
1
14
24

Thank you +1, it is a very clean answer, but I would like to write the algorithm. It is something I was asked in an interview and what I wrote in the question is the best I could do – Tony Balboa Jan 22 '21 at 07:28
well, you can look at the source code [here](https://docs.python.org/3/library/itertools.html#itertools.permutations) and observe the algorithm. – null Jan 22 '21 at 16:16

score 0 · Answer 4 · answered Jan 22 '21 at 07:30

1. Use permutations from itertools

from itertools import permutations 
  
s = 'abc'
permutation = [''.join(p) for p in permutations(s)] 
print(permutation) 
# ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

2. Implement the algorithm

s = 'abc'
result = []

def permutations(string, step = 0):
    if step == len(string):
        result.append("".join(string))
    for i in range(step, len(string)):
        string_copy = [character for character in string]
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]
        permutations(string_copy, step + 1)

permutations(s)
print(result)
# ['abc', 'acb', 'bac', 'bca', 'cba', 'cab']

How to get all possible combinations of characters in a String

4 Answers4

For permutations:

Using Itertools Library:

Recursive Method:

Iterative Method: