1 /*! 2 @file 3 Defines `boost::hana::permutations`. 4 5 @copyright Louis Dionne 2013-2017 6 Distributed under the Boost Software License, Version 1.0. 7 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) 8 */ 9 10 #ifndef BOOST_HANA_PERMUTATIONS_HPP 11 #define BOOST_HANA_PERMUTATIONS_HPP 12 13 #include <boost/hana/fwd/permutations.hpp> 14 15 #include <boost/hana/at.hpp> 16 #include <boost/hana/concept/sequence.hpp> 17 #include <boost/hana/config.hpp> 18 #include <boost/hana/core/dispatch.hpp> 19 #include <boost/hana/core/make.hpp> 20 #include <boost/hana/detail/array.hpp> 21 #include <boost/hana/length.hpp> 22 23 #include <cstddef> 24 #include <utility> 25 26 27 BOOST_HANA_NAMESPACE_BEGIN 28 //! @cond 29 template <typename Xs> operator ()(Xs && xs) const30 constexpr auto permutations_t::operator()(Xs&& xs) const { 31 using S = typename hana::tag_of<Xs>::type; 32 using Permutations = BOOST_HANA_DISPATCH_IF(permutations_impl<S>, 33 hana::Sequence<S>::value 34 ); 35 36 #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS 37 static_assert(hana::Sequence<S>::value, 38 "hana::permutations(xs) requires 'xs' to be a Sequence"); 39 #endif 40 41 return Permutations::apply(static_cast<Xs&&>(xs)); 42 } 43 //! @endcond 44 45 namespace detail { 46 template <std::size_t N> 47 struct permutation_indices { 48 static constexpr auto value = 49 detail::array<std::size_t, N>{}.iota(0).permutations(); 50 }; 51 } 52 53 template <typename S, bool condition> 54 struct permutations_impl<S, when<condition>> : default_ { 55 template <std::size_t n, typename Xs, std::size_t ...i> 56 static constexpr auto nth_permutationpermutations_impl57 nth_permutation(Xs const& xs, std::index_sequence<i...>) { 58 constexpr auto indices = detail::permutation_indices<sizeof...(i)>::value; 59 (void)indices; // workaround GCC warning when sizeof...(i) == 0 60 return hana::make<S>(hana::at_c<indices[n][i]>(xs)...); 61 } 62 63 template <std::size_t N, typename Xs, std::size_t ...n> 64 static constexpr auto permutations_helperpermutations_impl65 permutations_helper(Xs const& xs, std::index_sequence<n...>) { 66 return hana::make<S>(nth_permutation<n>(xs, std::make_index_sequence<N>{})...); 67 } 68 69 template <typename Xs> applypermutations_impl70 static constexpr auto apply(Xs const& xs) { 71 constexpr std::size_t N = decltype(hana::length(xs))::value; 72 constexpr std::size_t total_perms = detail::factorial(N); 73 return permutations_helper<N>(xs, std::make_index_sequence<total_perms>{}); 74 } 75 }; 76 BOOST_HANA_NAMESPACE_END 77 78 #endif // !BOOST_HANA_PERMUTATIONS_HPP 79