What I have is the following 'formula' : < +2 or -3 > (for example).
One can 'add 2 to' or 'substract 3 from' a starting digit recursively to form a next digit and add that digit to the the output. Then you can use the new digit for the next iteration.
So when the start digit is 1, that will be added tot the empty output, so the output will then be '1', then the only posibility is to add 2 to 1, so the next digit is 3, which will be added to the output, making the output '13' from here, the next posibility is again an add action, so the next digit will be 5, and the output will be '135', after this moment there are 2 possibilities, to add again so the next digit will be 7, another way is to substract 3 so the next digit will be 2, so the output can be '1357' or it can be '1352', etc.
The restrictions are not so complicated, one can only use the digits 1 to 9, and one can never reach the same digit within the same solution.
What I want to find is all possible combinations with a certain starting digit.
To find the first combination I add 2 to the previous digit as long as possible, and then try to substract 3, going back to adding 2, with the restriction that you can not use the same digit again, it gives:
1 + 3 + 5 + 7 + 9 + 6 + 8 -> (4 times add 2, 1 time substract 3, and 1 time add 2)
But the second (starting with an 1) will be:
1 + 3 + 5 + 7 + 4 + 6 + 8 -> (3x +2, 1x -3, and 2x +2)
and the third solution will be
1 + 3 + 5 + 2 + 4 + 6 + 8 -> (2x +2, 1x -3, and 3x +2)
so I find 3 solutions, all with a length of 7, doing this with only my brains :
'1357968', '1357468', '1352468'
As far as I see, there are 3 possibilities when starting with a 1.
I am researching a solution to find all posibilities with a start - digit.
The version starting with an 1 is easy to do with only a pen and paper, but other starting digits can be a bit more difficult.
My question is if there is some theory about this kind of 'formula's' or a research area, can someone get me some information to help me to develop an algoritm ?
Here a proposal in Python, what you name formula is given as a list of numbers ( (2, -3] in your case) :
# current : is a try on going
# deltas : contains the list of possible numbers to add
# return the possibilities as a list of int
def search(current : int, deltas):
unchanged = True # to know if an other digit was added or not
result = []
for delta in deltas:
x = current % 10 + delta
if (1 <= x <= 9) and not str(x) in str(current):
unchanged = False
result += search(current * 10 + x, deltas)
if unchanged:
result.append(current)
return result
Having that it is possible to compute all cases, so with the first digit from 1 to 9 :
for d in range(1,10):
print(d, " -> ", search(d, [2, -3]))
and that produces :
1 -> [1357968, 1357468, 1352468]
2 -> [2468579, 2463579, 241357968]
3 -> [357968, 357468, 35741, 352468, 35241]
4 -> [468579, 46852, 463579, 46352, 41357968, 41352]
5 -> [57968, 57963, 57468, 57463, 57413, 52468, 52463, 52413]
6 -> [68579, 6857413, 6852413, 63579, 635741, 635241]
7 -> [796852413, 79635241, 746852, 746352, 741352]
8 -> [857963, 857463, 857413, 852463, 852413]
9 -> [96857413, 96852413, 9635741, 9635241]
That proposal works on int, perhaps you prefer working with string because in your question you give result as string :
# current : is a try on going as str
# deltas : contains the list of possible numbers to add
# return the possibilities as a list of str
def search(current : str, deltas):
unchanged = True # to know if an other digit was added or not
result = []
for delta in deltas:
x = chr(ord(current[-1]) + delta)
if ('1' <= x <= '9') and not x in current:
unchanged = False
result += search(current + x, deltas)
if unchanged:
result.append(current)
return result
# compute all cases
for d in range(1,10):
print(d, " -> ", search(str(d), [2, -3]))
printing
1 -> ['1357968', '1357468', '1352468']
2 -> ['2468579', '2463579', '241357968']
3 -> ['357968', '357468', '35741', '352468', '35241']
4 -> ['468579', '46852', '463579', '46352', '41357968', '41352']
5 -> ['57968', '57963', '57468', '57463', '57413', '52468', '52463', '52413']
6 -> ['68579', '6857413', '6852413', '63579', '635741', '635241']
7 -> ['796852413', '79635241', '746852', '746352', '741352']
8 -> ['857963', '857463', '857413', '852463', '852413']
9 -> ['96857413', '96852413', '9635741', '9635241']
To refer to a comment I did two days ago, if you forget the details associated to these implementations in Python I am pretty sure you find the algorithm you executed in your head to give the results when starting with 1. It tries all possibilities, this is the brutal force, and this is not a problem because there are few cases.