C++コンビナトリアルコンビネーション高性能機能

Question

ここは私のコンビナトリアルコンビネーションの機能です。例えば

：将来的には組み合わせ"ABCD", 2 = AB AC AD BC BD CD.

、私はそれぞれの組み合わせ（だけでなく、printf）でいくつかの操作を行います。

このコードのパフォーマンスを向上させる方法はありますか？

#include "stdafx.h" 
#include "iostream" 
#include <vector> 

void display(std::vector<char> v, int* indices, int r)//f() to display combinations 
{ 
     for (int i = 0; i < r; ++i) 
      std::cout << v[indices[i]]; 
     std::cout << std::endl; 
} 

void combinations(std::vector<char> v, int n, int r, void(*f)(std::vector<char>, int*, int)) 
{ 
     int* indices = new int[r]; 
     for (int i = 0; i < r; ++i) 
      indices[i] = i; 

     int count; 
     bool b; 
     f(v, indices, r); 
     while (true) 
     { 
      b = true; 
      for (count = r - 1; count >= 0; --count) 
      { 
        if (indices[count] != count + n - r) 
        { 
          b = false; 
          break; 
        } 
      } 
      if (b) 
        break; 

      ++indices[count]; 
      for (int i = count + 1; i < r; ++i) 
        indices[i] = indices[i - 1] + 1; 

      f(v, indices, r); 
     } 
     delete[] indices; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
     std::vector<char> v(4);//pool 
     v[0] = 'A'; 
     v[1] = 'B'; 
     v[2] = 'C'; 
     v[3] = 'D'; 

     int n = 4;// pool size 
     int r = 2;// length of each combination 

     combinations(v, n, r, display);// pool, pool size, len of combination, func for each combination 
     return 0; 
} 

Answer 1

パフォーマンスはわかりませんが、可読性も重要です。 再帰の解を参照してください。 http://cpp.sh/2jimb

#include <iostream> 
#include <string> 

typedef unsigned int uint; 
typedef std::string::iterator seq_iterator; 

std::string FindCombinations(seq_iterator current, seq_iterator end, uint comb_length, std::string comb) 
{ 
    if (comb_length == 0 || comb_length > std::distance(current, end)) 
     return comb;//no more possible combinations 

    auto next = current + 1; 

    std::string with; 
    if (std::distance(next, end) >= comb_length - 1) 
     with = FindCombinations(next, end, comb_length - 1, comb + *current);//use current in combination 
    std::string without; 
    if (std::distance(next, end) >= comb_length) 
     without = FindCombinations(next, end, comb_length, comb);//skip current in combination 

    std::string result = with; 
    if (!result.empty() && !without.empty()) 
     result += ' '; 
    return result + without; 
} 

int main() 
{ 
    std::string seq = "ABCDE"; 
    std::cout << FindCombinations(seq.begin(), seq.end(), 2, "") << std::endl; 
}