Assume False

Flux Permutations Adaptor (1/4)

Using C++ coroutines for a simple permutations adaptor.

flux

cpp

coroutine

I’ve been using the Flux C++ library for a while now, ever since hearing Tristan Brindle talk about it on the ADSP podcast. As a brief introdution for the unintroduced, Flux is a library for “sequence-oriented programming, similar in spirit to C++20 ranges, Python itertools, and Rust iterators.” Flux provides an easy API to apply algorithms to sequences. For example, this is how you might sum all even integers from 0 to 10 using Flux.

1
2
3
4

auto sum = flux::ints() // [0, 1, 2, 3, ...]
    .take(10)           // [0, 1, 2, 3, ..., 10]
    .filter(is_even)    // [0, 2, 4, 6, 8, 10]
    .sum();             // 30

Flux is also an open source project, and I thought it would a great library to make a contribution to. I saw on GitHub that there was a request for a permutations adaptor I thought this would be something that I could handle, so I commented on the GitHub issue that I would try to implement it. After a busy Christmas season I was able to get a working implementation. These four articles detail how I implemented the adaptor.

The Idea

A permutations adapator (or iterator, or function, etc.) is a common tool in other iteration libraries. The adaptor takes in an input sequence, and returns a sequence made up of sequences that are a permutation of the previous sequence. A basic example would be as follows (in Python).

1
2
3
4
5
6
7
8
9

import itertools as it 

for permutation in it.permutations([1, 2]):
    print(permutation)

""" Output:
(1, 2)
(2, 1)
"""

The goal would be to add an adaptor to Flux such that operations like the previous example would be possible.

1
2
3

flux::ints()         // [1, 2, 3, ...]
    .take(2)         // [1, 2]
    .permutations(); // [[1, 2], [2, 1]]

Defining a Permutation

Before doing some implementation, let’s spend a few minutes trying to understand what a permutation actually is, and how the word is used in mathematics and programming. The Wikipedia page for permutation is displayed from a mathematics perspective, and states as follows.

Permutation (Wikipedia)
In mathematics, a permutation of a set can mean one of two different things: an arrangement of its members in a sequence or linear order, or the act or process of changing the linear order of an ordered set. (Wikipedia/Permutation)

Our adaptor will fulfil both definitions. We want the adaptor to (1) produce every permutation of the input sequence and (2) perform the process of generating new permutations from the sequence. Based on this we’ll make some definitions for our adaptor.

Input Sequence
The original sequence to perform the permutations on. This must be a flux::bounded_sequence, because there have to be a finite number of elements to permute.
Output Sequence
A sequence of sub-sequences where the sub-sequences are all of the permutations of the input sequence. The order of the sub-sequence is in lexicographical order.
Sub-Sequence
A sequence of length r that contains a permutation of the input sequence.

The Simplest Permutations Adaptor

While the Python itertools and Rust itertools iterators allow the user to specify the length of each sub-sequence, the simplest permutations adaptor will always output sub-sequences the length of the original sequence.

Flux allows for C++ coroutines to be used to specify simple adaptors, which is great for quickly developing a new adaptor. For a introduction to coroutines I would recommend Joel Schumacher’s Yet Another C++ Coroutine Tutorial or David Mazieres’ My tutorial and take on C++20 Coroutines. The basics for using a coroutine to create a Flux adaptor are as follows:

1
2
3
4
5
6
7
8
9
10
11
12

// Construction
auto adaptor_name = []<flux::sequence Seq>(Seq seq)
    -> flux::generator<flux::element_t<Seq>>
{
    // Implementation
};

// Usage
flux::ints()
    .take(2)
    ._(adaptor_name)
    . //...

The flux::generator type implements the flux::sequence functionality we need, and the _ function applies the adaptor to the input sequence.

Now to create the permutations adaptor we’ll consider what steps we need to take. First, we’ll need to cache the input sequence. We do this because each output-subsequence will be composed of the input values and the input sequence may be a single pass input so that if we don’t cache it we’ll only be able to produce the first output.

1
2
3
4
5
6

auto permutations_adaptor = []<flux::sequence Seq>(Seq seq)
    -> flux::generator</* subsequence type */>
{
    std::vector<flux::value_t<Seq>> cache;
    for (auto &&elem : seq) { cache.emplace_back(elem); }
};

Now we need to consider what the subsequence type should be. Since we want our output to be a sequence of subsequences, and we already have our input values cached in a std::vector we might as well just have the subsequence type be a std::vector as well. There are other types we could use in order to limit extraneous memory allocation, but we’ll talk about that another day.

1
2
3

auto permutations_adaptor = []<flux::sequence Seq>(Seq seq)
    -> flux::generator<std::vector<flux::value_t<Seq>>>
// ...

Producing the First Sub-Sequence

The first permutation in the sequence is the easiest, as it’s just the exact same as the input sequence. To return the first sequence, we’ll use co_yield to return the first element.

1
2
3
4
5
6
7
8

auto permutations_adaptor = []<flux::sequence Seq>(Seq seq)
    -> flux::generator<std::vector<flux::value_t<Seq>>>
{
    std::vector<flux::value_t<Seq>> cache;
    for (auto &&elem : seq) { cache.emplace_back(elem); }

    co_yield cache; // first subsequence
};

Producing Following Sub-Sequences

To get later sequences we can use the std::next_permutation to produce the permutations. According to the documentation the function permutes the input sequence to the next permutation, and returns true if there is another permutation possible, or false if all permutations have been exhausted. We can use the return value of std::next_permutation to determine if we should continue producing elements and permute the elements in one step.

1
2
3
4
5
6
7
8
9
10

auto permutations_adaptor = /* function signature */
{
    /* cache input */

    co_yield cache; // first subsequence

    while (std::next_permutation(cache.begin(), cache.end())) {
        co_yield cache; // following subsequences
    }
};

If we do a simple test with this adaptor and compare it with the Rust and Python implementations, we see that for simple input sequences we get the correct result! (See the examples on compiler explorer)

Language Output
C++ [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0],
[2, 0, 1], [2, 1, 0]]
Python [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0),
(2, 0, 1), (2, 1, 0)]
Rust [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0],
[2, 0, 1], [2, 1, 0]]

The number of possible permutations can be caculated using the following formula:

\[P(n,r) = \frac{n!}{(n - r)!}\]

If we calculate that for an input of size three (e.g. size of [0, 1, 2]) and a sub-sequence size of three as well, we calculate that the number of permutations should be six.

\[P(3,3) = \frac{3!}{0!} = 6\]

This just verifies the output is the correct length.

Let’s add another test though really quick, we’ll do the input sequence [2,1,0].

Language Output
C++ [[2, 1, 0]]
Python [(2, 1, 0), (2, 0, 1), (1, 2, 0), (1, 0, 2)
(0, 2, 1), (0, 1, 2)]
Rust [[2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 0, 2]
[0, 2, 1], [0, 1, 2]]

Well, that’s clearly not correct. If we step through the code using lldb (or any other debugger) the issue becomes apparent: std::next_permutation returns false on the first call to it, so the adaptor only returns the very first sub-sequence in the result, which is not what we expected. Let’s return back to the documentation.

Permutes the range [first, last) into the next permutation. Returns true if such a “next permutation” exists; otherwise transforms the range into the lexicographically first permutation (as if by std::sort) and returns false.
cppreference/next_permutation

This function does the permutation in-place on the input sequence, using the ordering of the values of the sequence itself. Since the input sequence is sorted in reverse order ([2, 1, 0]) then the next lexicographical permutation of the sequence should be [0, 1, 2] (the sequence in sorted order). Clearly, we can see that the Python and Rust sequences don’t return this as the next value. The second value of both of other implementations is [2, 0, 1], which isn’t the next lexicographical permutation of the input sequence. So what is going on here?

I pulled up the source for both the Python and the Rust implementations, and I found that both implementations don’t actually permute the input based off the input values, but rather they permute the input based off the indices of the input. Here’s an example:

1
2
3
4
5
6
7
8
9

Input:
  [2, 1, 0]

Permutations based off value:
  [[2, 0, 1], [0, 1, 2], [0, 2, 1], [1, 0, 2], ...]

Permutations based off index:
  Values:  [[2, 1, 0], [2, 0, 1], [1, 2, 0], ...]
  Indices: [[0, 1, 2], [0, 2, 1], [1, 0, 2], ...]

Based on this information, we can change our adaptor in a few ways. First, we need to keep track of all of the permuted indices of the input sequence. Secondly, we need a way to reindex the cached input sequence by the permuted indices. Let’s write the reindex function first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

using std::vector;

template<typename T>
auto reindex_sequence(const vector<T> &input,
                      const vector<size_t> &indices
                      ) -> vector<T>
{
    vector<T> output;

    for (const auto &index : indices) {
        output.push_back(input[index]);
    }

    return output;
}

Great! Now that we have a function that can take in the vectors of indices and inputs and return a vector with the input values ordered by the indices vector. Let’s add indices into our adaptor now.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

auto permutations_adaptor = []<flux::sequence Seq>(Seq seq)
    -> flux::generator<std::vector<flux::value_t<Seq>>>
{
    std::vector<flux::value_t<Seq>> cache;
    for (auto &&elem : seq) { cache.emplace_back(elem); }

    std::vector<size_t> indices(cache.size());
    std::iota(indices.begin(), indices.end(), 0);

    co_yield cache; // first subsequence

    while (std::next_permutation(indices.begin(), indices.end())) {
        // following subsequences
        co_yield reindex_sequence(cache, indices); 
    }
};

Great! Our output now matches our reference implementations in Python and Rust.

Language Output
C++ [[2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 0, 2]
[0, 2, 1], [0, 1, 2]]
Python [(2, 1, 0), (2, 0, 1), (1, 2, 0), (1, 0, 2)
(0, 2, 1), (0, 1, 2)]
Rust [[2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 0, 2]
[0, 2, 1], [0, 1, 2]]

With that complete, our simple permutations adaptor is now complete! To follow the process of adding this adaptor into the official Flux library read the follow up articles to this one.

Thanks for reading!

Complete Adaptor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// Made with Flux 0.4.0 and C++20

#include <algorithm>
#include <iostream>
#include <numeric>

#include <flux.hpp>

// Return a vector containing a permutation of the 
// input values in the order of the indices given in 
// the indices vector
template<typename T>
auto reindex_sequence(const std::vector<T> &input,
                      const std::vector<size_t> &indices
                      ) -> std::vector<T>
{
    std::vector<T> output;

    for (const auto &index : indices) {
        output.push_back(input[index]);
    }

    return output;
}

// Generates all permutations of a given input sequence
auto permutations_adaptor = []<flux::sequence Seq>(Seq seq)
    -> flux::generator<std::vector<flux::value_t<Seq>>>
{
    // cache the input
    std::vector<flux::value_t<Seq>> cache;
    for (auto &&elem : seq) { cache.emplace_back(elem); }

    // generate the indices vector from [0, n) where 
    // n is the size of the input sequence 
    std::vector<size_t> indices(cache.size());
    std::iota(indices.begin(), indices.end(), 0);

    co_yield cache; // first subsequence

    // permute the indices, and return the input reindexed by 
    // the indices
    while (std::next_permutation(indices.begin(), indices.end())) {
        // following subsequences
        co_yield reindex_sequence<flux::value_t<Seq>>(cache, indices); 
    }
};