Algorithms: One Call Instead of a Loop, and Every Order of a Set

Bob is seating friends in a row of chairs for a photo, and he wants to try every seating. For three friends he writes three nested loops, and for six friends six. Then Maria tells him that nobody knows how many friends will come, and no fixed nest of loops fits that. At the end of the day, Amara asks him for the café's total, its biggest hour and how many hours sold 30 cups. He writes three more loops, and one of them starts at index 1 instead of 0.

Each of those jobs is one call in the standard library. This lesson shows the calls, how they see a container, and what each one costs.

An algorithm is a function that takes a range

In the STL, an algorithm is a function that works on a range of elements, not on a container. You hand it two iterators from Module 11, first and last. It uses first and every element after it, up to last but not including it. That is the half-open range [first, last).

The algorithms that do arithmetic, such as accumulate, live in the header <numeric>. The rest, such as count, max_element, reverse and next_permutation, live in <algorithm>. Here are two calls, each on the whole vector and then on a part of it.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> sold{4, 7, 2, 9, 5, 7};
    cout << accumulate(sold.begin(), sold.end(), 0) << '\n';
    cout << accumulate(sold.begin() + 1, sold.begin() + 4, 0) << '\n';
    cout << count(sold.begin(), sold.end(), 7) << '\n';
    cout << count(sold.begin(), sold.begin() + 3, 7) << '\n';
    return 0;
}

34
18
2
1

The whole vector adds up to 34. sold.begin() + 1 to sold.begin() + 4 covers positions 1, 2 and 3, so the second line is 7 + 2 + 9 = 18. count found two 7s in the whole vector, and one in its first three positions.

So the same call works on a whole vector or on any stretch of it, and only the two iterators change.

Four loops you no longer write

Here are Amara's end-of-day numbers: cups sold in each of five hours. The program answers each question twice, first with Bob's hand loops, then with one call each. Then it turns the vector around with reverse.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> cups{12, 30, 18, 30, 9};

    int total = 0;
    for (int x : cups) {
        total += x;
    }
    int biggest = cups[0];
    for (int x : cups) {
        if (x > biggest) {
            biggest = x;
        }
    }
    int thirties = 0;
    for (int x : cups) {
        if (x == 30) {
            thirties++;
        }
    }
    cout << "loops: " << total << ' ' << biggest << ' ' << thirties << '\n';

    cout << "calls: " << accumulate(cups.begin(), cups.end(), 0) << ' '
         << *max_element(cups.begin(), cups.end()) << ' '
         << count(cups.begin(), cups.end(), 30) << '\n';

    reverse(cups.begin(), cups.end());
    cout << "reversed:";
    for (int x : cups) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

loops: 99 30 2
calls: 99 30 2
reversed: 9 30 18 30 12

Both ways print the same numbers. The calls have no index to start at 1 by mistake, and no best-so-far to start at the wrong value. There is no <= to type in place of < either. max_element returns an iterator, not a value, so the program reads the value with *. So each call is one line that names its job, and the loop is gone.

Every order of a set: next_permutation

Bob's seatings are permutations: every order of the same items. Three friends can sit in 3 × 2 × 1 = 6 orders, written 3! and read "3 factorial". To list them without nested loops, put the orders in dictionary order. Compare two orders by their first item, then by the second if the first ones tie, as a dictionary compares words.

next_permutation(first, last) rearranges the range into the next order in dictionary order and returns true. When the range already holds the last order, the largest, it returns false. It also rearranges the range back into the first order, the smallest. So a loop that calls it until it says false visits every order once.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> seat{1, 2, 3};
    int orders = 0;
    do {
        cout << seat[0] << ' ' << seat[1] << ' ' << seat[2] << '\n';
        orders++;
    } while (next_permutation(seat.begin(), seat.end()));
    cout << orders << " orders, and seat is back to " << seat[0] << ' ' << seat[1] << ' ' << seat[2] << '\n';
    return 0;
}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
6 orders, and seat is back to 1 2 3

The loop is a do-while because the first order, 1 2 3, must be used before the first call moves it. After 3 2 1 the call returned false and left 1 2 3 behind, so the loop stopped with the vector back where it began. The same five lines work for 3 friends, 6 friends or n friends. So next_permutation replaces Bob's nest of loops, whatever the number of chairs.

Watch next_permutation step through 1 2 3

Each call makes the smallest change that gives a bigger order, in four moves. It finds the last rise: the rightmost position i where v[i] < v[i + 1]. It finds the rightmost element after it that is bigger than v[i], and swaps the two. Then it reverses everything after position i. If there is no rise at all, the range is the largest order, so the call reverses the whole range and returns false.

The widget plays the six calls on vector<int> v{1, 2, 3}, one row per call. Every row was printed by a program on Compiler Explorer that made these moves by hand, and every row was checked against std::next_permutation.

Call 2 shows all four moves. The rise is at the 1, the 1 swaps with the 2, and the tail 3 1 turns into 1 3. Call 6 finds no rise in 3 2 1, so it reverses everything into 1 2 3 and returns false. Lesson 05 reads GCC 12's own code for these moves. So each call changes as little as it can, and the orders come out smallest first.

The syntax you need on day one

#include <numeric>      accumulate, and the other arithmetic algorithms
#include <algorithm>    count, max_element, min_element, reverse, sort, next_permutation

accumulate(first, last, init)     init plus every element; the result has init's type
count(first, last, x)             how many elements equal x
max_element(first, last)          an iterator to the first largest element
min_element(first, last)          an iterator to the first smallest element
*it                               the element an iterator points at
it - v.begin()                    that element's index in a vector
reverse(first, last)              turn the range around, in place

sort(v.begin(), v.end());                          start from the smallest order
do {
    ... use v ...
} while (next_permutation(v.begin(), v.end()));   every order once, smallest first

So two headers and seven calls cover this lesson, and every call takes its range the same way.

Sort first, or you miss orders

next_permutation only moves forward in dictionary order. Start it in the middle, and it never visits the orders that come before the start. This program counts the orders from 2 1 3, then sorts and counts again.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int countOrders(vector<int> v) {
    int orders = 0;
    do {
        orders++;
    } while (next_permutation(v.begin(), v.end()));
    return orders;
}

int main() {
    vector<int> friends{2, 1, 3};
    cout << "from 2 1 3: " << countOrders(friends) << " orders\n";
    sort(friends.begin(), friends.end());
    cout << "from 1 2 3: " << countOrders(friends) << " orders\n";
    return 0;
}

from 2 1 3: 4 orders
from 1 2 3: 6 orders

From 2 1 3 the loop saw 2 1 3, 2 3 1, 3 1 2 and 3 2 1: four of the six. The two orders before the start, 1 2 3 and 1 3 2, were never visited. After sort, all six came out. With a repeated value, each different order comes out once: 1 1 2 gives three orders, not six, and lesson 02 steps through them. So sort first, every time.

The start value sets the type

accumulate keeps its running total in the type of its start value, not in the type of the elements. That matters at both ends: for big sums and for fractions.

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> steps(100000, 100000);
    cout << accumulate(steps.begin(), steps.end(), 0) << '\n';
    cout << accumulate(steps.begin(), steps.end(), 0LL) << '\n';

    vector<double> prices{1.5, 2.5, 3.5};
    cout << accumulate(prices.begin(), prices.end(), 0) << '\n';
    cout << accumulate(prices.begin(), prices.end(), 0.0) << '\n';
    return 0;
}

1410065408
10000000000
6
7.5

100000 days of 100000 steps make 10000000000, far past the largest int, 2147483647. With 0 the total is an int, so it wrapped, and GCC 12 printed 1410065408. Signed overflow is undefined behaviour, so that number is what this compiler did, not a promise; lesson 05 explains where it comes from. With 0LL the total is a long long, and the answer is right.

The prices add up to 7.5, but 0 made the total an int again. Each step was cut back to a whole number: 0 + 1.5 became 1, then 3.5 became 3, then 6.5 became 6. With 0.0 the total is a double. So write the start value in the type of the answer you want.

What each call costs

accumulate, count, max_element and min_element look at each element once: n steps for n elements, O(n). reverse makes n / 2 swaps, also O(n). A hand loop doing the same job costs the same, so the call is never the slow choice.

One call of next_permutation costs O(n) at worst, when it reverses the whole range, as call 6 did. Over all the orders, though, it averages about 3 comparisons a call: 2.5 at n = 3 and 3.08 at n = 10, counted on Compiler Explorer. The real cost is the number of orders. n items have n! orders, and each extra item multiplies them. This program times the full do-while for 8 to 11 items.

#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    for (int n = 8; n <= 11; n++) {
        vector<int> v(n);
        iota(v.begin(), v.end(), 1);
        auto t0 = chrono::steady_clock::now();
        long long count = 0, check = 0;
        do {
            count++;
            check += v[0];
        } while (next_permutation(v.begin(), v.end()));
        auto t1 = chrono::steady_clock::now();
        cout << n << ": " << count << " orders, " << chrono::duration<double, milli>(t1 - t0).count() << " ms (" << check << ")\n";
    }
    return 0;
}

Eleven runs on Compiler Explorer's GCC 12.2 at -O2 -std=c++17, with a different comment each run so nothing came from a cache. The same input ran 2 to 3 times slower in some runs than in others, so read each row as a range. Each step up multiplies the time by about n, as n! says. 12 items would mean 479001600 orders, about 12 times the 11-item time. So visiting every order is fine up to about 10 or 11 items, and real work inside the loop only adds to it.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    vector<int> sales{120, 45, 300, 45, 80};
    cout << "total: " << accumulate(sales.begin(), sales.end(), 0) << '\n';
    cout << "largest: " << *max_element(sales.begin(), sales.end()) << '\n';
    cout << "sales of 45: " << count(sales.begin(), sales.end(), 45) << '\n';
    return 0;
}

total: 590
largest: 300
sales of 45: 2

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string secret = "853";   // the lock knows it; Kenji does not
    string code = "583";     // the three digits, in the order Kenji remembers
    sort(code.begin(), code.end());
    int tries = 0;
    do {
        tries++;
        cout << "try " << tries << ": " << code << '\n';
        if (code == secret) {
            break;
        }
    } while (next_permutation(code.begin(), code.end()));
    cout << "open after " << tries << " tries\n";
    return 0;
}

try 1: 358
try 2: 385
try 3: 538
try 4: 583
try 5: 835
try 6: 853
open after 6 tries

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> names{"alice", "bob", "david", "zara"};
    vector<int> score{72, 91, 85, 91};
    auto best = max_element(score.begin(), score.end());
    int at = best - score.begin();
    cout << "top score " << *best << " at index " << at << ": " << names[at] << '\n';
    return 0;
}

top score 91 at index 1: bob

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{1, 2, 3};
    cout << accumulate(v.begin(), v.end(), 0) << '\n';
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{3, 1, 2};
    cout << *max_element(v.begin(), v.end()) << '\n';
    reverse(v.begin(), v.end());
    return 0;
}

vector<int> friends{2, 1, 3};
int orders = 0;
do {
    orders++;
} while (next_permutation(friends.begin(), friends.end()));
cout << orders << '\n';

vector<double> prices{1.5, 2.5, 3.5};
cout << accumulate(prices.begin(), prices.end(), 0) << '\n';

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{3, 1, 2};
    int count = 0;
    do {
        count++;
    } while (next_permutation(v.begin(), v.end()));
    cout << count << '\n';
    for (int x : v) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    vector<string> words;   // every different word, in dictionary order

    // Visit every arrangement of the letters of s with next_permutation,
    // and add each one to words.

    cout << words.size() << '\n';
    for (const string& w : words) {
        cout << w << '\n';
    }
    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    int mirrors = 0;       // how many words read the same backwards
    string longest = "";   // the longest of them so far

    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        // Make a reversed copy of word with reverse. If the two are equal,
        // count the word, and keep it if it is longer than longest.
    }

    // Line 1: mirrors. Line 2: longest, or none if no word was a mirror.

    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> cards(n);   // each card's number, kept as text
    for (string& c : cards) {
        cin >> c;
    }
    string best = "";   // the biggest number found so far

    // Try every order of the cards. For each order, join the cards into one
    // string; keep it if it is a bigger number than best. Every joined string
    // has the same length, so comparing two of them as strings works.
    // Print best.

    return 0;
}

Next, lesson 02 goes through every algorithm of the weekly set, one by one, each with its cost.