Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I got thrown off by an interview question recently,

What structure do you use to find all the ways up a ladder with N steps in 1 or 2 steps moves?

It occured to me today that a graph expansion could be used but it's not optimal because when N = 30, it evalates almost 700,000 nodes on a single round of expansion.

Here's the output of solving for N = 5.

2 2 1
2 1 2
1 2 2
2 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
1 1 1 1 1

My instinct is that maybe this problem can be solved with regular methods from Discrete Math that I'm just not remembering.

Is there a way to get the set of sequences containing (1, 2) where the sum of the elements is N?

If anyone is interested here's the code of the program I wrote.

share|improve this question
    
So, just to be sure: you want to actually print all the paths not just the amount of paths? –  M.B. Jun 12 '12 at 0:44
    
Yes, i was asked to say how I'd find all the paths. –  Aaron Anodide Jun 12 '12 at 0:50
add comment

2 Answers

up vote 3 down vote accepted

If $N=0$ there is one way: $\langle\rangle$. (No steps at all.) If $N=1$, there is one way, $\langle 1\rangle$. For $N>1$, take each way up a ladder of $N-2$ steps and append a $2$, and each way up a ladder of $N-1$ steps and append a $1$. Thus, for $N=2$ you get $\langle 2\rangle$ and $\langle 1,1\rangle$. The first few stages, with semicolons separating the paths derived from two steps back from those derived from one step back:

$$\begin{align*} &N=0: \langle\rangle\\ &N=1: \langle 1\rangle\\ &N=2: \langle 2\rangle;\langle 1,1\rangle\\ &N=3: \langle 1,2\rangle;\langle 2,1\rangle,\langle 1,1,1\rangle\\ &N=4: \langle 2,2\rangle,\langle 1,1,2\rangle;\langle 1,2,1\rangle,\langle 2,1,1\rangle,\langle 1,1,1,1\rangle \end{align*}$$

You never need to have more than two consecutive levels in storage at once, and it’s a straightforward generation with no trial and error. By the way, the number of paths for a given $N$ is $F_{N+1}$, the $(N+1)$-st Fibonacci number,

share|improve this answer
add comment

The number of such paths is the Fibonacci number $F_{n+1}$.

You can get the set $S_n$ of $n$-step paths recursively: append $1$ to each member of $S_{n-1}$, $2$ to each member of $S_{n-2}$, and take the union.

share|improve this answer
    
Heh. Beat me to the answer by 1 minute. –  Rick Decker Jun 12 '12 at 0:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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