Printing the Pair of Numbers in desired format

Question

Given pair of numbers,where frequency of each number is even(sum of frequency of both columns)

1 4
1 5
2 3
3 4
2 5

how could i modify the arrangement to a form such that each column has equal frequency count which would be half of the total frequency of a number in both column,i am only allowed to swap two column entries.

1 4
5 1
3 2
4 3
2 5

Can someone give me a hint,also make sure all components are connected in graph representation ,if disconnected print -1?

EDIT: the numbers are in n rows and two columns.

row1/col1:1
row1/col2:4
row2/col1:1
row2/col2:5

and the rest

Answer 1

That very interesting puzzle!

First what we need to do is to describe the problem in the graph theory. Vertices in the graph are numbers from the array. In your particular example it will be {1, 2, 3, 4, 5}. For every row we have edge, so in the example we get such graph:

This is undirected graph. Out goal is to direct every edge. If we have edge u, v we can direct it in one of two ways:

• u -> v, that means that we chose row to be: u v
• v -> u, that means that we chose row to be: v u

For every vertex u number of outgoing edges corresponds to number of frequency count of u in the left column. In the same way ingoing edges corresponds to number of frequency count in the right column.

Please notice, that if find direction of edges which satisfied condition: every vertex has the same number of ingoing and outgoing edges, we will also find the solution for original problem.

So now let me describe how to find these directions.

We will use two thesis:

1. Undirected graph has Eulerian circuit if and only if for every vertex u, number of its edges is even.
2. Directed graph has Eulerian circuit if and only if for every vertex u, u has the same number of ingoing and outgoing edges.

Just for case if you have never heard about Eulerian circuits :) https://en.wikipedia.org/wiki/Eulerian_path

From 1. we know, that the graph always has solution (because, as you wrote at the beginning frequency of each number is even). From 2. we get the algorithm to find solution: first we have to find the Eulerian circuit, and then direct every edge according to its appearance in the circuit.

And there is the good tutorial how to find Eulerian circuit:

Looking for algorithm finding euler path

Answer 2

First, just summarizing the problem:

We have two columns with a number of different tokens in them. Each token appears an even number of times. The goal is to swap rows such that in the end, each token appears an equal number of times in each column.

First I go through all the data, counting how many times each token appears.

Then for each token, I iterate through each column and check if that particular token appears. If I encounter more than n/2 tokens in that column, then it gets swapped.

This whole procedure is repeated until no more swapping was necessary.

I'm unsure of two things: a) will there, in general, always be a solution to the problem (I'm almost sure that this must be the case...)? B) Can I be sure that the iteration will always stop. I.e. it will not get stuck swapping things back and forth?

Anyway, here is some code that does this. Please note that there is no checking if the input is correct etc.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class my_pair
{
    private:
        int m_x,m_y;

    public:
        my_pair( int x, int y ) : m_x( x ), m_y( y ) {}

        void swap()
        {
            int tmp = m_x;
            m_x = m_y;
            m_y = tmp;
        }

        int x()
        {
            return m_x;
        }
        int y()
        {
            return m_y;
        }
};

int main()
{
    // Generate some input:
    // I'm assuming that the tokens in the columns are
    // in the form 0,1,2 etc such that the tokens
    // themselves can be interpreted as an index of an array.
    // I think there is no loss of generality here, as it can
    // be considered a re-labeling...

    vector<my_pair> pair_vector;

    pair_vector.push_back( my_pair( 0,1 ) );
    pair_vector.push_back( my_pair( 1,1 ) );
    pair_vector.push_back( my_pair( 2,2 ) );
    pair_vector.push_back( my_pair( 2,1 ) );
    pair_vector.push_back( my_pair( 2,0 ) );
    pair_vector.push_back( my_pair( 2,1 ) );
    pair_vector.push_back( my_pair( 2,1 ) );
    pair_vector.push_back( my_pair( 2,2 ) );

    cout << "Start vector:" << endl;

    for( auto p : pair_vector )
        cout << p.x() << ' ' << p.y() << endl;

    // 1: Count number of occurrences of each token.
    // Here the assumption on the tokens is used:
    vector<int> num_tokens;

    for( auto& p : pair_vector )
    {
        if( p.x()+1 > num_tokens.size() )
            num_tokens.resize( p.x()+1 );

        num_tokens[p.x()]++;

        if( p.y()+1 > num_tokens.size() )
            num_tokens.resize( p.y()+1 );

        num_tokens[p.y()]++;
    }


    // 2. Now I iterate through the columns for each token
    // and swap each token
    // that appears more often than n/2 times in that column,
    // where n is the number of appearances of each token:
    bool swap_was_performed = true;

    while( swap_was_performed )
    {
        int token = 0;
        swap_was_performed = false;

        for( auto& n : num_tokens ) // n is the number (or frequency) of tokens
        {
            int x_ctr = 0;
            int y_ctr = 0;

            // Iterating through the input columns:
            for( auto& p : pair_vector )
            {
                if( p.x()==token ) // x-values (i.e. the first column)
                {
                    x_ctr++;

                    if( x_ctr>n/2 )
                    {
                        p.swap();
                        swap_was_performed = true;
                    }
                }
            }

            for( auto& p : pair_vector )
            {
                if( p.y()==token ) // y-values...
                {
                    y_ctr++;

                    if( y_ctr>n/2 )
                    {
                        p.swap();
                        swap_was_performed = true;
                    }
                }
            }

            token++;
        }
    }


    cout << "After re-arranging:" << endl;

    for( auto p : pair_vector )
        cout << p.x() << ' ' << p.y() << endl;

}