テスト機能のすべての組み合わせをすべての注文

Question

に、私は、機能の束を持っているa.process、b.process、c.process ...、のaそれらを呼びましょう、b、c ...。

は初期std::string sを考えると、私は、任意の順序で呼び出されると、最初の入力としてs与えa、b、cの組み合わせのあらゆる可能な出力を生成したいです...。

ので、たとえば、私はなど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)))、

を計算したい、私は私がすべての順列を生成する機能を行うことができると思いますリスト、Pythonのitertools.permutationsのようなものが、私はここでは2つの主要な問題があります。

• を私はすべての順列をしたくありません私はすべての順番ですべての順列を欲しい。

• さらに重要なのは、Pythonで簡単にやっているような配列に関数を格納する方法について私は考えていません。

また、私は、可能な各出力は、私は上記の与え例えば、私は、出力は次の順序であることを知っているであろうように、それを生成した機能の組み合わせが付属していることが必要です。"a"、"b"、"c"、"ab"、など"ac"、"ba"、"bc"、"ca"、"cb"、​​、

は、どのように私はC++でそれを実装するだろうか？

Answer 1

配列に関数を格納するには、function pointersを使用する必要があります。これは次のようなことでしょう：

次に、配列のすべての組み合わせを生成して文字列に適用するだけです。 this questionを見てください。

Answer 2

いくつかのアイデアや擬似コード関数ポインタの

配列、機能ごとに1。我々はまた、

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 

が必要

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 

は、それぞれの組み合わせのために、我々はすべての可能な順列を必要としています。私。

For all k = 1 to n, 
    All permutations of (All combinations of n-choose-k) 

スケッチ

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 

私が右多分このような何かを、問題を理解している場合はhttps://en.wikipedia.org/wiki/Power_setとhttp://en.cppreference.com/w/cpp/algorithm/next_permutation

Answer 3

を参照してください。

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

出力：

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

これは、プロセスのすべての発注を通じて、すべての注文、それは入力に（連続的に）動作させるために、各サブリストまたはプロセスを選択するために反復するstd::next_permutationを使用しています注：このメソッドはいくつかの重複を生成するようです。今は私を逃しているものを排除するための巧妙な数学的方法があるはずですが、反復がないことを確かめるために既に試みられたすべての組み合わせを記録するために常にstd::set<std::vector<process>>を維持することができます。または単に出力から重複を削除します。

Answer 4

Sid's answerを実際のコードに書き込んでいます。 Galik's answer異なり、これが重複私の関数はインスタンスから抽出された場合、私はそれを行う必要がありますどのように

#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