Multiple column sorting and arraging algorithm

Question

Problem

The goal is to perform the following transformation:

Additionally, if two rows can be merged, they are combined into one:

Code

I wrote the following algorithm to solve this problem:

#include <vector>
#include <iostream>
#include <algorithm>

using Matrix = std::vector<std::vector<int>>;
using Column = std::vector<int>;

Column max_col(const Matrix &v) {
    return *std::max_element(v.begin(), v.end(),
                             [](auto& lhs, auto& rhs)
                             {
                                 return lhs.size() < rhs.size();
                             });
}

bool is_element_in_next_rows(const Matrix &v, int element,int row) {
    for (auto& col : v) {
        if (row >= static_cast<int>(col.size())) continue; // out of range
        if (std::lower_bound(col.begin()+row+1,col.end(),element) != 
            std::upper_bound(col.begin()+row+1,col.end(),element)) {
            return true;
        }
    }
    return false;
}

int min_element_in_row(const Matrix &v, int row) { 
    int min_element = max_col(v)[row];
    for (auto& col : v) {
        if (row >= static_cast<int>(col.size())) continue; // out of range
        if (col[row] != 0) min_element = std::min(min_element, col[row]);
    }
    return min_element;
}

void print_elements(const Matrix &v) {
    for (auto& i : v) {
        for (auto& j : i) {
            std::cout << j << " ";
        }
        std::cout << std::endl;
    }
}

void organize_elements(Matrix &v) {
    for (auto& col : v) {
        std::sort(col.begin(),col.end());
    }
    auto current_max_col = max_col(v);
    for (int row{0}; current_max_col.begin()+row!=current_max_col.end(); ++row) {
        int min_element = min_element_in_row(v,row);
        for(auto& col : v) {
            if (row >= static_cast<int>(col.size())) continue; // out of range
            int candidate = col[row];
            if (candidate > min_element) {
                if (is_element_in_next_rows(v,candidate,row)) {
                    col.push_back(0);
                    std::rotate(col.begin()+row,col.end()-1,col.end());
                }
            }
        }
        current_max_col = max_col(v);
    }
}

int main() {

    Column c1 = {5,6,8,11};
    Column c2 = {2,5,3,1,4,6};
    Column c3 = {8,7,2,4,5,3,1};

    Matrix v;
    v.push_back(c1);
    v.push_back(c2);
    v.push_back(c3);

    std::cout << "original: \n";
    print_elements(v);
    organize_elements(v);
    std::cout << "organized: \n";
    print_elements(v);
    return 0;
}

Which produces the following output:

original: 
5 6 8 11 
2 5 3 1 4 6 
8 7 2 4 5 3 1 
organized: 
0 0 0 0 5 6 8 11 
1 2 3 4 5 6 
1 2 3 4 5 7 8 

Questions

I particularly don't like this part of my code:

auto current_max_col = max_col(v);
for (int row{0}; current_max_col.begin()+row!=current_max_col.end(); ++row) {
    // ....
    current_max_col = max_col(v);
}

I also don't like that I have to do this cast:

if (row >= static_cast<int>(col.size())) continue; // out of range

Is there a way to do this check better?

The fact that I need to declare current_max_col out of the for, and then update it inside the loop. Any idea how to avoid this?

Any other ideas about how to solve this problem? Any other tips? Thank you!

Answer 1

I believe that you can leverage the stl algorithms better. There are still too many raw loops in your code...

I understand why you fell in love with std::rotate but it isn't the only tool at your disposal.

For instance, std::min_element is flexible enough to handle the min_element_in_row:

int row_minimum(const Matrix& m, std::size_t row) {
    return std::min_element(m.begin(), m.end(), [row](auto&& lhs, auto&& rhs) {
            if (row < lhs.size()) {
                if (row < rhs.size()) return lhs[row] < rhs[row];
                return true;
            }
            return false;
        })->at(row);
}

Also, there is no need to compare the results of std::lower_bound and std::upper_bound. You know that the element is in the range if *std::lower_bound(b, e, elem) == elem, because it returns an iterator to the first element equal to or greater than elem.

That said, here's my suggestion (I'm not handling row combinations though):

#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>

void normalize_columns(Matrix& m) {
    for (auto& col : m) std::sort(col.begin(), col.end());
    // build a 'synthetized' column by merging columns and removing duplicates
    Column merger;
    for (const auto& col : m) {
        Column tmp;
        std::merge(col.begin(), col.end(), merger.begin(), merger.end(), std::back_inserter(tmp));
        std::swap(tmp, merger);
    }
    auto uniques = std::unique(merger.begin(), merger.end());
    // replace each column by a copy of the synthetized column 
    //from which all elements not included in the original column are replaced by 0
    for (auto& col : m) {
        Column normalized;
        std::replace_copy_if(merger.begin(), uniques, std::back_inserter(normalized),
                             [&col](auto&& elem) { 
                                 return *std::lower_bound(col.begin(), col.end(), elem) != elem; 
                             }, 0);
        std::swap(col, normalized);
    }
}

int main() {

    Column c1 = {5,6,8,11};
    Column c2 = {2,5,3,1,4,6};
    Column c3 = {8,7,2,4,5,3,1};

    Matrix m{c1, c2, c3};

    normalize_columns(m);
    for (auto& col : m) {
        for (auto elem : col) std::cout << elem << ' ';
        std::cout << '\n';
    }

}

The output is slightly different from yours but seems to fit the problem specification:

0 0 0 0 5 6 0 8 11    
1 2 3 4 5 6 0 0 0 
1 2 3 4 5 0 7 8 0 

Answer 2

It seems that the transform you are after is a k-way merge in disguise.

In the nutshell, set up a min-heap of pairs <col_id, vector<int>::iterator>. On each iteration construct a vector of values equal to heap head, 0 otherwise; push it to the resulting matrix; remove those entries from heap an pull new values from the respective columns. Sorry if I miss something obvious.

I don't think you shall strive for in-place transform.

---

I am pretty sure that merging rows deserve a separate pass.

---

The

                col.push_back(0);
                std::rotate(col.begin()+row,col.end()-1,col.end());

is no better than col.insert(col.begin() + row, 0);

---

The static_cast<int>(col.size()) suggests that row should not be int, but along the lines of std::vector<int>::size_type.