我需要一个算法，在给定偶数个元素的情况下，对分为两组的元素的所有组合进行评估。组内的顺序并不重要，因此组内的排列不应该重复。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时也失败了，测试很草率。
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);
}
实时演示
// generate all combination that use n of the numbers 1..k
void sym::combinations(int n, int k) {
if (n>k) return; // oops
if (n==0) { evaluate(); return; }
combinations(n, k-1);
order[n-1] = k;
combinations(n-1,k-1);
}
从combinations(N/2,N)开始，无需预先初始化order。但在编码时，它只用第一组填充order的前半部分，您需要发布处理才能获得第二组。
使用适量的额外逻辑，您可以在combinations期间填充后半部分。我认为这样做：
void sym::combinations(int n, int k) {
if (k==0) { evaluate(); return; }
if (n>0) {
order[n-1] = k;
combinations(n-1,k-1); }
if (n<k) {
order[Nhalf+k-n-1] = k;
combinations(n, k-1); }
}
我认为翻盖设计更难看。但经过深思熟虑，这其实并不难。因此，改回从combinations(0,0)开始的设计，您可以使用：
// Generate all combinations subject to having already filled the first n
// of the first group and having already filled the last k of the second.
void sym::combinations(int n, int k) {
if(n==Nhalf) {
// Once the first group is full, the rest must be the second group
evaluate();
return;
}
// Since the first group isn't full, recursively get all combinations
// That make the current order[n] part of the first group
combinations(n+1,k);
if (k<Nhalf) {
// Next try all combinations that make the current order[n] part of
// the second group
std::swap(order[n], order[N-k-1]);
combinations(n,k+1);
// Since no one cares about the sequence of the items not yet chosen
// there is no benefit to swapping back.
}
}
要递归地列出n choose n/2组合，可以使用一种算法将每个值添加到任一组：
f(n,k,A,B):
if k == 0:
output A,B with {n,n-1..1}
else if n == k:
output A with {n,n-1..1},B
else if k > 0:
f(n-1,k-1,A with n,B)
f(n-1,k,A,B with n)
以下示例。为了达到累积堆栈的一半，可以跳过前两个递归调用中的一个，并在求值过程中反转对的顺序。
f(4,2,[],[])
f(3,1,[4],[])
f(2,0,[4,3],[]) => {[4,3],[2,1]}
f(2,1,[4],[3])
f(1,0,[4,2],[3]) => {[4,2],[3,1]}
f(1,1,[4],[3,2]) => {[4,1],[3,2]}
f(3,2,[],[4])
f(2,1,[3],[4])
f(1,0,[3,2],[4]) => {[3,2],[4,1]}
f(1,1,[3],[4,2]) => {[3,1],[4,2]}
f(2,2,[],[4,3]) => {[2,1],[4,3]}