Test every combination of functions in every order
I have a bunch of functions a.process
, b.process
, c.process
..., name them a
, b
, c
..., that all take a std::string
as with the parameter and return a std::string
.
Given the starting std::string s
, I want to generate every possible conclusion combinations a
, b
, c
... called in any order, and given s
as an initial input.
For example, I want to calculate a(s)
, b(s)
, c(s)
, a(b(s))
, a(c(s))
, b(a(s))
, b(c(s))
, c(a(s))
, c(b(s))
, a(b(c(s)))
,, etc.
I think I could make a function to generate each permutation of the list, something like Python itertools.permutations
, but I have two main problems:
-
I don't just want every permutation, I want every permutation in every order.
-
And more importantly, I have no idea how to store functions in arrays, as it would be easy to do in Python.
Also, I need to get every possible conclusion includes a combination of features that generated it for the example above, I would have known that the outputs are in the following order: "a"
, "b"
, "c"
, "ab"
, "ac"
, "ba"
, "bc"
, "ca"
, "cb"
, "abc"
, etc.
How could I implement this in C ++?
source to share
To store functions in an array, you need to use function pointers . Something like that:
typedef string (*t_fnPtr)(string);
t_fnPtr fnPtrArray[10]; //Initialize this with your functions
Then it's just a matter of creating all combinations of your array and applying it to a string. Have a look at this question .
source to share
I am just debugging Sid's answer into valid code. Unlike Galik's answer , this does not lead to duplication
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using Fn = std::string (*)(std::string);
std::string apply_all(const std::vector<Fn>& fns, std::string s)
{
for(auto fn : fns)
s = fn(s);
return s;
}
int main()
{
std::string s = /* some string */;
std::vector<Fn> functions{/* initialize with functions */};
int n = functions.size();
for(int r = 1; r <= n; r++)
{
std::vector<bool> v(n);
std::fill(v.begin(), v.begin() + r, true); // select r functions
// permute through all possible selections of r functions
do {
std::vector<Fn> selected;
for(int i = 0; i < n; ++i)
if(v[i])
selected.push_back(functions[i]);
std::sort(selected.begin(), selected.end());
// permute through the r functions
do {
std::cout << apply_all(selected, s) << std::endl;
} while(std::next_permutation(selected.begin(), selected.end()));
} while(std::prev_permutation(v.begin(), v.end()));
}
}
source to share
Some ideas and pseudocode
An array of function pointers, one for each function.
typedef std::string (*Func)(std::string const&);
Func const func_array[] = {&a, &b, &c};
int const n = sizeof array / sizeof array[0]; // number of functions
We need
n choose 1 to get 1-element combinations a, b, c
n choose 2 to get 2-element combinations ab, ac, bc
n choose 3 to get 3-element combinations abc
Further, for each combination we need all possible permutations. I.e.
For all k = 1 to n,
All permutations of (All combinations of n-choose-k)
Sketch
for i = 0 to 2^(n-1):
xi = elements of func_array corresponding to the '1' bits in i
used std::next_permutation() to generate all permutations of xi
See https://en.wikipedia.org/wiki/Power_set and http://en.cppreference.com/w/cpp/algorithm/next_permutation
source to share
If I understood the problem correctly, it might be something like this. It uses std::next_permutation
to iterate through each order of processes and for each order it selects each sub-list or processes to run (sequentially) on the input:
std::string process_1(std::string const& s)
{ return s + 'a'; }
std::string process_2(std::string const& s)
{ return s + 'b'; }
std::string process_3(std::string const& s)
{ return s + 'c'; }
int main(int, char** argv)
{
using process = std::string(*)(std::string const&);
std::vector<process> processes;
processes.push_back(process_1);
processes.push_back(process_2);
processes.push_back(process_3);
std::vector<std::string> outputs;
std::sort(std::begin(processes), std::end(processes));
do
{
for(auto p = std::begin(processes); p != std::end(processes); ++p)
{
std::string s = "";
for(auto p1 = p; p1 != std::end(processes); ++p1)
s = (*p1)(s);
outputs.push_back(s);
}
}
while(std::next_permutation(std::begin(processes), std::end(processes)));
for(auto const& o: outputs)
std::cout << o << '\n';
}
Output:
abc
bc
c
acb
cb
b
bac
ac
c
bca
ca
a
cab
ab
b
cba
ba
a
NOTE: This method seems to create some duplicates. There must be a clever mathematical way to eliminate them, which eludes me right now, but you can always maintain std::set<std::vector<process>>
to record every combination that has already tried to make sure there are no repetitions. Or just remove duplicates from the output.
source to share