Несколько столбцов сортировки и arraging алгоритм


Проблема

Цель состоит в том, чтобы выполнить следующие преобразования:

enter image description here

Кроме того, если две строки могут быть объединены, они объединяются в один:

enter image description here

Код

Я написал следующий алгоритм решения этой проблемы:

#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;
}

Которая производит следующий вывод:

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 

Вопросы

Особенно мне не нравится эта часть моего кода:

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);
}

Я также не нравится, что я должен сделать это в ролях:

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

Есть ли способ, чтобы сделать это лучше проверить?

Тот факт, что мне нужно объявить current_max_col из forи обновить его внутри цикла. Любая идея, как этого избежать?

Любые другие идеи о том, как решить эту проблему? Любые другие советы? Спасибо!



212
2
задан 30 января 2018 в 07:01 Источник Поделиться
Комментарии
2 ответа

Я считаю, что вы можете использовать стл лучше алгоритмы. Есть еще слишком много сырых петель в коде...

Я понимаю, почему ты влюбилась std::rotate но это не единственный инструмент в вашем распоряжении.

Например, std::min_element является достаточно гибкой для обработки 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);
}

Кроме того, нет необходимости сравнивать результаты std::lower_bound и std::upper_bound. Вы знаете, что элемент находится в диапазоне если *std::lower_bound(b, e, elem) == elem, потому что он возвращает итератор на первый элемент, равен или больше, чем Элем.

Что сказал, Вот мое предложение (хотя я не обработке комбинаций строк):

#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';
}

}

На выходе получается слегка отличается от вашей, но, кажется, чтобы соответствовать спецификации проблему:

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

1
ответ дан 30 января 2018 в 11:01 Источник Поделиться

Похоже, что преобразование вы после k-путем слияния в маскировке.

В двух словах, создать мин-кучи пар <col_id, vector<int>::iterator>. На каждой итерации построить вектор значений равен куче голову, 0 в противном случае; подтолкнуть ее к полученной матрицы; удалить эти записи из кучи в новых значений из соответствующих столбцов. Извините, если я пропускаю что-то очевидное.

Я не думаю, что вы должны стремиться для преобразования.


Я уверен, что слияние строк заслуживают отдельного прохода.


В

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

ничем не лучше col.insert(col.begin() + row, 0);


В static_cast<int>(col.size()) предполагает, что row не должно быть intно вдоль линии std::vector<int>::size_type.

1
ответ дан 30 января 2018 в 08:01 Источник Поделиться