How to find all possible permutation of two strings within constant length

Admin 1
Viewed 529

I want to find all possible permutation of two list of strings within a constant length (5). Assume list_1 = ["A"] and list_2 = ["BB"].

All possible combinations are:

A A A A A
A A A BB
A A BB A
A BB A A
BB A A A
A BB BB
BB A BB
BB BB A

I was trying to implement it with the code below, but I am not sure how to define the length 5 for it.

import itertools 
from itertools import permutations 

list_1 = ["A"] 
list_2 = ["BB"] 
unique_combinations = [] 

permut = itertools.permutations(list_1, 5) 

for comb in permut: 
    zipped = zip(comb, list_2) 
    unique_combinations.append(list(zipped)) 

print(unique_combinations)
combinations permutation itertools python string
4 Answers

You could do the following:

import itertools

unique_combinations = []

permut = itertools.product(["A","B"], repeat=5)
for comb in permut:
    l = "".join(comb)
    c_bb = l.count("BB")
    c_a = l.count("A")
    if 2*c_bb + c_a == 5:
        unique_combinations.append(l)
print(unique_combinations)

This will give:

['AAAAA', 'AAABB', 'AABBA', 'ABBAA', 'ABBBB', 'BBAAA', 'BBABB', 'BBBBA']

First find all the string-like of length 5 consists of 5 elements, either "A" or "B". Then use string.count to count the occurrences of each substring you are interested in and if it is equal 5 save it.

user_88906040

You can use itertools.product to find all the possible combinations of 'A' and 'BB' (of repeat from 3 to 5, as these are the number of elements in the acceptable answers), and then filter than based on their total length being 5 characters:

import itertools

all_options = []
for i in range(3,6):
    all_options += list(itertools.product(['A', 'BB'], repeat=i))
all_options = [i for i in all_options if len(''.join(i)) == 5]
print(all_options)

Output:

[('A', 'BB', 'BB'), ('BB', 'A', 'BB'), ('BB', 'BB', 'A'), ('A', 'A', 'A', 'BB'), ('A', 'A', 'BB', 'A'), ('A', 'BB', 'A', 'A'), ('BB', 'A', 'A', 'A'), ('A', 'A', 'A', 'A', 'A')]
user_133869790

Use recursion:

list_1 = ["A"]
list_2 = ["BB"]
size = 5

strs = list_1 + list_2
res = []

def helper(strs, size, cur, res):
    if size == 0:
        res.append(cur)
        return
    if size < 0:
        return

    for s in strs:
        helper(strs, size-len(s), cur+[s], res)

helper(strs, size, [], res)
print(res)

No recursion:

list_1 = ["A"]
list_2 = ["BB"]
size = 5

strs = list_1 + list_2
res = []

q = [[]]
while q:
    t = q.pop()
    for s in strs:
        cur = t + [s]
        cursize = len(''.join(cur))
        if cursize == size:
            res.append(cur)
        elif cursize < size:
            q.append(cur)
print(res)
user_47249330

You need a recursive function like this:

def f(words, N, current = ""):
    if(len(current)<N):
        for i in words:
            f(words, N, current+i)
    elif(len(current)==N):
        print(current)
        

f(["A", "BB"], 5)

Edit: Unfortunately, this function return duplicates, if two or more words in your list share the same letter. So the correct approach should be to fill a list with all return and then eliminate the duplicates.

Admin1
Related