CODEWITHSUNDEEP
python
Tony Balboa
Tony Balboa

Reputation: 33

How to get all possible combinations of characters in a String

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

Upvotes: 1

Views: 1815

Answers (4)

U13-Forward
U13-Forward

Reputation: 71610

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

Upvotes: 2

itsDV7
itsDV7

Reputation: 854

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)

Upvotes: 5

Kien Nguyen
Kien Nguyen

Reputation: 2701

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

Upvotes: 0

null
null

Reputation: 2137

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.

Upvotes: 1

Related Questions