c++ - 递归算法将所有组合分为两组

Question

我需要一种算法，在给定偶数个元素的情况下，对分为两组的元素的所有组合进行评估。组内的顺序无关紧要，因此不应重复组内的排列。 N=4 元素的示例是评估

e(12,34), e(13,24), e(14,32), e(32,14), e(34,12), e(24,13)

我以为我已经掌握了，递归算法可以达到 N=6，但事实证明它在 N=8 时失败了。这是算法(此版本仅打印出两组；在我的实际实现中，它将执行计算):

// Class for testing algoritm
class sym {

    private:
    int N, Nhalf, combs;
    VI order;
    void evaluate();
    void flip(int, int);
    void combinations(int, int);

    public:
    void combinations();

    sym(int N_) : N(N_) {
        if(N%2) {
           cout "Number of particles must divide the 2 groups; requested N = " << N << endl;
           throw exception();
        }
        Nhalf=N/2;
        order.resize(N);
        for(int i=0;i<N;i++) order[i]=i+1;  
    }

    ~sym() {
        cout << endl << combs << " combinations" << endl << endl;
    }
};

// Swaps element n in group 1 and i in group 2
void sym::flip(int n, int i) {
    int tmp=order[n];
    order[n]=order[i+Nhalf];
    order[i+Nhalf]=tmp;
}

// Evaluation (just prints the two groups)
void sym::evaluate() {
    for(int i=0;i<Nhalf;i++) cout << order[i] << " ";
    cout << endl;
    for(int i=Nhalf;i<N;i++) cout << order[i] << " ";
    cout << endl << "--------------------" << endl;
    combs++;
}

// Starts the algorithm
void sym::combinations() {
    cout << "--------------------" << endl;
    combinations(0, 0);
} 

// Recursive algorithm for the combinations
void sym::combinations(int n, int k) {
    if(n==Nhalf-1) {
        evaluate();
        for(int i=k;i<Nhalf;i++) {
            flip(n, i);
            evaluate();
            flip(n, i);
        }
        return;
    }
    combinations(n+1, k);
    for(int i=k;i<Nhalf;i++) {
        flip(n, i);
        combinations(n+1, k+i+1);
        flip(n, i);
    }
}

例如，如果我使用 N=2 运行它，我会得到正确的结果

--------------------
1 2 
3 4 
--------------------
1 3 
2 4 
--------------------
1 4 
3 2 
--------------------
3 2 
1 4 
--------------------
3 4 
1 2 
--------------------
4 2 
3 1 
--------------------

6 combinations

但似乎 N>6 不起作用。是否有一个简单的更改可以解决此问题，还是我必须重新考虑整个事情？

编辑:最好每次更改都涉及交换两个元素(如上面失败的尝试)；因为我认为这最终会使代码更快。

编辑:刚刚意识到 N=6 也失败了，草率的测试。

Answer 1

std::next_permutation 可能有帮助(无需递归):

#include <iostream>
#include <algorithm>

template<typename T>
void do_job(const std::vector<T>& v, const std::vector<std::size_t>& groups)
{
    std::cout << " e(";
    for (std::size_t i = 0; i != v.size(); ++i) {
        if (groups[i] == 0) {
            std::cout << " " << v[i];
        }
    }
    std::cout << ",";
    for (std::size_t i = 0; i != v.size(); ++i) {
        if (groups[i] == 1) {
            std::cout << " " << v[i];
        }
    }
    std::cout << ")\n";
}

template<typename T>
void print_combinations(const std::vector<T>& v)
{
    std::vector<std::size_t> groups(v.size() / 2, 0);
    groups.resize(v.size(), 1); // groups is now {0, .., 0, 1, .., 1}

    do {
        do_job(v, groups);
    } while (std::next_permutation(groups.begin(), groups.end()));
}

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4};
    print_combinations(numbers);
}

Live Demo