Function that returns all combinations of a string

Question

Hello! I’m trying to develop a script so I can review some content covered while studying and training my logic and I proposed a challenge to myself: Develop a script capable of returning all possible combinations of a string. However, I see in my script several things that make it ineffective.

from random import shuffle
from math import factorial


def combinations(str):
    allcomb = []  # Aqui aramazena todas combinações
    word = [l for l in str]  
    for l in str:
        t = 0  # Quantas combinações uma letra tem
        while t != factorial(len(str)) / len(str):
            word2 = word.copy()
            shuffle(word2)  # Embaralha a lista da palavra
            print(word2)
            if word2 not in allcomb:
                t += 1
                allcomb.append(word2)

    print(allcomb)


combinations('eae')

my doubts are: How can I make the computer shuffle the strings more efficiently? Because this way, he’s doing it randomly, and when he increases the amount of letters, the probability of him finding the only word missing is very low.

The second is that there is a logical error. In the word I tested as input we have two repeated letters. When he checks, he will see that there are two equal combinations 'Eae' and 'Eae'. Something that verification will not accept, making this an infinite looping.

Well, if you think you can help me, please contact me :)

Answer 1

TL:DR

Use itertools.permutations instead of itertools.combinations for permutations will return the possibilities of a Arrangement while combinations the possibilities of a Combining. That is, in combinations ab and ba are identical because your order does not matter, however you are talking about words then medo and demo are different words, so the use of itertools.permutations.

from itertools import permutations

def arranjos(palavra):
    resultado = set()

    for i in range(1, len(palavra) + 1):
        resultado.update("".join(r) for r in permutations(palavra, i))

    return resultado

---

Explanation

If you go to see the theory of Combinatorial Analysis, you don’t want a Combining, you want a Arrangement, because in the Combination the order of what you are combining nay it matters, already in the Arrangement this order makes a difference.

Arrangement with repetition

To order makes difference and objects can be repeated, a good example is when you want to create a numeric password.

Imagine that the password has 2 digits and you can use only the numbers from zero to nine, it is clear that the password 12 is different from the password 21 so we have an arrangement, not a combination. It is also possible for a person to create a password 11 or 22, so we use an arrangement with repetition, which is nothing more than the cartesian product of 0123456789 with itself. The module itertools implements this algorithm performatively in function itertools.product.

See the example of the password:

from itertools import product

arranjo_com_rep = product("0123456789", repeat=2)
# ['00', '01', '02', ..., '98', '99']

Arrangement without repetition

To order makes difference and objects CANNOT be repeated, I believe that’s what you’re trying to do. Using common arrangement you’re saying: "What are the possibilities if I mix and pick up N letters of this word?". That is, you are using only the letters that are in the word without repeating them.

An example of use would be, "I have a ladder with 2 steps and 3 bottles (bottles 'a', 'b' and 'c'). how many different ways I can dispose my bottles on these steps?".

It is worth remembering that a Permutations Simples It is nothing more than an arrangement without repetition where the size of the grouping of elements of the result is equal to the size of the elements being combined. That is, a simple permutation is nothing more than "shuffling" the elements.

The module itertools implements this algorithm performatively in function itertools.permutations. Note that if you do not pass the second parameter to the function, it uses the length of the iterable it received. That being said, it is clear that if you want to make an arrangement, just pass the second parameter setting the size of the result sets, if you want a permutation just do not pass the second parameter.

from itertools import permutations

arranjo_com_rep = permutations("abc", 2)
# [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

permutacao = permutations("abc")
# [('a', 'b', 'c'),
#  ('a', 'c', 'b'),
#  ('b', 'a', 'c'),
#  ('b', 'c', 'a'),
#  ('c', 'a', 'b'),
#  ('c', 'b', 'a')]

Combination without repetition

Although it is not what you need for this case it is important you understand that combinations DO NOT take into account the order of the elements.

Imagine you have 5 students in a class wondering how many groups of 2 members you could form with them.

You can calculate which groups could be formed using the method itertools.combinations. Note that order does not matter, because a group formed by students "A" and "C" is the same group formed by students "C" and "A".

from itertools import combinations

combinacoes = combinations("ABCDE", 2)
# [('A', 'B'),
#  ('A', 'C'),
#  ('A', 'D'),
#  ('A', 'E'),
#  ('B', 'C'),
#  ('B', 'D'),
#  ('B', 'E'),
#  ('C', 'D'),
#  ('C', 'E'),
#  ('D', 'E')]

Combination with repetition

It is the same as before, but the repetition of the elements is allowed.

Imagine you want to buy an ice cream with 4 balls in an ice cream shop that has 3 flavors available. How many different ways you can make this purchase?

You can calculate repeat combinations using the method itertools.combinations_with_replacement.

from itertools import combinations_with_replacement
combinacoes = combinations_with_replacement("ABC", 4)
# [('A', 'A', 'A', 'A'),
#  ('A', 'A', 'A', 'B'),
#  ('A', 'A', 'A', 'C'),
#  ('A', 'A', 'B', 'B'),
#  ('A', 'A', 'B', 'C'),
#  ('A', 'A', 'C', 'C'),
#  ('A', 'B', 'B', 'B'),
#  ('A', 'B', 'B', 'C'),
#  ('A', 'B', 'C', 'C'),
#  ('A', 'C', 'C', 'C'),
#  ('B', 'B', 'B', 'B'),
#  ('B', 'B', 'B', 'C'),
#  ('B', 'B', 'C', 'C'),
#  ('B', 'C', 'C', 'C'),
#  ('C', 'C', 'C', 'C')]

Answer 2

Specifically in the case of Python you can use the itertools.:

from itertools import combinations

all_combinations = set()

my_string = "pernambuco"  # <- já não tem repetições de caracteres

for i in range(1,len(my_string)+1):
    for j in combinations(my_string, i):
        all_combinations.add("".join(j))

print(all_combinations)

The use of set() is to restrict repetitions, although they will not occur in the example since the string Pernambuco has no repeated letters.