Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- vector< vector<int> > get_ways(int num_stairs) {
- /* Returns a vector of vectors of ints representing
- the different combinations of ways to climb num_stairs
- stairs, moving up either 1, 2, or 3 stairs at a time.
- Optimized to use a modified integer partition algorithm. */
- vector<vector<int>> all_ways;
- vector<int> p(num_stairs, 0);
- if (num_stairs < 4) {
- all_ways.push_back(vector<int>{num_stairs});
- }
- int k = 0;
- p[k] = num_stairs;
- while (true) {
- // Generate next partition
- // Find the rightmost non - one value in p[].
- // Also, update the rem_val so that we know
- // how much value can be accommodated
- int rem_val = 0;
- while (k >= 0 && p[k] == 1) {
- rem_val += p[k];
- k -= 1;
- }
- // if k < 0, all the values are 1 so
- // there are no more partitions
- if (k < 0) return all_ways;
- // Decrease the p[k] found above and adjust the rem_val
- p[k] -= 1;
- rem_val += 1;
- // Ensure values are below or equal to 3 before increment
- while (p[k] > 3) {
- p[k] -= 1;
- rem_val += 1;
- }
- // Copy rem_val to next position
- // and increment position
- p[k + 1] = rem_val;
- k += 1;
- // Keep values only if they at most 3
- if (rem_val > 3) continue;
- vector<int> valid_p;
- // Add non-zero values (everything before k + 1)
- for (int i=0; i < k + 1; i++) {
- valid_p.push_back(p[i]);
- }
- all_ways.push_back(valid_p);
- }
- }
- void display_ways(const vector< vector<int> > &ways) {
- /* Iterates through the ways to climb the stairs and displays them
- **Must be printed in reverse for the partition algorithm */
- int width = ways.size() == 0 ? 1 : log10(abs(long(ways.size()))) + 1;
- // for (unsigned int i=0; i < ways.size(); i++) {
- for (unsigned int i=ways.size() - 1; i >= 0; i--) {
- cout << setw(width) << ways.size() - i << ". [";
- for (unsigned int j=0; j < ways[i].size(); j++) {
- cout << ways[i][j];
- if (j < ways[i].size() - 1) {
- cout << ", ";
- }
- }
- cout << "]" << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement