'generating all permuated products from a map is not working
My code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> generate_all(map<ll, int> mp, int keys_done, ll prod) {
if (keys_done == mp.size()) {
vector<ll> v;
v.push_back(prod);
return v;
}
vector<ll> vr;
int ctr = 0;
for (auto it = mp.begin(); it != mp.end(); ++it, ctr++) {
if (ctr < keys_done or ctr > keys_done)
continue;
ll next_prod = 1;
for (int j = 1; j <= it->second; j++) {
next_prod *= it->first;
vector<ll> v1 = generate_all(mp, 1 + keys_done, prod * next_prod);
for (int k = 0; k < v1.size(); k++) {
vr.push_back(v1[k]);
}
}
}
return vr;
}
int main() {
map<ll, int> mp = {{2,4},{3,1}, {5,3}};
vector<ll> v_final=generate_all(mp,0,1);
for (const auto & val:v_final) {
cout << val << endl;
}
}
current output:
2
Expected output
2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 25, 30, 40, 48, 50, 60, 75, 80, 100, 120, 125, 150, 200, 240, 250, 300, 375, 400, 500, 600, 750, 1000, 1200, 1500, 2000, 3000, 6000
To illustrate the output it is the following:
2^1,2^2, 2^3, 2^4, 3^1, 5^1, 5^2, 5^3,
2^1 * 3, 2^2 * 3, 2^3 * 3, 2^4 * 3, 5^1 * 3, 5^2 * 3, 5^3 * 3,
2^1 * 5, 2^2 * 5, 2^3 * 5, 2^4 * 5,
2^1 * 5^2, 2^2 * 5^2, 2^3 * 5^2, 2^4 * 5^2, 3^1 * 5^2,
2^1 * 5^3, 2^2 * 5^3, 2^3 * 5^3, 2^4 * 5^3, 3^1 * 5^3,
2^1 * 3^1 * 5^1, 2^1 * 3^1 * 5^2, 2^1 * 3^1 * 5^3,
2^2 * 3^1 * 5^1, 2^2 * 3^1 * 5^2, 2^2 * 3^1 * 5^3,
2^3 * 3^1 * 5^1, 2^3 * 3^1 * 5^2, 2^3 * 3^1 * 5^3,
2^4 * 3^1 * 5^1, 2^4 * 3^1 * 5^2, 2^4 * 3^1 * 5^3,
Here 2 can have 0 to 4 th power multiplied by 3 from 0 to 4 th power and so on.
If the choices were limited to 3 like this example. this is how my code would have looked:
vector<ll>v;
for(int i=0;i<=4;i++)
for(int j=0;j<=1;j++)
for(int k=0;k<=3;k++)
v.insert(pow(2,i)*pow(3,j)*pow(5,k));
return v;
But I need to solve for k such keys not just 3 keys.
If possible do also suggest a non-recusrvice method.
Solution 1:[1]
We have to implement 2 major mathematical concepts here
- Create a power set
- Building the cartesian product over several sets (or the comnination of all elements over several sets)
The task contains some additional indirections to add a little bit complexity.
Let's start with the power set.
We will first make a simplification for an easier understanding of the task. We will name the input pairs, consisting of a base value and an exponent, as set elements a,b,c and so on. If we assume an input of { {2,4},{3,1}, {5,3}, {4,2} }, then we will name this now as a set with 4 elements {a,b,c,d}.
What we need to generate is a power set from this. There are 2 main standard approaches.
- Counting with checking of set bits via it mask
- Setting more and more bits in a field and do permutations.
Let us look at solution 1. Counting. Based on "abcd" we will get
Count Binary Selection (sub set)
DCBA Cardinality
0 0000 {----} 0 Empty set
1 0001 {---A} 1
2 0010 {--B-} 1
3 0011 {--BA} 2
4 0100 {-C--} 1
5 0101 {-C-A} 2
6 0110 {-CB-} 2
7 0111 {-CBA} 3
8 1000 {D---} 4
9 1001 {D--A} 2
10 1010 {D-B-} 2
11 1011 {D-BA} 3
12 1100 {DC--} 3
13 1101 {DC-A} 3
14 1110 {DCB-} 3
15 1111 {DCBA} 4
As a result we will get the powerset:
{{A},{B},{AB},{C},{AC},{BC},{ABC},{D},{AD},{BD},{ABD},{CD},{ACD},{BCD},{ABCD}}
If you look at the output, we see that the elements are not sorted according to their cardinality. Therefore we will choose a different approach. We will set more and more bits in a field an do permutations on them. Also with a selector. Then, we will get something like this:
Binary Selection
0000 {----} Empty set. Ignored
0001 {---A} Set bit 0
0010 {--B-} Permutation
0101 {-C--} Permutation
1000 {D---} Permutation
0011 {--BA} Set next bit number 1
0101 {-C-A} Permutation
1001 {D--A} Permutation
0110 {-CB-} Permutation
1010 {D-B-} Permutation
1100 {D--A} Permutation
0111 {-CBA} Set next bit number 2
1011 {D-BA} Permutation
1101 {DC-A} Permutation
1110 {DCB-} Permutation
1111 {DCBA} Set next bit number 3
As a result we will get the "more reasonable/expected" powerset:
{{A},{B},{C},{D},{AB},{AC},{AD},{BC},{BD},{AD},{ABC},{ABD},{ACD},{BCD},{ABCD}}
By the way. The overall number of sub sets is of course 2^n and the size of the cardinality group is equal to the corresponding binomial coeeficient.
Cardinality
0 4 choose 0 --> 1
1 4 choose 1 --> 4
2 4 choose 1 --> 6
3 4 choose 1 --> 4
4 4 choose 1 --> 1
Sum: 16
The corresponding algorithm is easy to implement, which can also be seen later in the code example.
Next. If we have the powerset, then we need to combine all elements. Let us take as an example the sub set {ABC}. We can translate this back to the original input data:
{2,4},{3,1},{5,3}
which would expand with the given rule to
{2,4,8,16},{3},{5,25,125}
And now we need to build all combinations of that. The number of combinations is of cause the product of the cardinality of the sub sets. Here 4*1*3 = 12. To illustrate that and get a first idea of the solution approach, we list up all combinations.
2 3 5
4 3 5
8 3 5
16 3 5
2 3 25
4 3 25
8 3 25
16 3 25
2 3 125
4 3 125
8 3 125
16 3 125
We could imagine that we have an odometer with 3 disks. Diks 1 contains 2,4,8,13, disk 2 contins 3 and disk 3 contains 5,25,125.
Everytime, when a disks rolls over than the next disk will be triggered as well. So, if the first diks is at 16 and rolls over to 2 then diks 3 is triggered. Because disk 3 contains only 1 number (the 3), it will also immediately roll over and trigger disk 3. This will then show the next value. And so on and so on.
So, we also do some sort of counting, but the counters have a different base number. Anyway. All this is easy to implement.
As an additional implementation detail, I will not use the "pow" function. I will just multiple the counter, the value on the disk, with its base value. This will save space and time. And all of this put together could be implemented like the following:
(Please note. I use "easy code". We could use many more advanced algorithms, but for the sake of readability, I go this way. As said. Many other solutions possible)
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using MyType = unsigned long long;
// The base-number and the max exponent are the elements of a set
struct Element {
MyType base{};
MyType maxExponent{};
// Actually, this elements does not store one value only, but "maxExponent" elements
// Do get all of those, we use the well known odometer approach
// We can always calculate the next value in the list and inform, if we have a rollover
// In case of a roll over, we can inform other sets about this and the other set can also count up
MyType currentResult{ base };
MyType currentExponent{};
// Calculate next value. So, will for {2,4} get 2, 4, 8, 16
bool next(bool overflowFromPrevious) {
// Indicates that we will wrap around from previous
bool overflow{};
// If a previous odometer roll has overflowed
if (overflowFromPrevious) {
// Check, if we are NOT at the end. This will happen, if ther is only 1 as the max exponent.
if (currentExponent < maxExponent) {
// Get next exponent
++currentExponent;
// And calculate current data. We could also store those values,
// but we do not want to waste space
currentResult *= base;
// Now check again for overflow (after we incremented the exponent)
if (currentExponent >= maxExponent) {
// If overlow, then reset exponent counter and base
currentExponent = 0;
currentResult = base;
overflow = true;
}
}
else overflow = true;
}
return overflow;
}
// Simple inserter operator override, to be able to do an easier output
friend std::ostream& operator << (std::ostream& os, const Element& e) {
return os << '{' << e.base << ',' << e.maxExponent << '}';
}
};
// We will use a vetcor and not a set, because we need random access via the index operator
using MSet = std::vector<Element>;
void getProducts(MSet& mset) {
// Selectors for creating the subsets of the power set
std::vector<bool> selector(mset.size());
// For all number of elements in the original set
for (size_t k{}; k < mset.size(); ++k) {
// Set selecot bits. In each loop one more bit. So, 1 then 11, then 111 and so on
selector[k] = true;
// Do all permutations of the above set bits
do {
// For debug output
for (bool b : selector) std::cout << b * 1; std::cout << " ";
std::ostringstream oss{};
// Here we will store all elements of a resulting subset
MSet subSet{};
// Check if the selector bit is set, and if so, then add to subset
for (size_t n{}; n < mset.size(); ++n) {
if (selector[n]) {
subSet.push_back(mset[n]);
oss << mset[n]; // For debug output
}
}
// Debug output of powerset with number of subsets
std::cout << "Powerset("<< subSet.size()<< "): " << std::left << std::setw(22) << oss.str() << ' ';
// Now, we want to calculate all combinations of subsets, using the odometer approach
// Here we will store the overall number of combinations. It is the product of all max exponents
MyType combinations{ 1 };
for (const Element& element : subSet)
combinations *= element.maxExponent;
// Now get the product for all combinations over all subsets
for (MyType i{}; i < combinations; ++i) {
// Get the product for one combination
MyType product{ 1 };
for (Element& element : subSet)
product *= element.currentResult;
std::cout << product << ' '; // For debug output
// And, using the odometer approach, create the next combination
bool overflow{true};
for (Element& element : subSet)
overflow = element.next(overflow);
}
std::cout << '\n'; // For debug output
} while (std::prev_permutation(selector.begin(), selector.end()));
}
}
// Test / driver code
int main() {
MSet mset{ {2,4},{3,1}, {5,3}, {4,2} };
getProducts (mset);
}
I added a lot of debug output. You may delete that.
With that the solution the result will be:
By the way. I think that your expected output is wrong . . .
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Armin Montigny |