Core/Utilities/CombinatoricSelectionTests.cpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #include <boost/test/unit_test.hpp>
0010
0011 #include "Acts/Utilities/detail/CombinatoricIndices.hpp"
0012
0013 #include <ranges>
0014 #include <set>
0015
0016 using namespace Acts::detail;
0017 using namespace Acts;
0018
0019 struct ArraySorter {
0020   template <std::size_t K>
0021   bool operator()(const std::array<std::size_t, K>& a,
0022                   const std::array<std::size_t, K>& b) const {
0023     for (std::size_t i = 0; i < K; ++i) {
0024       if (a[i] != b[i]) {
0025         return a[i] < b[i];
0026       }
0027     }
0028     return false;
0029   }
0030 };
0031
0032 template <std::size_t K>
0033 std::ostream& operator<<(std::ostream& ostr,
0034                          const std::array<std::size_t, K>& x) {
0035   ostr << "[";
0036   for (std::size_t i = 0ul; i < x.size(); ++i) {
0037     ostr << x[i];
0038     if (i + 1ul != x.size()) {
0039       ostr << ", ";
0040     }
0041   }
0042   ostr << "]";
0043   return ostr;
0044 }
0045
0046 template <std::size_t K>
0047 using CombinationSet = std::set<std::array<std::size_t, K>, ArraySorter>;
0048
0049 BOOST_AUTO_TEST_SUITE(UtilitiesCloneablePtr)
0050
0051 template <std::size_t K>
0052 bool goodArray(const std::array<std::size_t, K>& array, const std::size_t N) {
0053   bool good{true};
0054   for (std::size_t k = 0; k < array.size(); ++k) {
0055     BOOST_CHECK_LT(array[k], N);
0056     good &= (array[k] < N);
0057   }
0058   for (std::size_t j = 1; j < array.size(); ++j) {
0059     for (std::size_t i = 0; i < j; ++i) {
0060       BOOST_CHECK_NE(array[j], array[i]);
0061       good &= (array[i] != array[j]);
0062     }
0063   }
0064   return good;
0065 }
0066
0067 template <std::size_t K>
0068 void checkComboDrawing(const std::size_t N) {
0069   if (N < K) {
0070     if constexpr (K > 1) {
0071       checkComboDrawing<K - 1>(N);
0072     }
0073     return;
0074   }
0075   const CombinatoricIndices<K> indexGenerator{N};
0076   BOOST_CHECK_EQUAL(indexGenerator.size(), binomial(N, K));
0077   BOOST_CHECK_EQUAL(indexGenerator.intervalSize(), N);
0078
0079   CombinationSet<K> cachedCombos{};
0080
0081   for (std::size_t combo = 0ul; combo < indexGenerator.size(); ++combo) {
0082     std::array<std::size_t, K> combination = indexGenerator.draw(combo);
0083     std::cout << "N=" << N << ", K=" << K << " --- Iteration: " << (combo)
0084               << "-> drawn indices: " << combination << std::endl;
0085     BOOST_CHECK_EQUAL(goodArray(combination, N), true);
0086     /// Check that all indices are sorted
0087     for (std::size_t i = 1ul; i < combination.size(); ++i) {
0088       for (std::size_t k = 0ul; k < i; ++k) {
0089         BOOST_CHECK_LT(combination[k], combination[i]);
0090       }
0091     }
0092     BOOST_CHECK_EQUAL(cachedCombos.insert(combination).second, true);
0093   }
0094   BOOST_CHECK_EQUAL(cachedCombos.size(), indexGenerator.size());
0095
0096   if constexpr (K > 1) {
0097     checkComboDrawing<K - 1>(N);
0098   }
0099 }
0100
0101 BOOST_AUTO_TEST_CASE(CombinationDraw) {
0102   checkComboDrawing<11ul>(11ul);
0103   checkComboDrawing<10ul>(10ul);
0104 }
0105
0106 template <std::size_t K>
0107 void checkCombinatoricIterator(const std::size_t N) {
0108   if (N < K) {
0109     return;
0110   }
0111   CombinatoricIndices<K> indexGenerator{N};
0112   BOOST_CHECK_EQUAL(indexGenerator.size(), binomial(N, K));
0113   BOOST_CHECK_EQUAL(indexGenerator.intervalSize(), N);
0114
0115   auto begin = indexGenerator.begin();
0116   auto end = indexGenerator.end();
0117   BOOST_CHECK_EQUAL(begin != end, true);
0118   BOOST_CHECK_EQUAL((begin + indexGenerator.size()) == end, true);
0119
0120   CombinationSet<K> cachedCombos{};
0121   for (const auto& combination : indexGenerator) {
0122     BOOST_CHECK_EQUAL(goodArray(combination, N), true);
0123     BOOST_CHECK_EQUAL(cachedCombos.insert(combination).second, true);
0124   }
0125   if constexpr (K > 1) {
0126     checkCombinatoricIterator<K - 1>(N);
0127   }
0128 }
0129
0130 BOOST_AUTO_TEST_CASE(CombinatoricIterator) {
0131   checkCombinatoricIterator<7>(16);
0132 }
0133
0134 template <std::size_t K>
0135 void checkCombinatoricRemapping(const std::size_t N,
0136                                 const std::array<bool, K>& applyRemap) {
0137   if (N < K) {
0138     return;
0139   }
0140   CombinatoricIndices<K> indexGenerator{N};
0141   CombinationSet<K> cachedCombos{}, allCombos{};
0142   BOOST_CHECK_EQUAL(indexGenerator.size(), binomial(N, K));
0143   BOOST_CHECK_EQUAL(indexGenerator.intervalSize(), N);
0144
0145   for (std::size_t combo = 0; combo < indexGenerator.size(); ++combo) {
0146     const auto indices = indexGenerator.draw(combo);
0147     BOOST_CHECK_EQUAL(allCombos.insert(indices).second, true);
0148     std::array<std::size_t, K> remappedIndices{};
0149     for (std::size_t i = 0; i < K; ++i) {
0150       if (applyRemap[i]) {
0151         remappedIndices[i] = N - indices[i] + indices[1];
0152       } else {
0153         remappedIndices[i] = indices[i];
0154       }
0155     }
0156     std::cout << "RemapIndices - Iteration: " << (combo + 1)
0157               << " -> drawn: " << indices
0158               << " --> remapped: " << remappedIndices << std::endl;
0159     BOOST_CHECK_EQUAL(goodArray(remappedIndices, N), true);
0160     std::ranges::sort(remappedIndices);
0161     BOOST_CHECK_EQUAL(cachedCombos.insert(remappedIndices).second, true);
0162   }
0163   BOOST_CHECK_EQUAL(allCombos.size(), cachedCombos.size());
0164 }
0165
0166 BOOST_AUTO_TEST_CASE(RemapIndices4) {
0167   constexpr std::size_t N = 16;
0168   for (std::size_t i = 4; i <= N; ++i) {
0169     checkCombinatoricRemapping<4>(i, {false, false, true, true});
0170   }
0171 }
0172 BOOST_AUTO_TEST_CASE(RemapIndices3) {
0173   constexpr std::size_t N = 16;
0174   for (std::size_t i = 3; i <= N; ++i) {
0175     checkCombinatoricRemapping<3>(i, {false, false, true});
0176   }
0177 }
0178
0179 BOOST_AUTO_TEST_SUITE_END()