c - 将数组排列成所有可能的对

Question

我正在解决一个问题(在 C 中)，它要求我列出偶数个点之间的所有可能连接，以便每个点都只连接到一个其他点。例如，假设我有点 1、2、3 和 4:

• 1 - 2, 3 - 4
• 1 - 3, 2 - 4
• 1 - 4, 2 - 3

点的顺序无关紧要(1 - 2 与 2 - 1 相同)，连接顺序也无关紧要(1 - 2、3 - 4 与 3 - 4 相同、1 - 2 ).

我目前正在尝试简单地将诸如 {1, 2, 3, 4} 之类的数组排序为所有可能的顺序，并检查它是否已经生成。然而，这可能非常昂贵，而且需要忽略点和对的顺序。

将数组排列成所有可能的对的更好方法是什么？算法的基本概述将不胜感激!

编辑:在上面带有 {1, 2, 3, 4} 的示例中，如果配对表示为数组中的两个相邻元素，则所有可能的结果将是:

• {1, 2, 3, 4}: 1 - 2, 3 - 4
• {1, 3, 2, 4}: 1 - 3, 2 - 4
• {1, 4, 2, 3}: 1 - 4, 2 - 3

我需要整个排列的数组来执行基于所有连接的计算。

Answer 1

这可以通过非确定性配对最右边未配对的元素并递归来实现。在 C 中:

void enum_matchings(int n, int a[static n]) {
    if (n < 2) {
        // do something with the matching
        return;
    }
    for (int i = 0; i < n-1; i++) {
        int t = a[i];
        a[i] = a[n-2];
        a[n-2] = t;
        enum_matchings(n-2, a);
        a[n-2] = a[i];
        a[i] = t;
    }
}