表格单元格/ 2d数组排序算法

Question

Is there an algorithm that could help sort the left table (which is an abstraction for multidimensional array of scalars or objects) down below so the result would be as in the right one, given that there maybe a limited amount of available depth in the right table (e.g. max of 30 rows)?

And slightly more complex version of the problem (first key in a cell is having precedence over another):

EDIT: And another level of complexity (merge rows/levels if it's safe to do so to prevent redundancy):

Answer 1

A possible solution could be this:

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

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

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

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

int min_element_in_row(const Matrix &m, Column::size_type row) { 
    int min_element = max_col(m)[row];
    for (auto& col : m) {
        if (row >= 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 &m) {
    for (auto& i : m) {
        for (auto& j : i) {
            std::cout << j << " ";
        }
        std::cout << std::endl;
    }
}

void organize_elements(Matrix &m) {
    for (auto& col : m) {
        std::sort(col.begin(),col.end());
    }
    auto current_max_col = max_col(m);
    for (Column::size_type row{0}; current_max_col.begin()+row!=current_max_col.end(); ++row) {
        int min_element = min_element_in_row(m,row);
        for(auto& col : m) {
            if (row >= col.size()) continue; // out of range
            int candidate = col[row];
            if (candidate > min_element) {
                if (is_element_in_next_rows(m,candidate,row)) {
                    col.insert(col.begin()+row,0);
                }
            }
        }
        current_max_col = max_col(m);
    }
}

int main() {

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

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

    std::cout << "original: 
";
    print_elements(m);
    organize_elements(m);
    std::cout << "organized: 
";
    print_elements(m);
    return 0;
}

which outputs the following:

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

including pairs is easy, just change how the compare functions are done for them. I don't know if this is what you meant. It can also be further optimized, this was a quick solution that might serve your needs or inspire you for a better one.