Given an input generate all combinations where each digit is one bigger or one smaller

Question

So for example given 123456, no digits can be unchanged but each will either go up one or down one for example 234567 or 012345 or 212565. I believe there should be 2^N combinations, where N is the number of digits.

I have no idea where to start. I was thinking for loops but I can't think of a systematic way to run through every combination.

Answer 1

You're correct in your approach of using a systematic method to generate all combinations where each digit in a given number is either increased or decreased by one. For a number with N digits, there indeed are 2^N such combinations. This is because for each digit, you have two choices: either increase it by one or decrease it by one.
The function generates all combinations for a given number where each digit is either increased or decreased by one. For the example "123456", it successfully creates 64 combinations, as expected for a 6-digit number (2^6=64). The function works for any number of digits and provides a set of strings representing all possible combinations according to your criteria.

 def generate_combinations(number_str):
    if not number_str:
        return {''}  # Base case: return a set with an empty string
    smaller_combinations = generate_combinations(number_str[1:])
    digit = int(number_str[0])
    new_combinations = set()
    for combo in smaller_combinations:
        if digit < 9:
            new_combinations.add(str(digit + 1) + combo)
        if digit > 0:
            new_combinations.add(str(digit - 1) + combo)
    return new_combinations

  test_number = "123456"
  combinations = generate_combinations(test_number)
  print(len(combinations), combinations)

Output : 64 {'234367', '032547', '014545', '214545', '232545', '014567', '034567', '214547', '212345', '212567', '014365', '012347', '214347', '032345', '232347', '034367', '234545', '034347', '014347', '012367', '214345', '234365', '012545', '032365', '032347', '234567', '212545', '232565', '212347', '214565', '214567', '014547', '012345', '214367', '014565', '232367', '034365', '232345', '034565', '032565', '034545', '232567', '234345', '232365', '234565', '212565', '032545', '234347', '012547', '012365', '012567', '214365', '212547', '014367', '032567', '232547', '212365', '034345', '034547', '234547', '014345', '212367', '012565', '032367'}

Changing to accommodate 0 and 9

def generate_combinations(number_str):
    if not number_str:
        return {''}  # Base case: return a set with an empty string
    smaller_combinations = generate_combinations(number_str[1:])
    digit = int(number_str[0])
    new_combinations = set()
    for combo in smaller_combinations:
        if digit < 9:
            new_combinations.add(str(digit + 1) + combo)
        if digit > 0:
            new_combinations.add(str(digit - 1) + combo)
        if digit == 0:
            new_combinations.add(str(9) + combo)
        if digit == 9:
            new_combinations.add(str(0) + combo)
    return new_combinations

test_number = "0123496"
combinations = generate_combinations(test_number)
print(len(combinations), combinations)

Output: 128 {'9234585', '9232587', '9212305', '1212307', '1212385', '1212585', '9232307', '1012305', '1032587', '1214387', '9234387', '1012505', '1234505', '1014307', '1032585', '1012307', '1212305', '9012505', '1232305', '9014585', '9214505', '1032505', '1012585', '9012587', '9032385', '9012305', '1234307', '9034387', '9014305', '1034585', '9032585', '1234507', '1232585', '9014505', '1034505', '9034587', '1214307', '9034385', '1032387', '9012585', '9032505', '1012387', '9214385', '1212505', '1234387', '1232307', '1214505', '1234585', '9212385', '9014307', '1034385', '1212587', '1032385', '9232385', '1034587', '1234587', '1034305', '9234307', '9232505', '1234385', '9014507', '9014385', '9212587', '1214587', '9234507', '1014387', '9032307', '9014387', '1014505', '1034507', '9212387', '9034585', '9232387', '1014305', '1032305', '1014385', '9012307', '9232305', '9212307', '1232387', '1212387', '1214507', '1232385', '1232587', '9214587', '9234587', '9212585', '9034507', '1034387', '9034305', '9012387', '1014507', '9214387', '9032587', '1014585', '9214585', '9214507', '9212507', '1214305', '9014587', '1212507', '1214385', '9214305', '1032507', '9234505', '9214307', '9032507', '9032387', '9234305', '1034307', '9012507', '1032307', '9232507', '9232585', '1012587', '1232507', '9034505', '1014587', '1214585', '9012385', '1232505', '9034307', '1012507', '9234385', '1012385', '9032305', '9212505', '1234305'}