如何在C++中使用递归函数调用对偶数长度整数数组的每个元素进行配对？

xkrw2x1b 于 2023-05-30 发布在其他

关注(0)|答案(1)|浏览(130)

所以目前我有一个长度为偶数的数组int arr[]。我的问题是，我试图将每个元素与另一个元素配对到Mapunordered_map <int, int> pairs中。只要arr[]的大小大于2，就有多种可能性。我需要的是生成所有可能的配对集。
为了阐明这一目标，下面是一个示例：

int arr[4] = {1, 2, 3, 4};

如果这是数组，那么map可以有这些对：

pairs = {{1, 2}, {2, 1}, {3, 4}, {4, 3}};//1 and 2, 3 and 4
pairs = {{1, 3}, {3, 1}, {2, 4}, {4, 2}};//1 and 3, 2 and 4
pairs = {{1, 4}, {4, 1}, {2, 3}, {3, 2}};//1 and 4, 2 and 3

对于这些类型的问题，我自动选择了递归方法，让无限数量的嵌套循环通过每一对，将它们标记为已经配对，并进入下一级循环。然而，一些尝试证明这项任务超出了我的能力。有人能帮我吗？
我的代码：

#include <iostream>
#include <deque>
#include <unordered_map>
int n = 4;
std::unordered_map <int, int> pairs;
std::deque <int> arr = {0, 1, 2, 3};
std::deque <bool> paired = {false, false, false, false};
bool finishedPairing() {
    for (int i = 0; i < n; i++) {
        if (paired[i] == false) { return false; }
    }
    return true;
}
void pairUp() {
    if (finishedPairing()) {
        std::cout << "\nNew Set:\n";
        for (int i = 0; i < 4; i++) {
            std::cout << i << " is paired with " << pairs[i] << '\n';
        }
        return;
    }
//what I need written as C++ code
}
int main () {
    pairUp();
    return 0;
}

在我手动执行pairUp()之后，应该得到的输出是：

New Set:
0 is paired with 1
1 is paired with 0
2 is paired with 3
3 is paired with 2

New Set:
0 is paired with 2
1 is paired with 3
2 is paired with 0
3 is paired with 1

New Set:
0 is paired with 3
1 is paired with 2
2 is paired with 1
3 is paired with 0

c++

来源：https://stackoverflow.com/questions/76301699/how-to-pair-every-element-of-an-even-length-integer-array-in-c-using-recursive

1条答案

按热度按时间

bvjxkvbb1#

当我意识到我可以为每次递归运行选择第一个非配对数，并循环遍历其他可能的第二项，将第一项与第一项配对并重复，直到所有项配对时，我发现了解决方案。还有一个错误。由于arr[]中的元素可能不会从0开始递增1，因此代码中的某些i和j应该变为arr[i]和arr[j]。
全篇：

#include <iostream>
#include <deque>
#include <unordered_map>
using namespace std;
int n = 4;
std::unordered_map <int, int> pairs;
std::deque <int> arr = {0, 1, 2, 3};
std::deque <bool> paired = {false, false, false, false};
bool finishedPairing() {
    for (int i = 0; i < n; i++) {
        if (paired[i] == false) { return false; }
    }
    return true;
}
void pairUp() {
    if (finishedPairing()) {
        std::cout << "\nNew Set:\n";
        for (int i = 0; i < 4; i++) {
            std::cout << arr[i] << " is paired with " << pairs[arr[i]] << '\n'; //changed i into arr[i]
        }
        return;
    }
//add portion:
    int i = 0;
    while (paired[i] == true) { i++; } //find first non-paired
    paired[i] = true;//pair it
    for (int j = 0; j < n; j++) {
        if (paired[j] == false) { //find a counterpart
            paired[j] = true, pairs[arr[i]] = arr[j], pairs[arr[j]] = arr[i];//pair it
            pairUp();//next recursive run
            paired[j] = false;//reset
        }
    }
    paired[i] = false;//reset
}
int main () {
    pairUp();
    return 0;
}

测试结果：

New Set:
0 is paired with 1
1 is paired with 0
2 is paired with 3
3 is paired with 2

New Set:
0 is paired with 2
1 is paired with 3
2 is paired with 0
3 is paired with 1

New Set:
0 is paired with 3
1 is paired with 2
2 is paired with 1
3 is paired with 0

赞(0）回复(0）举报 2023-05-30

我来回答

如何在C++中使用递归函数调用对偶数长度整数数组的每个元素进行配对？

1条答案

相关问题

热门标签

最新问答