all possible steps by 1 or 2 to reach nth stair

Question

I am working on a python program where I want to find all possible ways to reach nth floor.

Here is my program taken from here:

# A program to count the number of ways to reach n'th stair 

# Recurssive program to find n'th fibonacci number 
def fib(n): 
    if n <= 1: 
        return n 
    return fib(n-1) + fib(n-2) 

# returns no. of ways to reach s'th stair 
def countWays(s): 
    return fib(s + 1) 

# Driver program 

s = 10
print("Number of ways = ", countWays(s) )

Here I am getting the total number of ways to reach nth floor, but I want a function that can return an array of all possible ways to reach nth floor.

Example:
1) s = 3 output should be the possible steps which are {1,1,1}, {2,1}, {1,2}.

2) s = 10, has 89 combinations:

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

Update:

I found this working code in Java, I am not able to understand how do I change this to python

public static void main(String args[]) {
    int s = 10;
    List<Integer> vals = new ArrayList<>();
    ClimbWays(s, 0, new int[s], vals);
    vals.sort(null);
    System.out.println(vals);
}

public static void ClimbWays(int n, int currentIndex, int[] currectClimb, List<Integer> vals) {
    if (n < 0)
        return;

    if (n == 0) {
        vals.add(currentIndex);
        int last = 0;
        for (int i = currentIndex - 1; i >= 0; i--) {
            int current = currectClimb[i];
            int res = current - last;
            last = current;
            System.out.print(res + " ");
        }

        System.out.println();
        return;
    }

    currectClimb[currentIndex] = n;
    ClimbWays(n - 1, currentIndex + 1, currectClimb, vals);
    ClimbWays(n - 2, currentIndex + 1, currectClimb, vals);
}

rassar · Accepted Answer · 2019-11-01T20:20:57.697

2

It seems like you are looking for a modification of the partitions of a number:

import itertools as it

def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p

def countWays(s):
    for i in partitions(s):
        if s in i: continue # just the original number
        yield from set(it.permutations(i)) # set to remove duplicates

print(list(countWays(3)))

Displays:

[(1, 2), (2, 1), (1, 1, 1)]

Note that this will return them in no particularly sorted order.

(Partitions algorithm from here.)

Here is a conversion of your java code into python:

def climbWays(n, currentIndex, currentClimb, vals):
    if n < 0:
        return

    if n == 0:
        vals.append(currentIndex)
        last = 0
        for i in range(currentIndex - 1, -1, -1):
            current = currentClimb[i]
            res = current - last
            last = current
            print(res, end=" ")
        print()
        return

    currentClimb[currentIndex] = n
    climbWays(n - 1, currentIndex + 1, currentClimb, vals)
    climbWays(n - 2, currentIndex + 1, currentClimb, vals)

s = 10
vals = []
climbWays(s, 0, [0] * s, vals)
vals.sort()
print(vals)

edited Nov 01 '19 at 20:20

answered Nov 01 '19 at 00:44

rassar

5,412
3
25
41

I have a restriction in my task, that I have to use steps 1 or 2 only to reach the end point, so when I tried with input as 10 with this program, I see steps 3, 4, 5 which is not correct. Can you please help me how to fix this? – learner Nov 01 '19 at 18:21
What's your expected output for 10 stairs? Do you want the higher stairs to be expressed as the sums of stairs 1 and 2? – rassar Nov 01 '19 at 19:16
For input = 10, we will get 89 combinations using 1 and 2 values – learner Nov 01 '19 at 19:30
I added all the 89 combinations for input = 10 to my question – learner Nov 01 '19 at 19:35
Also I found a Java code which is working correctly, I am not able to understand how to change this to python now – learner Nov 01 '19 at 19:41
@rassar What is the purpose of sorting `vals`? – a_sid Jan 03 '21 at 21:44
@a_sid I sorted `vals` to just confirm for myself that every partition was in the list; there's no purpose if you just want a list of unordered partitions. – rassar Jan 03 '21 at 22:05
@a_sid also because the java code sorted vals, and I was transcribing it – rassar Jan 03 '21 at 22:12
@rassar Do you not know the reason behind doing this? – a_sid Jan 03 '21 at 22:55
@rassar _I sorted vals to just confirm for myself that every partition was in the list; there's no purpose if you just want a list of unordered partitions._ Oh ok. I did not notice this comment earlier. – a_sid Jan 04 '21 at 01:43

all possible steps by 1 or 2 to reach nth stair

1 Answers1