Info

• Did you know about C++20 std::next_permutation algorithm?

  • https://eel.is/c++draft/alg.permutation.generators#lib:next_permutation

Example

[[nodiscard]] constexpr auto factorial(const auto n) {
    if (n == 0 or n == 1) {
        return 1;
    }
    auto result = 1;
    for (auto i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}
static_assert(1 == factorial(0));
static_assert(1 == factorial(1));
static_assert(1 * 2 == factorial(2));
static_assert(1 * 2 * 3 == factorial(3));
static_assert(1 * 2 * 3 * 4 == factorial(4));
static_assert(1 * 2 * 3 * 4 * 5 == factorial(5));
static_assert(1 * 2 * 3 * 4 * 5 * 6 == factorial(6));

https://godbolt.org/z/14r8EdevM

Puzzle

• Can you implement permute invoke which will try to call using all possible permutations?

// TODO invoke

template <auto>
struct Foo {};

constexpr auto foo() { return 1; }
constexpr auto bar(Foo<0>) { return 2; } constexpr auto baz(Foo<0>, Foo<1>) { return 3; }

static_assert(1 == invoke<int>(foo));
static_assert(2 == invoke<int>(bar, Foo<0>{}));
static_assert(3 == invoke<int>(baz, Foo<0>{}, Foo<1>{}));
static_assert(3 == invoke<int>(baz, Foo<1>{}, Foo<0>{}));

https://godbolt.org/z/xeaxP46qW

Solutions

template <class T, auto N>
[[nodiscard]] constexpr auto permute(std::array<T, N> nums) {
    std::array<std::array<T, N>, factorial(N)> result{};
    auto i = 0;
    do {
        result[i++] = nums;
    } while (std::next_permutation(nums.begin(), nums.end()));
    return result;
}

namespace detail {
template<class> constexpr auto invoke(auto fn, auto... ts) -> std::pair<bool, decltype(fn(ts...))> { return {true, fn(ts...)}; }
template<class R> constexpr auto invoke(...) -> std::pair<bool, R> { return {false, {}}; }

template<auto N> constexpr auto nth(auto... args) {
  return [&]<auto... Ns>(std::index_sequence<Ns...>) {
    return [](decltype((void*)Ns)..., auto* nth, auto*...) {
      return *nth;
    }(&args...);
  }
  (std::make_index_sequence<N>{});
}
} // namespace detail

template<class R>
constexpr auto invoke(auto fn, auto... ts) -> R {
    constexpr auto ids = []<auto... Ns>(std::index_sequence<Ns...>) { return std::array<std::size_t, sizeof...(Ns)>{Ns...}; }(std::make_index_sequence<sizeof...(ts)>{});
    constexpr auto permutations = permute(ids);

    R result;
    bool called{};
    [&]<auto... Ns>(std::index_sequence<Ns...>) {
        ([&]<auto N, auto... Is>(std::index_sequence<Is...>) {
            std::tie(called, result) = detail::invoke<R>(fn, detail::nth<permutations[N][Is]>(ts...)...);
            return called;
        }.template operator()<Ns>(std::make_index_sequence<permutations[Ns].size()>{}) or ...);
    }(std::make_index_sequence<permutations.size()>{});
    return result;
}

https://godbolt.org/z/vKbofePes

template <class T, auto N>
[[nodiscard]] constexpr auto permute(std::array<T, N> nums) {
    std::array<std::array<T, N>, factorial(N)> result{};
    auto i = 0;
    do {
        result[i++] = nums;
    } while (std::next_permutation(nums.begin(), nums.end()));
    return result;
}

namespace detail {
template<class, auto N> constexpr auto invoke(auto fn, auto... ts) -> std::pair<std::integral_constant<int, N>, decltype(fn(ts...))> { return {{}, fn(ts...)}; }
template<class R, auto> constexpr auto invoke(...) -> std::pair<std::integral_constant<int, 0>, R> { return {}; }

template<auto N> constexpr auto nth(auto... args) {
  return [&]<auto... Ns>(std::index_sequence<Ns...>) {
    return [](decltype((void*)Ns)..., auto* nth, auto*...) {
      return *nth;
    }(&args...);
  }
  (std::make_index_sequence<N>{});
}

template<class R, auto I, auto Size, auto Permutations, auto Split>
constexpr auto invoke_impl(auto fn, auto... ts) -> R {
    if constexpr (I >= Size) {
        return {};
    } else {
        constexpr auto N = [&]<auto... Ns>(std::index_sequence<Ns...>) {
            return ([&]<auto N, auto... Is>(std::index_sequence<Is...>) {
                return decltype(detail::invoke<R, N+1>(fn, detail::nth<Permutations[N][Is]>(ts...)...)){}.first.value;
            }.template operator()<I+Ns>(std::make_index_sequence<Permutations[I+Ns].size()>{}) + ...);
        }(std::make_index_sequence<Split>{});

        if constexpr (N > 0) {
            constexpr auto N_ = N - 1;
            return [&]<auto... Is>(std::index_sequence<Is...>) {
                return detail::invoke<R, N_>(fn, detail::nth<Permutations[N_][Is]>(ts...)...).second;
            }(std::make_index_sequence<Permutations[N_].size()>{});
        } else {
            constexpr auto chunks = Size / Split;
            return invoke_impl<R, I+chunks, chunks, Permutations>(fn, ts...);
        }
    }
}
} // namespace detail

template<class R>
constexpr auto invoke(auto fn, auto... ts) -> R {
    constexpr auto ids = []<auto... Ns>(std::index_sequence<Ns...>) { return std::array<std::size_t, sizeof...(Ns)>{Ns...}; }(std::make_index_sequence<sizeof...(ts)>{});
    constexpr auto permutations = permute(ids);
    constexpr auto max_params_without_chunking = 7;
    constexpr auto split = 10;

    if constexpr (sizeof...(ts) < max_params_without_chunking) {
        constexpr auto N = [&]<auto... Ns>(std::index_sequence<Ns...>) {
            return ([&]<auto N, auto... Is>(std::index_sequence<Is...>) {
                return decltype(detail::invoke<R, N+1>(fn, detail::nth<permutations[N][Is]>(ts...)...)){}.first.value;
            }.template operator()<Ns>(std::make_index_sequence<permutations[Ns].size()>{}) + ...);
        }(std::make_index_sequence<permutations.size()>{});

        if constexpr (N > 0) {
            constexpr auto N_ = N - 1;
            return [&]<auto... Is>(std::index_sequence<Is...>) {
                return detail::invoke<R, N_>(fn, detail::nth<permutations[N_][Is]>(ts...)...).second;
            }(std::make_index_sequence<permutations[N_].size()>{});
        } else {
            return {};
        }
    } else {
      return detail::invoke_impl<R, 0, permutations.size(), permutations, split>(fn, ts...);
    }
}

https://godbolt.org/z/97ejzW4Px