So currently I have an array int arr[] of a length that is an even number. My problem is that I am trying to pair each element up with another into a map unordered_map <int, int> pairs. As long as arr[] has a size that is greater than 2, there will be multiple possibilities. What I need is to generate all possible sets of pairings.
To clarify this objective, here is an example:
int arr[4] = {1, 2, 3, 4};
If that is the array, then the map could have these pairs:
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
For these types of problems, I automatically went for the recursive approach to have an indefinite number of nested loops going through each pair, marking them as already paired, and going into the next level of loops. However, some tries proved that this task is beyond my capabilities. Can anyone help me here?
My code:
#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;
}
The output I should get after I did pairUp() by hand is:
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
The solution was discovered when I realized I could pick the first non-paired number for each recursive run and cycle through the other possible second terms to pair the first up with and repeat until everything is paired. Also, there was an error. Since the elements in arr[] might not be numbered starting from 0 and increasing by one, some i and j in the code should become arr[i] and arr[j].
The full piece:
#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;
}
Test results:
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