I am trying to figure out all the possible random walks for a given distance and displacement, and it has a fairly complicated set of conditions.
The step sizes can vary, eg. the walk is not just a combination of +1s and -1s, but will include combinations of every integer within a given range excluding zero. In this case, I am using 7 as my maximum step size and distance (distance will be the absolute sum of all the steps). 7 will also be the maximum displacement (displacement is the final distance from the start, regardless of steps taken) and -7 will be the minimum displacement.
You can also think of this as compositions, but with negative integers. This would normally create an infinite list, but the distance stipulation solves this issue. In other words:
- What are all the unique ways you can make 7 using integers -6 through 7?
- What are all the unique ways you can make 6 using integers -5 through 7?
- What are all the unique ways you can make 5 using integers -4 through 7?
- What are all the unique ways you can make 4 using integers -3 through 7?
...
- What are all the unique ways you can make -6 using integers -7 through 5?
- What are all the unique ways you can make -7 using integers -7 through 6?
- Without an absolute sum that exceeds 7
- Excluding zero
- Order matters
One last possible approach would be to plot every integer point in the domain [0<x<7] and range [-7<y<7] and connect every point with lines of slope -7 through 7 (excluding zero). Every possible route that could be traced along these lines represents one of the many permutations, although it is possible for the distance to exceed 7 using this method so it's not great. Normally I would be alright with that, but it also becomes very complicated with the remaining conditions:
- This list represents random walks as every unique, iterable pattern possible within the given bounds. This means that +1+1+1+1+1 would represent the same pattern as +1 since it is just 5 repeated +1s. +2+2 is also the same as 2 repeated +2s, +1-3+1-3 is the same as 2 repeated +1-3s, etc. Somehow these permutations will have to be eliminated. It may be possible to do this by hand but I'm not completely sure on that.
- +1-3 is NOT the same as -2, these are completely different patterns.
- Displacements of 0 must also be eliminated. +0 or -0 also don't count as steps.
I have tried to start this by hand but I don't think that it's humanly possible to finish it that way so I'm wondering if there is anyone who might know how to make a python script that will generate a list of all of these possible permutations? Preferably it would be in order of displacement. I have absolutely no idea how long this list will be or how to even calculate that much. It would also be great if the code could be altered to generate lists with other distance/displacement/step size conditions besides 7, just in case it ends up being absurdly long. (For all I know, it could be anywhere from tens of thousands to hundreds of millions). There's a good chance that this has already been done, but if that's the case, then I'm wondering where I might be able to find an existing algorithm/what it might be called?
As for why? Well, I'm just gonna say donworrybout it for now lol