| 1 | /*
|
| 2 | * Souffle - A Datalog Compiler
|
| 3 | * Copyright (c) 2022, The Souffle Developers. All rights reserved
|
| 4 | * Licensed under the Universal Permissive License v 1.0 as shown at:
|
| 5 | * - https://opensource.org/licenses/UPL
|
| 6 | * - <souffle root>/licenses/SOUFFLE-UPL.txt
|
| 7 | */
|
| 8 |
|
| 9 | /************************************************************************
|
| 10 | *
|
| 11 | * @file SubsetCache.h
|
| 12 | *
|
| 13 | * Data structure for efficiently generating subsets without recomputation
|
| 14 | *
|
| 15 | ***********************************************************************/
|
| 16 |
|
| 17 | #pragma once
|
| 18 |
|
| 19 | namespace souffle {
|
| 20 |
|
| 21 | class SubsetCache {
|
| 22 | public:
|
| 23 | using PowerSet = std::set<std::vector<std::size_t>>;
|
| 24 |
|
| 25 | const PowerSet& getSubsets(std::size_t N, std::size_t K) const {
|
| 26 | if (cache.count({N, K})) {
|
| 27 | return cache.at({N, K});
|
| 28 | }
|
| 29 |
|
| 30 | PowerSet res;
|
| 31 |
|
| 32 | // generate the next permutation of the bitmask
|
| 33 | std::vector<std::size_t> cur;
|
| 34 | cur.reserve(K);
|
| 35 |
|
| 36 | // use bitmask for subset generation
|
| 37 | std::string bitmask(K, 1); // K leading 1's
|
| 38 | bitmask.resize(N, 0); // N-K trailing 0's
|
| 39 |
|
| 40 | // generate the combination while there are combinations to go
|
| 41 | do {
|
| 42 | cur.clear();
|
| 43 |
|
| 44 | // construct the subset using the set bits in the bitmask
|
| 45 | for (std::size_t i = 0; i < N; ++i) // [0..N-1] integers
|
| 46 | {
|
| 47 | if (bitmask[i]) {
|
| 48 | cur.push_back(i);
|
| 49 | }
|
| 50 | }
|
| 51 | res.insert(cur);
|
| 52 | } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
|
| 53 | cache[std::make_pair(N, K)] = res;
|
| 54 | return cache.at({N, K});
|
| 55 | }
|
| 56 |
|
| 57 | private:
|
| 58 | mutable std::map<std::pair<std::size_t, std::size_t>, PowerSet> cache;
|
| 59 | };
|
| 60 |
|
| 61 | } // namespace souffle
|