0
$\begingroup$

This is basically a follow-up to Climbing/Descending the Integer Ladder, but in multiple dimensions. It's basically just an index counting problem, but combinatoric blow-up makes it interesting.

In that question, we had a single ladder that we could climb up or down, and we wanted to hit some target integer $k$ over $m$ steps. I'd like to extend this to higher-dimensions.

Let's assume we have a sequence of numbers of steps, $\{m_i\}$, where $i=1..N$ (i.e. this is an $N$-dimensional problem) and each of these $\{m_i\}$ can be partitioned over $N$ ladders, e.g. if $N=7$ and $m_3=5$ then I can do a single step on 5 of the 7 ladders, or 2 on the first, and 1 on three others, etc.

The question is then, how many different ways can we do this partitioning so that after we're done with all $N$ climbing/descending operations we end up at $0$ on all of the ladders. All of the ladders are equivalent, so the following paths are equivalent in this kind of picture (for $\{m_i\}=\{3, 3, 2\}$)

{{-3, 0, 0}, {2, -1,0}, {1, 1,0}} <-> {{0, -3, 0}, {-1, 2, 0}, {1, 1, 0}}

since all we did was transpose the indices. In general, I actually have that some of the ladders will be equivalent and some won't (i.e. there'll be a prescribed transposition symmetry to the indices), but I think that'll make the solutions more complicated and the problem less fun.

Here's the naive approach that takes no advantage of symmetry and is just based on pruning the total list of candidates.


ladderUpAndDownPaths[changes : {__Integer}] :=
 Block[
  {
   maxDim = Max[changes],
   displacements
   },
  displacements =
   Function[{dim},
     Select[
      Tuples[Range[-dim, dim], maxDim],
      Total[Abs[#]] == dim &
      ]
     ] /@ changes;
  Select[Tuples[displacements], AllTrue[Total[#], EqualTo[0]] &]
  ]

which gives

ladderUpAndDownPaths[{2, 2}]//Column

{{-2,0},{2,0}}
{{-1,-1},{1,1}}
{{-1,1},{1,-1}}
{{0,-2},{0,2}}
{{0,2},{0,-2}}
{{1,-1},{-1,1}}
{{1,1},{-1,-1}}
{{2,0},{-2,0}}

but of course this blows up

ladderUpAndDownPaths[{3, 3, 2}]

{{-3,0,0},{2,-1,0},{1,1,0}}
{{-3,0,0},{2,0,-1},{1,0,1}}
{{-3,0,0},{2,0,1},{1,0,-1}}
{{-3,0,0},{2,1,0},{1,-1,0}}
{{-2,-1,0},{1,1,-1},{1,0,1}}
{{-2,-1,0},{1,1,1},{1,0,-1}}
{{-2,-1,0},{1,2,0},{1,-1,0}}
{{-2,-1,0},{2,-1,0},{0,2,0}}
{{-2,-1,0},{2,0,-1},{0,1,1}}
{{-2,-1,0},{2,0,1},{0,1,-1}}
{{-2,-1,0},{3,0,0},{-1,1,0}}
{{-2,0,-1},{1,-1,1},{1,1,0}}
{{-2,0,-1},{1,0,2},{1,0,-1}}
{{-2,0,-1},{1,1,1},{1,-1,0}}
{{-2,0,-1},{2,-1,0},{0,1,1}}
{{-2,0,-1},{2,0,-1},{0,0,2}}
...
{{2,0,1},{-2,1,0},{0,-1,-1}}
{{2,0,1},{-1,-1,-1},{-1,1,0}}
{{2,0,1},{-1,0,-2},{-1,0,1}}
{{2,0,1},{-1,1,-1},{-1,-1,0}}
{{2,1,0},{-3,0,0},{1,-1,0}}
{{2,1,0},{-2,0,-1},{0,-1,1}}
{{2,1,0},{-2,0,1},{0,-1,-1}}
{{2,1,0},{-2,1,0},{0,-2,0}}
{{2,1,0},{-1,-2,0},{-1,1,0}}
{{2,1,0},{-1,-1,-1},{-1,0,1}}
{{2,1,0},{-1,-1,1},{-1,0,-1}}
{{3,0,0},{-2,-1,0},{-1,1,0}}
{{3,0,0},{-2,0,-1},{-1,0,1}}
{{3,0,0},{-2,0,1},{-1,0,-1}}
{{3,0,0},{-2,1,0},{-1,-1,0}}
```
$\endgroup$
2
  • $\begingroup$ This smells like homework / coursework / contest work in disguise. Is it? $\endgroup$
    – ciao
    Nov 4, 2020 at 17:09
  • $\begingroup$ @ciao nah it's actually something that just came up as I'm trying to optimize an algorithm I use in research and felt like a good mathematica.SE problem. My guess is that this kind of thing has been worked out before, but I don't know where to look... $\endgroup$
    – b3m2a1
    Nov 4, 2020 at 17:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.