row and column of an index above of the main diagonal of the matrix (n * n)

Question

As you can see in the image, I indexed all items above the main diagonal of the matrix (n * n) starting from 0. I need an algorithm to get this index and give us the row and the column. I wrote a code in c++ and it works properly, however, I wondered if there is any smart/simpler algorithm to find the result. Thanks.

My code:

int inputIndex = 8;
int n = 5;

int row = 0, column = 0;
for (int i = 0; i < n - 1; ++i) {
    if (inputIndex < n - i - 1){
        row = i;
        column = inputIndex + i + 1;
        break;
    }
    inputIndex -= n - i - 1;
}

cout << "row = " << row << endl << "column = " << column;

Output:

row = 2
column = 4

Answer 1

Not necessarily easier, but you can calculate all mappings at compile time and then also use them at runtime. Meaning that at least the for loops don't have to run over and over again.

#include <array>
#include <stdexcept>
#include <limits>
#include <iostream>

// put this in a header file
namespace details
{

    // create a structure to hold row/col data this allows 
    // those two values to be returned from one function call.
    struct position_t
    {
        position_t() = default;

        constexpr position_t(const std::size_t r, const std::size_t c) :
            row{ r },
            col{ c }
        {
        }

        std::size_t row = 0;
        std::size_t col = 0;
    };

    // function to compare two position_t structs, used later in static_assert.
    // constexpr means the compiler can call this function at compile time.
    constexpr bool operator==(const position_t& lhs, const position_t& rhs)
    {
        return ((lhs.row == rhs.row) && (lhs.col == rhs.col));
    }

    // template class based on the size of the matrix
    // this class will store precalculated mappings from index to position and the 
    // other way around.
    template<std::size_t N>
    class index_map_t
    {
    public:

        // allow class to be instantiated at compile time 
        constexpr index_map_t() :
            m_to_pos{},
            m_to_index{}
        {
            std::size_t index{ 0ul };
            for (std::size_t row = 0; row < N; ++row)
            {
                for (std::size_t col = 0; col < N; ++col)
                {
                    // row by row the index is increased only
                    // if the column value is greater then the row value
                    // (the upper right half of the matrix)
                    if (col > row)
                    {
                        // store valid position/index values in internal arrays
                        // std::array can be used in constexpr
                        m_to_pos[index] = position_t{ row, col };
                        m_to_index[row][col] = index;
                        index++;
                    }
                    else
                    {
                        // for positions in the lower left half fill in "invalid" indices
                        // so we can detect them.
                        m_to_index[row][col] = std::numeric_limits<std::size_t>::max();
                    }
                }
            }
        }

        // convert a position to an index.
        constexpr auto to_index(const std::size_t row, const std::size_t col) const
        {
            if ((row >= N) || (col >= N)) throw std::invalid_argument("position out of range");

            if (m_to_index[row][col] == std::numeric_limits<std::size_t>::max())
            {
                throw std::invalid_argument("no inverse lookup for this position, position is not in upper-right half of matrix");
            }

            return m_to_index[row][col];
        }

        // convert an index to a position_t
        constexpr auto to_position(const std::size_t i) const
        {
            return m_to_pos[i];
        }

    private:
        // for this N*N sparse matrix type there will be 2*N valid indices
        std::array<position_t, 2 * N> m_to_pos;                 

        // the inverse mapping is a bit less memory efficient and
        // will be an N*N array.
        std::array<std::array<std::size_t, N>, N> m_to_index;
    };

} // details

int main()
{
    // calculate mapping at compile time for a 5x5 matrix
    // you can use this as member in your matrix class
    constexpr details::index_map_t<5> remapping;

    // this means we can even check the calculations at compile time
    static_assert(remapping.to_position(0) == details::position_t{ 0,1 });
    static_assert(remapping.to_position(1) == details::position_t{ 0,2 });
    static_assert(remapping.to_position(2) == details::position_t{ 0,3 });
    static_assert(remapping.to_position(3) == details::position_t{ 0,4 });
    static_assert(remapping.to_position(4) == details::position_t{ 1,2 });
    // etc..

    static_assert(remapping.to_index(1, 3) == 5);
    static_assert(remapping.to_index(3, 4) == 9);

    // runtime code
    auto pos = remapping.to_position(5);
    std::cout << "The position for index 5 : row = " << pos.row << ", col = " << pos.col << "\n";
    return 0;
}