1
$\begingroup$

I have a solution to the following problem:

Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the time ($1 \leq m \leq n$), return all the ways you can climb the stairway.

E.g. for $n = 3$, $m = 2$, the possible ways to climb are $[2,1], [1,2], [1,1,1]$

// outputs all the ways to react total using steps from 1 to max;
// returns the count of iterations
function permut(total, max, out) {
  // store unfinished tracks; start with an initial track
  let iter = [{ val: [], sum: 0 }];
  let count = 0;

  // take the next track until there are none
  for (let i of iter) {
    for (let s = 1; s <= max; s++) {
      // append step value to the current track
      // assume constant complexity
      let val = [...i.val, s];
      let sum = i.sum + s;

      count++;

      if (sum === total) {
        // we've reached the top;
        // do not expand current track further
        out(val);
        break;
      }

      // add an unfinished track and start over
      iter.push({ val, sum });
    }
  }

  return count;
}

Codesandbox: https://codesandbox.io/s/busy-cdn-7idu9

However, I can't figure out the time complexity relatively to $m$ and $n$. For $m = 1$ the number of iterations is $n$, for $m = n$ it's $2^n - 1$.

Also, is there a canonical solution to this problem?

$\endgroup$
  • $\begingroup$ So what if sum > total? $\endgroup$ – gnasher729 Aug 21 at 17:05
  • 1
    $\begingroup$ Shouldn't happen if valid inputs are provided $\endgroup$ – Pavlo Aug 21 at 19:04
  • 1
    $\begingroup$ Can you express your algorithm in concise language-independent pseudocode, so we don't have to understand Javascript syntax or the meaning of things like iter.push() or [...i.val, s]? $\endgroup$ – D.W. Aug 28 at 6:43
  • $\begingroup$ @D.W. I don't think I can do any better in pseudocode, but I added few more comments $\endgroup$ – Pavlo Aug 28 at 8:09
  • $\begingroup$ But what is the cost of [...i.val, s]? Linear? Constant? Depends on the compiler? $\endgroup$ – Peter Taylor Aug 28 at 9:15
3
$\begingroup$

The solution is the recursive formula:

$S[k] = \sum_{i=1}^mS[k-i]$

For $m=2$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $O(m \cdot n)$.

Consider the last step before reaching step $k$, the number of ways to reach $k$ when the last step is $i$, is equal to the number of steps to reach $S[k-i]$

$\endgroup$
  • 1
    $\begingroup$ Note that if $m$ is small and $n$ is large you might want to consider rewriting this in matrix form and then use fast exponentiation, to get a runtime of $O(m^3\log(n))$, or even $O(m^{2.376}\log(n))$ if you use the Coppersmith–Winograd algorithm for the matrix multiplication steps. $\endgroup$ – Tassle Aug 28 at 12:15
  • $\begingroup$ Thanks for the answer! This assumes 𝑆[𝑘] is only calculated once per 𝑘, correct? What complexity it would be otherwise? $\endgroup$ – Pavlo Aug 28 at 14:04
  • 1
    $\begingroup$ Yes, it assumes that the calculation is done once, otherwise, with recursion (without memory) it will be $O(m^n)$ since every step makes m recursion calls $\endgroup$ – S.A Aug 28 at 14:35
2
$\begingroup$

What you are looking for is the so-called partition function (with some constraints on the addends). A simple upper bound is the number of solutions (and thus for the runtime since you generate all of them). For the unconstrained case this is $e^{c\sqrt n}$ as per Siegel with c=$\pi\sqrt\frac{2}{3}$.

There are several specialised formulas with tighter bounds depending on certain contraints (see https://en.wikipedia.org/wiki/Partition_(number_theory) for lots of them) but generally the dominating term will be in the order of $n!$.

In (de Azevedo Pribitkin, W. Ramanujan J (2009) 18: 113. https://doi.org/10.1007/s11139-007-9022-z) an upper bound of $\frac{e^{c\sqrt n}} {n^{3/4}}$ is given. Without further assumptions about $m$ that is probably the best bound we can give while keeping the formula simple.

$\endgroup$
  • $\begingroup$ Thanks for the answer! So where is 𝑚 in this formula? $\endgroup$ – Pavlo Sep 4 at 7:11
  • $\begingroup$ As I said, you need further assumptions about 𝑚 to decrease the bound. If for instance $m$ would be 3 you could lower the bound to $\frac{n^2}{3!} + O(n)$. (This is from the Asymptotics part of the wiki page.) The exponent $2$ coming from $m-1$. $\endgroup$ – Eisenknurr Sep 4 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.