How to create an algorithm to find all possible pairings (referring to the chinese postman problem)?

When trying to solve the chinese postman problem you will have to find minimum cost of all possible pairings of all odd vertexes in the graph and add found edges (pairings), which my question is almost about.

How to implement an algorithm, which returns all possible pairings? or how to fix mine.

I got a starting point, but am not able to go or think further.

I tried looking on following topics but they did'nt help me unfortunetly. How should I generate the partitions / pairs for the Chinese Postman problem? or Find the pairings such that the sum of the weights is minimized?

std::vector<std::vector<int>> Postman::pairOdd(std::vector<int> vertices)
{   
    std::vector<std::vector<int>> pairs;
    if (vertices.empty()) {
        return std::vector<std::vector<int>>();
    }
    else {
        auto it = std::min_element(vertices.begin(), vertices.end());
        int i = *it;
        vertices.erase(it);
        for (int index = 0; index < vertices.size(); index++) {
            int j = vertices[index];
            vertices.erase(vertices.begin() + index);
            pairs.push_back(std::vector<int>{i, j});
            std::vector<std::vector<int>> returnValue = pairOdd(vertices);
            pairs.insert(pairs.end(), returnValue.begin(), returnValue.end());
            vertices.insert(vertices.begin(), j);
        }
        vertices.insert(vertices.begin(), i);
    }
    return pairs;
}

Output with

std::vector<std::vector<int>> res = pairOdd(std::vector<int>{1,2,3,4,5,6});
for (auto v : res) {
    for (auto u : v) {
        std::cout << u;
    }
    std::cout << std::endl;
}

should be:

1 2  3 4  5 6
1 2  3 5  4 6
1 2  3 6  4 5
1 3  2 4  5 6
1 3  2 5  4 6
1 3  2 6  4 5
1 4  2 3  5 6
1 4  2 5  3 6
1 4  2 6  3 5
1 5  2 3  4 6
1 5  2 4  3 6
1 5  2 6  3 4
1 6  2 3  4 5
1 6  2 4  3 5
1 6  2 5  3 4

But is:

I can't quite fix how I insert into the vector. When looking at the output, you can see that it is almost right (ignoring the formatting). First line 12 34 45 is correct. Second 35 46, when it has to be 12 35 36, seems that only the first pair is missing, which you will notice applies to every pairings.

Update: So I came up with another algorithm which seems to be promising, but instead of missing some pairs, I get duplicates. A solution is highly appreciated. If I find one myself I will post it.

std::vector<std::vector<int>> Postman::aaa(std::vector<int> vertices, std::vector<int> list, int in1, int in2)
{
    std::vector<std::vector<int>> pairs;
    if (vertices.empty()) {
        list.push_back(in1);
        list.push_back(in2);
        pairs.push_back(list);
        return pairs;
    }
    else {
        auto it = std::min_element(vertices.begin(), vertices.end());
        int i = *it;
        vertices.erase(it);
        for (int index = 0; index < vertices.size(); index++) {
            int j = vertices[index];
            vertices.erase(vertices.begin() + index);

            if (in1 != 0 && in2 != 0) {
                list.push_back(in1);
                list.push_back(in2);
            }

            std::vector<std::vector<int>> returnValue = aaa(vertices, list, i, j);
            pairs.insert(pairs.end(), returnValue.begin(), returnValue.end());

            vertices.insert(vertices.begin(), j);
        }
        vertices.insert(vertices.begin(), i);
    }
    return pairs;
}

Output:

Solution

So I found a solution for the second algorithm I mentioned. The problem was I send the pair to the next recursion step to be then added in this step. So when you returned from a recursion step the pairing would still be in there. So I just deleted this pair, so the new one can be added. Instead of just returning an int vector I made an pair vector. Visualizing the return value better. I am willing to listen to any improvements to this algorithm or any good practices.

I am willing to listen to any improvements to this algorithm or any good practises.

std::vector<std::vector<std::pair<int, int>>> Postman::pairing(std::vector<int> vertices, std::vector<std::pair<int, int>> list)
{
    std::vector<std::vector<std::pair<int, int>>> pairs;
    if (vertices.empty()) {
        pairs.push_back(list);
        return pairs;
    }
    else {
        auto it = std::min_element(vertices.begin(), vertices.end());
        int i = *it;
        vertices.erase(it);
        for (int index = 0; index < vertices.size(); index++) {
            int j = vertices[index];
            vertices.erase(vertices.begin() + index);

            std::pair<int, int> pair(i, j);
            list.push_back(pair);

            std::vector<std::vector<std::pair<int, int>>> r = pairing(vertices, list);

            list.erase(list.end() - 1);

            pairs.insert(pairs.end(), r.begin(), r.end());

            vertices.insert(vertices.begin(), j);
        }
    }
    return pairs;
}

std::vector<std::vector<std::pair<int, int>>> a = pairing(vertices, std::vector<std::pair<int, int>>());
for (auto v : a) {
    for (auto p : v) {
        std::cout << '(' << p.first << ' ' << p.second << ')';
    }
    std::cout << std::endl;
}