Get all strings matching wanted length by repeating x characters from first string

Question

Let's say I have the following string:

string = '---A---B-C'

And I have the following dict:

min_max_values = {'A': [2,4], 'B': [2, 15], 'C': [1, 2]}

My goal is to generate new strings from the first string:

• All new strings must match a pre-defined length

• All groups of character must be separated by the same amount of '-' as the original string

• Only characters from the dict can be repeated, but there is a minimum and a maximum amount of time they can be repeated ([min, max]). For example, 'A' has to be used at least 2 times but at most 4 times.

Here is an exemple to make myself clear:

string = '---A---B-C'
min_max_values = {'A': [2,4], 'B': [2, 15], 'C': [1, 2]}

wanted_length = 20

Outputs :
'---AAAA---BBBBBBBB-C'
'---AAAA---BBBBBBB-CC'
'---AAA---BBBBBBBBB-C'
'---AAA---BBBBBBBB-CC'
'---AA---BBBBBBBBBB-C'
'---AA---BBBBBBBBB-CC'

I can see how I can do that with only one character, maybe two, but I have absolutely no idea of how I can deal with all the combinations ! Any ideas ?

EDIT

@AChampion asked me to show code in comments and explain where I'm stuck.

So, here is my current code (with new_strings being my final output) - it is fully working if you want to copy and paste it -:

import re

string = '---A---B-C'
split_string = re.findall('-*', string)
characters = re.findall('[A-Z]', string)
min_max_values = {'A': [2,4], 'B': [2, 15], 'C': [1, 2]}
wanted_length = 20
combinations = get_combinations(string, min_max_values, wanted_length)
new_strings = []

for combination in combinations:
    new_string = ''
    character_index = 0
    for chunk in cut_string:
        print new_string
        if chunk:
            new_string += chunk
        elif character_index < len(characters):
            character = characters[character_index]
            new_string += character*combination[character]
            character_index += 1
    new_strings.append(new_string)


def get_combinations(string, min_max_values, wanted_length):
    constant_length = string.count('-') # 7
    remaining_length = wanted_length - constant_length # 13
    # What I want to do : find combinations that will add up to the remaining_length
    # i.e. : combinations = [{'A': 4, 'B': 8, 'C': 1}, {'A': 4, 'B': 7, 'C': 2}, {'A': 3, 'B': 9, 'C': 1}, {'A': 3, 'B': 8, 'C': 2}, {'A': 2, 'B': 10, 'C': 1}, {'A': 2, 'B': 9, 'C': 2}]
    combinations = [{'A': 4, 'B': 8, 'C': 1}, {'A': 4, 'B': 7, 'C': 2}, {'A': 3, 'B': 9, 'C': 1}, {'A': 3, 'B': 8, 'C': 2}, {'A': 2, 'B': 10, 'C': 1}, {'A': 2, 'B': 9, 'C': 2}]
    return combinations

And I'm stuck at "combinations". I don't know how to automatically generate this dict. I would like to add up the three values so that they match the remaining length but I don't know how to do that. My even bigger problem is that this method has to work with any number of characters in the original string (e.g. ---A----B---D---E--F---G). The only given is that the string only contains dashes and characters ; and that the characters will always be in the min_max_values dict.

I didn't put this code in the first place because even the rest of my code seems wrong. I'm open to any input / improvement.

Answer 1

You can use itertools.product() to generate the combinations of 'A' and 'B' and then subtract from your wanted string length to see if you can fit 'C'. It's easier to operate on range()s so a quick dict comprehension can turn the min_max_values to a set of ranges:

import itertools as it

dashes = string.count('-')
ranges = {k: range(v[0], v[1]+1) for k, v in min_max_values.items()}
for a, b in it.product(ranges['A'], ranges['B']):
    c = wanted_length - dashes - a - b
    if c in ranges['C']:
        print('---{}---{}-{}'.format('A'*a, 'B'*b, 'C'*c))

Output:

---AA---BBBBBBBBB-CC
---AA---BBBBBBBBBB-C
---AAA---BBBBBBBB-CC
---AAA---BBBBBBBBB-C
---AAAA---BBBBBBB-CC
---AAAA---BBBBBBBB-C

To turn this into a list of dicts:

results = []
for a, b in it.product(ranges['A'], ranges['B']):
    c = wanted_length - dashes - a - b
    if c in ranges['C']:
        results.append({'A': a, 'B': b, 'C': c})
print(results)

Output:

[{'A': 2, 'B': 9, 'C': 2},
 {'A': 2, 'B': 10, 'C': 1},
 {'A': 3, 'B': 8, 'C': 2},
 {'A': 3, 'B': 9, 'C': 1},
 {'A': 4, 'B': 7, 'C': 2},
 {'A': 4, 'B': 8, 'C': 1}]

You could just it.product(ranges['A'], ranges['B'], ranges['C']) and get the same result but it is a little less efficient:

[{'A':a, 'B':b, 'C':c} for a, b, c in it.product(ranges['A'], ranges['B'], ranges['C']) if a+b+c=20-dashes]