Rotation and permutation

Remember our code from Swapping, reversing, and partitioning to reverse the order of words in a sentence? When the "sentence" contains only two words, there is another way to look at the reversal: you could consider it a cyclic rotation of the elements in the underlying range. std::rotate(a,mid,b) rotates the elements of the range [a,b) so that the element formerly addressed by mid is now at a (and returns an iterator pointing to the element whose value was formerly at a):

    template<class FwdIt>
    FwdIt rotate(FwdIt a, FwdIt mid, FwdIt b)
    {
      auto result = a + (b - mid);

      // First, reverse the whole range.
      std::reverse(a, b);

      // Next, un-reverse each individual segment.
      std::reverse(a, result);
      std::reverse(result, b);

      return result;
    }

    void test()
    {
      std::vector<int> v = {1, 2, 3, 4, 5, 6};
      auto five = std::find(v.begin(), v.end(), 5);
      auto one = std::rotate(v.begin(), five, v.end());
      assert((v == std::vector{5, 6, 1, 2, 3, 4}));
      assert(*one == 1);
    }

Another miscellaneous but sometimes useful permutative algorithm is std::next_permutation(a,b). Calling this function in a loop runs through all the possible permutations of n elements, which might be useful if you're trying to brute-force a solution to a (small) instance of the Traveling Salesman Problem:

    std::vector<int> p = {10, 20, 30};
    std::vector<std::vector<int>> results;

    // Collect the permutations of these three elements.
    for (int i=0; i < 6; ++i) {
      results.push_back(p);
      std::next_permutation(p.begin(), p.end());
    }

    assert((results == std::vector<std::vector<int>>{
      {10, 20, 30},
      {10, 30, 20},
      {20, 10, 30},
      {20, 30, 10},
      {30, 10, 20},
      {30, 20, 10},
    }));

Notice that next_permutation uses the idea of a "less-than relationship" to determine that one permutation is lexicographically "less than" another; for example, {20, 10, 30} is "less than" {20, 30, 10} because 10 is less than 30. Therefore, next_permutation also has a comparator-based version: std::next_permutation(a,b,cmp). There are also std::prev_permutation(a,b) and std::prev_permutation(a,b,cmp), which count lexicographically "downward" instead of "upward."

By the way, to compare two sequences lexicographically in this way, you could use std::mismatch from section Read-only range algorithms, or you could just use the standard-provided std::lexicographical_compare(a,b,c,d).