test toutes les combinaisons de fonctions dans chaque commande

Question

J'ai un tas de fonctions, a.process, b.process, c.process ..., appelons-les a, b, c ... que tous prennent un std::string comme paramètre et retourner un std::string.

Compte tenu d'une std::string s initiale, je veux générer chaque sortie de combinaisons possibles de a, b, c ... appelé dans un ordre donné et s en entrée initiale.

Ainsi, par exemple, je veux calculer 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.

Je pense que je pourrais faire une fonction pour générer toutes les permutations de une liste, quelque chose comme Python itertools.permutations mais j'ai deux principales questions ici:

• Je ne veux simplement toutes les permutations , Je veux chaque permutation dans chaque ordre.

• Et plus important encore, je ne sais pas sur la façon de stocker des fonctions dans des tableaux comme on pourrait facilement le faire en Python.

Je dois aussi que chaque sortie possible est livré avec les combinaisons de fonctions qui ont généré si pour l'exemple que j'ai donné ci-dessus, je sais que les résultats sont dans l'ordre suivant: "a", "b", "c", "ab", "ac", "ba", "bc", "ca", "cb", "abc", etc.

Comment pourrais-je mettre en œuvre que dans C++?

Answer 1

Pour le stockage des fonctions dans un tableau, vous devez utiliser function pointers. Quelque chose comme cela ferait:

typedef string (*t_fnPtr)(string); 
t_fnPtr fnPtrArray[10]; //Initialize this with your functions 

Ensuite, il est juste une question de générer toutes les combinaisons de votre tableau et l'appliquer à la chaîne. Regardez this question.

Answer 2

Quelques idées et pseudocode

Tableau de pointeurs de fonction, un pour chaque fonction.

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 

Nous avons besoin

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 

De plus, pour chaque combinaison, nous avons besoin de toutes les permutations possibles. C'est à dire.

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 

Voir https://en.wikipedia.org/wiki/Power_set et http://en.cppreference.com/w/cpp/algorithm/next_permutation

Answer 3

Si je comprends le problème tout peut-être quelque chose comme ça. Il utilise std::next_permutation pour parcourir chaque commande de processus et pour chaque commande sélectionne chaque sous-liste ou procédés pour faire fonctionner (successivement) sur l'entrée:

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'; 
} 

sortie:

abc 
bc 
c 
acb 
cb 
b 
bac 
ac 
c 
bca 
ca 
a 
cab 
ab 
b 
cba 
ba 
a 

NOTE: Il semble que cette méthode produit des doublons. Il devrait y avoir un moyen mathématique intelligent pour les éliminer qui me manque maintenant mais vous pouvez toujours maintenir un std::set<std::vector<process>> pour enregistrer chaque combinaison qui a déjà été essayée pour s'assurer qu'il n'y a pas de répétitions. Ou simplement supprimer les doublons de la sortie.

Answer 4

Je suis juste en train d'étoffer Sid's answer en code réel. A la différence de Galik's answer, cela ne produit pas de doublons

#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())); 
    } 
} 

Live example