• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Stairclimber a guest Feb 21st, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. vector< vector<int> > get_ways(int num_stairs) {
2.     /* Returns a vector of vectors of ints representing
3.     the different combinations of ways to climb num_stairs
4.     stairs, moving up either 1, 2, or 3 stairs at a time.
5.     Optimized to use a modified integer partition algorithm. */
6.     vector<vector<int>> all_ways;
7.     vector<int> p(num_stairs, 0);
8.     if (num_stairs < 4) {
9.         all_ways.push_back(vector<int>{num_stairs});
10.     }
11.     int k = 0;
12.     p[k] = num_stairs;
13.     while (true) {
14.         // Generate next partition
15.         // Find the rightmost non - one value in p[].
16.         // Also, update the rem_val so that we know
17.         // how much value can be accommodated
18.         int rem_val = 0;
19.         while (k >= 0 && p[k] == 1) {
20.             rem_val += p[k];
21.             k -= 1;
22.         }
23.         // if k < 0, all the values are 1 so
24.         // there are no more partitions
25.         if (k < 0) return all_ways;
26.         // Decrease the p[k] found above and adjust the rem_val
27.         p[k] -= 1;
28.         rem_val += 1;
29.         // Ensure values are below or equal to 3 before increment
30.         while (p[k] > 3) {
31.             p[k] -= 1;
32.             rem_val += 1;
33.         }
34.         // Copy rem_val to next position
35.         // and increment position
36.         p[k + 1] = rem_val;
37.         k += 1;
38.         // Keep values only if they at most 3
39.         if (rem_val > 3) continue;
40.         vector<int> valid_p;
41.         // Add non-zero values (everything before k + 1)
42.         for (int i=0; i < k + 1; i++) {
43.             valid_p.push_back(p[i]);
44.         }
45.         all_ways.push_back(valid_p);
46.     }
47. }
48.
49. void display_ways(const vector< vector<int> > &ways) {
50.     /* Iterates through the ways to climb the stairs and displays them
51.     **Must be printed in reverse for the partition algorithm */
52.     int width = ways.size() == 0 ? 1 : log10(abs(long(ways.size()))) + 1;
53.     // for (unsigned int i=0; i < ways.size(); i++) {
54.     for (unsigned int i=ways.size() - 1; i >= 0; i--) {
55.         cout << setw(width) << ways.size() - i << ". [";
56.         for (unsigned int j=0; j < ways[i].size(); j++) {
57.             cout << ways[i][j];
58.             if (j < ways[i].size() - 1) {
59.                 cout << ", ";
60.             }
61.         }
62.         cout << "]" << endl;
63.     }
64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top