c++ - 在给定数组中生成所有元素对的有效方法

Question

假设我得到了数组{1, 2, 3, 4}，其中 n（数组的大小）在 2 到 18 之间。我需要找到成对排列这些元素的所有方法。所以对于这个例子，我会得到：

(1, 2), (3, 4)

(1, 3), (2, 4)

(1, 4), (2, 3)

所以这里的顺序有点重要，因为我不想/不需要生成配对相同的所有排列（我认为？）。（(1, 2), (3, 4)例如(3, 4), (1, 2)。）

我已经尝试过一种可行的递归回溯方法，但对于较大的数组（14-18）来说，它的时间效率并不高，我需要所有可能的输入的执行时间低于 2 秒。

这是我的代码：

void gen_sol(int k)
{
    if(k > n)
    {
        //do further calculations    
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = i + 1; j <= n; j++)
            {
                if(k == 1)
                {
                    if(!used[i] && !used[j])
                    {
                        sol[k] = v[i];
                        sol[k + 1] = v[j];
                        used[i] = true;
                        used[j] = true;
                        gen_sol(k + 2);
                        used[i] = false;
                        used[j] = false;
                    }
                }
                else
                {
                    if(sol[k - 2] < v[i] && !used[i] && !used[j])
                    {
                        sol[k] = v[i];
                        sol[k + 1] = v[j];
                        used[i] = true;
                        used[j] = true;
                        gen_sol(k + 2);
                        used[i] = false;
                        used[j] = false;
                    }
                }
            }
        }
    }
}

现在我知道简短的、不具描述性的名称通常是不受欢迎的，但我认为这在竞争激烈的编程环境中并不算太糟糕。所以k表示递归级别/我正在使用的当前对，sol是我正在构建当前排列的数组，并used用于指示我已经使用的数组的哪些元素。

关于实际的对生成，我将当前可能的对集与前一个进行比较，以查看其是否按字典顺序排列。我知道我可能可以合并循环内的 2 个单独的 if 语句，我应该这样做。

我曾考虑过尝试一种迭代方法，但无论如何，n=18 的执行时间对于这种方法来说太长了，我认为迭代不会有太大帮助。

有没有办法减少一个循环？

标签： c++backtracking