// Output all 3-digit numbers with unique digits in sorted order.
// (Yes, there is an easier way to do this)
 
#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
 
template<typename T>
struct Permutation {
    template<typename InputIt>
    Permutation(InputIt, InputIt, int k);
    bool next();
    std::vector<T> get() const;
 
private:
    std::vector<T> m_pool;
    std::vector<int> m_index;
    std::vector<int> m_cycle;
    int m_k;
};
 
template<typename T>
template<typename InputIt>
Permutation<T>::Permutation(InputIt first, InputIt last, int k)
: m_pool(first, last), m_k(k)
{
    int n = m_pool.size();
    if (k > n)
        throw std::runtime_error("k cannot be greater than input size");
    for (int i = 0; i < n; i++)
        m_index.push_back(i);
    for (int i = n; i > n-k; i--)
        m_cycle.push_back(i);
}
 
template<typename T>
bool Permutation<T>::next()
{
    int n = m_pool.size();
    for (int i = m_k-1; i >= 0; i--)
    {
        if (--m_cycle[i])
        {
            std::swap(m_index[i], m_index[n - m_cycle[i]]);
            return true;
        }
        m_cycle[i] = n - i;
        auto first = m_index.begin();
        std::rotate(std::next(first, i), std::next(first, i+1), m_index.end());
    }
    return false;
}
 
template<typename T>
std::vector<T> Permutation<T>::get() const
{
    std::vector<T> out;
    for (int i = 0; i < m_k; i++)
        out.push_back(m_pool[m_index[i]]);
    return out;
}
 
template<typename InputIt>
auto make_permutation(InputIt first, InputIt last, int k)
{
    return Permutation<typename std::iterator_traits<InputIt>::value_type>(first, last, k);
}
 
//
// Main.
//
 
template<typename InputIt>
int digitsToInt(InputIt first, InputIt last)
{
    return std::accumulate(first, last, 0, [](int x, int y) { return 10*x + y; });
}
 
int main()
{
    int n = 10;
    int k = 3;
 
    std::vector<int> digits(n);
    auto first = digits.begin(), last = digits.end();
    std::iota(first, last, 0);
    auto permutations = make_permutation(first, last, k);
 
    // Drop while first element is zero.
    while (permutations.get().at(0) == 0 && permutations.next())
        ;
    // Output numbers with unique digits in order.
    do
    {
        auto perm = permutations.get();
        std::cout << digitsToInt(begin(perm), end(perm)) << ' ';
    }
    while (permutations.next());
}

Ly8gT3V0cHV0IGFsbCAzLWRpZ2l0IG51bWJlcnMgd2l0aCB1bmlxdWUgZGlnaXRzIGluIHNvcnRlZCBvcmRlci4KLy8gKFllcywgdGhlcmUgaXMgYW4gZWFzaWVyIHdheSB0byBkbyB0aGlzKQoKI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCnRlbXBsYXRlPHR5cGVuYW1lIFQ+CnN0cnVjdCBQZXJtdXRhdGlvbiB7CiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBJbnB1dEl0PgogICAgUGVybXV0YXRpb24oSW5wdXRJdCwgSW5wdXRJdCwgaW50IGspOwogICAgYm9vbCBuZXh0KCk7CiAgICBzdGQ6OnZlY3RvcjxUPiBnZXQoKSBjb25zdDsKCnByaXZhdGU6CiAgICBzdGQ6OnZlY3RvcjxUPiBtX3Bvb2w7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IG1faW5kZXg7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IG1fY3ljbGU7CiAgICBpbnQgbV9rOwp9OwoKdGVtcGxhdGU8dHlwZW5hbWUgVD4KdGVtcGxhdGU8dHlwZW5hbWUgSW5wdXRJdD4KUGVybXV0YXRpb248VD46OlBlcm11dGF0aW9uKElucHV0SXQgZmlyc3QsIElucHV0SXQgbGFzdCwgaW50IGspCjogbV9wb29sKGZpcnN0LCBsYXN0KSwgbV9rKGspCnsKICAgIGludCBuID0gbV9wb29sLnNpemUoKTsKICAgIGlmIChrID4gbikKICAgICAgICB0aHJvdyBzdGQ6OnJ1bnRpbWVfZXJyb3IoImsgY2Fubm90IGJlIGdyZWF0ZXIgdGhhbiBpbnB1dCBzaXplIik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBtX2luZGV4LnB1c2hfYmFjayhpKTsKICAgIGZvciAoaW50IGkgPSBuOyBpID4gbi1rOyBpLS0pCiAgICAgICAgbV9jeWNsZS5wdXNoX2JhY2soaSk7Cn0KCnRlbXBsYXRlPHR5cGVuYW1lIFQ+CmJvb2wgUGVybXV0YXRpb248VD46Om5leHQoKQp7CiAgICBpbnQgbiA9IG1fcG9vbC5zaXplKCk7CiAgICBmb3IgKGludCBpID0gbV9rLTE7IGkgPj0gMDsgaS0tKQogICAgewogICAgICAgIGlmICgtLW1fY3ljbGVbaV0pCiAgICAgICAgewogICAgICAgICAgICBzdGQ6OnN3YXAobV9pbmRleFtpXSwgbV9pbmRleFtuIC0gbV9jeWNsZVtpXV0pOwogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICB9CiAgICAgICAgbV9jeWNsZVtpXSA9IG4gLSBpOwogICAgICAgIGF1dG8gZmlyc3QgPSBtX2luZGV4LmJlZ2luKCk7CiAgICAgICAgc3RkOjpyb3RhdGUoc3RkOjpuZXh0KGZpcnN0LCBpKSwgc3RkOjpuZXh0KGZpcnN0LCBpKzEpLCBtX2luZGV4LmVuZCgpKTsKICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKdGVtcGxhdGU8dHlwZW5hbWUgVD4Kc3RkOjp2ZWN0b3I8VD4gUGVybXV0YXRpb248VD46OmdldCgpIGNvbnN0CnsKICAgIHN0ZDo6dmVjdG9yPFQ+IG91dDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbV9rOyBpKyspCiAgICAgICAgb3V0LnB1c2hfYmFjayhtX3Bvb2xbbV9pbmRleFtpXV0pOwogICAgcmV0dXJuIG91dDsKfQoKdGVtcGxhdGU8dHlwZW5hbWUgSW5wdXRJdD4KYXV0byBtYWtlX3Blcm11dGF0aW9uKElucHV0SXQgZmlyc3QsIElucHV0SXQgbGFzdCwgaW50IGspCnsKICAgIHJldHVybiBQZXJtdXRhdGlvbjx0eXBlbmFtZSBzdGQ6Oml0ZXJhdG9yX3RyYWl0czxJbnB1dEl0Pjo6dmFsdWVfdHlwZT4oZmlyc3QsIGxhc3QsIGspOwp9CgovLwovLyBNYWluLgovLwoKdGVtcGxhdGU8dHlwZW5hbWUgSW5wdXRJdD4KaW50IGRpZ2l0c1RvSW50KElucHV0SXQgZmlyc3QsIElucHV0SXQgbGFzdCkKewogICAgcmV0dXJuIHN0ZDo6YWNjdW11bGF0ZShmaXJzdCwgbGFzdCwgMCwgW10oaW50IHgsIGludCB5KSB7IHJldHVybiAxMCp4ICsgeTsgfSk7Cn0KCmludCBtYWluKCkKewogICAgaW50IG4gPSAxMDsKICAgIGludCBrID0gMzsKCiAgICBzdGQ6OnZlY3RvcjxpbnQ+IGRpZ2l0cyhuKTsKICAgIGF1dG8gZmlyc3QgPSBkaWdpdHMuYmVnaW4oKSwgbGFzdCA9IGRpZ2l0cy5lbmQoKTsKICAgIHN0ZDo6aW90YShmaXJzdCwgbGFzdCwgMCk7CiAgICBhdXRvIHBlcm11dGF0aW9ucyA9IG1ha2VfcGVybXV0YXRpb24oZmlyc3QsIGxhc3QsIGspOwoKICAgIC8vIERyb3Agd2hpbGUgZmlyc3QgZWxlbWVudCBpcyB6ZXJvLgogICAgd2hpbGUgKHBlcm11dGF0aW9ucy5nZXQoKS5hdCgwKSA9PSAwICYmIHBlcm11dGF0aW9ucy5uZXh0KCkpCiAgICAgICAgOwogICAgLy8gT3V0cHV0IG51bWJlcnMgd2l0aCB1bmlxdWUgZGlnaXRzIGluIG9yZGVyLgogICAgZG8KICAgIHsKICAgICAgICBhdXRvIHBlcm0gPSBwZXJtdXRhdGlvbnMuZ2V0KCk7CiAgICAgICAgc3RkOjpjb3V0IDw8IGRpZ2l0c1RvSW50KGJlZ2luKHBlcm0pLCBlbmQocGVybSkpIDw8ICcgJzsKICAgIH0KICAgIHdoaWxlIChwZXJtdXRhdGlvbnMubmV4dCgpKTsKfQ==