C++ Combinatorics 组合高性能函数

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