Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.239.87.20] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем привет!
Пришла моя очередь просить помощи Нужен компактный алгоритм на C++20 не выше, с максимальным задействованием стандартной библиотеки. Пока просто приведу пример, что есть и что должно получиться: #include <vector> #include <string> using Vint = std::vector<int>; using Bolt = std::vector<Vint>; using Wood = std::vector<std::string>; int main() { Bolt raw = { {4,6}, {5,2}, {4,7,1}, {3,2,1}, {2,2} }; // тут ваше супер-преобразование-1 и нужный результат // Bolt wet = { {3,2,1}, {4,7,1}, {2,2}, {3,2}, {4,6}, {4,7}, {5,2}, {2}, {3}, {4}, {5} }; Wood dirty = { "4.6", "5.2", "4.7.1", "3.2.1", "2.2" }; // тут ваше супер-преобразование-2 и нужный результат // Wood pure = { "3.2.1", "4.7.1", "2.2", "3.2", "4.6", "4.7", "5.2", "2", "3", "4", "5" }; return 0; } Если логика преобразований не совсем очевидна - дайте занть, я распишу. |
Сообщ.
#2
,
|
|
|
Лучше всё-таки помучиться © тов. Сухов
Можно предположить, что выдаются сортированные префиксы подмассивов, при этом длина - первый ключ сортировки по убыванию, но лучше всё-таки объяснить, что имелось в виду. |
Сообщ.
#3
,
|
|
|
Цитата MBo @ но лучше всё-таки объяснить, что имелось в виду Хорошо, сделаю вам многобукв ... Имеется некий многоуровневый рубрикатор. Пример: 1 Топчик 1.1 Ниже 1.1.1 Еще ниже ... 3.2 Что-то там ... 3.4 Что-то там еще Есть плоская таблица связи элементов с этим рубрикатором. Простой вариант - в таблице найдена одна связь 1.1.1. Значит нам нужно из нее (из связи) получить дополнительные связи 1.1 и 1. При этом будем считать самую "глубокую" связь 1.1.1 главной, остальные полученные - дополнительными. Что делать, если изначально имеем привязку не к одному элементу рубрикатора, а к нескольким? Тут придется привязывать как и в первом случае, но находить главную связь уже по своим правилам. А они будут такие: 1) Все низ лежащие рубрики разворачиваем и дополняем в вектор 2) Если появляются дубли - оставляем только один из элементов 3) Производим сортировку по правилам - сперва по "длине" в порядке убывания, среди рубрик равной "длины" в порядке возрастания. Первую рубрику в полученном векторе считаем - главной. Остальные ... ну неглавными Ну вот как-то так. И да ... в самом начале вектор привязок от дублей изначально очищен. А в рубрикаторе в каждой ветке может быть своя глубина. А в таблице связей с рубрикатором могут быть связи только к самым низ лежащим рубрикам. В примере этого поста - связи к 1.1 или 1 быть не может, только 1.1.1. |
Сообщ.
#4
,
|
|
|
ОК, значит, я верно понял.
Тогда можно создать std::priority_queue, содержащую vector<int>, и написать для очереди функцию сравнения, в которой первичный ключ - длина вектора, а вторичный при равенстве - набор значений. Закладываем все полные вектора в очередь. На каждом шаге извлекаем вектор с верхушки очереди, на вывод его, удаляем последний элемент вектора, и если он не пуст - кладём обратно в кучу. |
Сообщ.
#5
,
|
|
|
Цитата MBo @ Тогда можно создать std::priority_queue Пасип! Никогда это не приходилось использовать - буду почитать |
Сообщ.
#6
,
|
|
|
Впрочем, может, это и лишнее. Все префиксы всё равно генерировать надо - так сгенерировать их, сложить в одно место, и отсортировать с тем же компаратором.
|
Сообщ.
#7
,
|
|
|
Цитата MBo @ Впрочем, может, это и лишнее. Все префиксы всё равно генерировать надо - так сгенерировать их, сложить в одно место, и отсортировать с тем же компаратором. Именно. Я, пока ехал домой, тоже об этом подумал. Сначала разворачиваем все префиксы и складываем в кучу. Потом удаляем дубли. Потом сортируем. Да, так будет проще. |
Сообщ.
#8
,
|
|
|
В общем, чтобы вопрос закрыть, опубликую свои реализации только для точечной нотации рубрикатора.
Сперва на Perl 5 (https://ideone.com/M9UEve) #!/usr/bin/perl use strict; use warnings; use v5.24; my @Arr = ('1.1', '2.4.5', '1.1.1', '3.4'); my %Tmp = (); foreach my $i (@Arr) { $Tmp{$i} = '*'; my $j = $i; while ($j =~ /^(.+).\d/) { $j = $1; $Tmp{$j} = '*'; } } my @Res = sort {return (length($a) == length($b)) ? $a cmp $b : length($b) <=> length($a)} keys %Tmp; map {say $_ } @Res; Потом это же на C++ (https://ideone.com/96ifZV) #include <iostream> #include <vector> #include <map> #include <regex> #include <algorithm> int main() { std::vector<std::string> Arr = {"1.1", "2.4.5", "1.1.1", "3.4"}; std::map<std::string, std::string> Tmp; std::regex re(R"((.+?)\.\d)"); std::smatch match; for (const auto& i : Arr) { Tmp[i] = "*"; std::string j = i; while (std::regex_search(j, match, re)) { j = match.str(1); Tmp[j] = "*"; } } std::vector<std::string> Res; for (const auto& pair : Tmp) { Res.push_back(pair.first); } std::sort(Res.begin(), Res.end(), [](const std::string& a, const std::string& b) { return (a.length() == b.length()) ? a < b : a.length() > b.length(); }); for (const auto& item : Res) { std::cout << item << std::endl; } return 0; } Вывод будет одинаков: 1.1.1 2.4.5 1.1 2.4 3.4 1 2 3 Собственно , что и требовалось. За сим вопрос считаю для себя закрытым. Но если кому будет интересно реализовать компактнее - вэлком. Равно как и реализовать алгоритм чисто на векторах, без точечной нотации. |
Сообщ.
#9
,
|
|
|
Сортировка по длинам строк опасна, для двузначных номеров (под)разделов будет сбоить.
|
Сообщ.
#10
,
|
|
|
Цитата Qraizer @ Сортировка по длинам строк опасна, для двузначных номеров (под)разделов будет сбоить. Я тебя понял. У меня таких нет - но предусмотреть нужно! |
Сообщ.
#11
,
|
|
|
Описание не осилил, но если подгонять под пример и использовать одни векторы, то как-то так:
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <unordered_set> int main() { const std::vector<std::string> arr = {"1.1", "2.4.5", "1.1.1", "3.4"}; std::vector<std::vector<int>> int_arr; std::vector<std::vector<int>> int_out_arr; std::vector<std::string> out_arr; for (const std::string& s : arr) { std::vector<int> x; size_t i = 0; for ( ; ; ) { const size_t j = s.find('.', i); x.emplace_back(std::stoi(s.substr(i, j != std::string::npos ? (j - i) : j))); if (j == std::string::npos) break; i = j + 1; } int_arr.emplace_back(std::move(x)); } std::sort(int_arr.begin(), int_arr.end()); for (size_t i = 0; i < int_arr.size(); ++i) { size_t len = int_arr[i].size(); if (i != 0 && std::equal(int_arr[i - 1].begin(), int_arr[i - 1].end(), int_arr[i].begin())) len -= int_arr[i - 1].size(); while (len-- > 1) int_out_arr.emplace_back(std::vector<int>(int_arr[i].begin(), int_arr[i].begin() + len)); int_out_arr.emplace_back(int_arr[i]); } std::sort(int_out_arr.begin(), int_out_arr.end(), [](const std::vector<int>&a, const std::vector<int>&b){ if (a.size() == b.size()) return a < b; return a.size() > b.size(); }); for (const std::vector<int>& line : int_out_arr) { std::string s; for (int value : line) { if (!s.empty()) s += '.'; s += std::to_string(value); } out_arr.emplace_back(std::move(s)); } for (const std::string& s : out_arr) std::cout << s << std::endl; return 0; } |
Сообщ.
#12
,
|
|
|
Я залетел в больничку, чисто на телефоне некузяво смотреть код. Вернусь - заценю.
|
Сообщ.
#13
,
|
|
|
Выписался с больнички с диагнозом "небольшой диабетик II" (неинсулиновый)
А по существу вопроса, shm, твой код немного косячит на следующем сетапе: const std::vector<std::string> arr = {"1.12.1", "2.4.15", "1.11.1", "33.4"}; Выдает: 1.11.1 1.12.1 2.4.15 1.11 1.12 2.4 33.4 1 1 2 33 Дубль цифры "1". Ну а так, да - норм. |
Сообщ.
#14
,
|
|
|
Ну я вроде порешал этот вопрос Perl #!/usr/bin/perl use strict; use warnings; use v5.24; my @Arr = ('1.12', '2.4.15', '111.1.1', '3.4', '1.1'); my @Res = (); # если задан массив в "точечной нотации" преобразуем в массив массивов my @Tmp = map {[split /\./]} @Arr; # обработка ExpandSubsections(\@Tmp, \@Res); # печать результата map {say join('.', @{$_})} @Res; # ------------------------------------------ sub ExpandSubsections { my ($Tmp, $Res) = @_; my %Seen; foreach my $i (@{$Tmp}) { do { my @Items = @{$i}; my $Key = join(".", @Items); unless (exists $Seen{$Key}) { $Seen{$Key} = "*"; push @{$Res}, [@Items]; } pop @{$i}; } while (scalar(@{$i})); } @{$Res} = sort { return 1 if (@$b > @$a); return -1 if (@$b < @$a); for my $i (0 .. @$a - 1) { return -1 if ($a->[$i] < $b->[$i]); return 1 if ($a->[$i] > $b->[$i]); } return 0; } @{$Res}; } C++ #include <iostream> #include <algorithm> #include <vector> #include <sstream> #include <iterator> #include <unordered_map> void ExpandSubsections(std::vector<std::vector<unsigned>>& tmp, std::vector<std::vector<unsigned>>& res) { std::unordered_map<std::string, bool> seen; for (const auto& i : tmp) { std::vector<unsigned> items = i; do { std::stringstream key; std::copy(items.begin(), items.end(), std::ostream_iterator<unsigned>(key, ".")); std::string val = key.str(); if (seen.find(val) == seen.end()) { res.push_back(items); seen[val] = true; } items.pop_back(); } while (!items.empty()); } std::sort(res.begin(), res.end(), [](const std::vector<unsigned>& a, const std::vector<unsigned>& b) { if (a.size() != b.size()) return a.size() > b.size(); for (size_t i = 0; i < a.size(); ++i) { if (a[i] != b[i]) return a[i] < b[i]; } return false; }); } int main() { std::vector<std::string> arr = {"1.12", "2.4.15", "111.1.1", "3.4", "1.1"}; std::vector<std::vector<unsigned>> res; // если задан массив в "точечной нотации" преобразуем в массив массивов std::vector<std::vector<unsigned>> tmp; for (const auto& str : arr) { std::vector<unsigned> subsection; std::stringstream ss(str); std::string el; while (std::getline(ss, el, '.')) subsection.push_back(std::stoul(el)); tmp.push_back(subsection); } // обработка ExpandSubsections(tmp, res); // печать результата for (const auto& subsection : res) { for (size_t i = 0; i < subsection.size(); ++i) { std::cout << subsection[i]; if (i != subsection.size() - 1) std::cout << "."; } std::cout << std::endl; } std::cout << std::endl; return 0; } Оба вывода идентичны, и так как мне надо 2.4.15 111.1.1 1.1 1.12 2.4 3.4 111.1 1 2 3 111 Perl красивше! |
Сообщ.
#15
,
|
|
|
Цитата Majestio @ Красивше русский. Особенно нелитературный. А Плюсы круче:Perl красивше! #include <iostream> #include <vector> #include <string> #include <algorithm> #include <tuple> #include <set> // стратегия для векторов struct VectorAccessor { using value_type = std::vector<int>; static size_t getSize(const value_type& cont) { return cont.size(); } static int getItem(const value_type& cont, size_t idx) { return cont.at(idx); } static void addItem( value_type& cont, int val) { cont.push_back(val); } }; // стратегия для строк struct StringAccessor { using value_type = std::string; static size_t getSize(const value_type& cont) { return std::count(cont.begin(), cont.end(), '.') + 1; // количество определяется точками } static int getItem(const value_type& cont, size_t idx) { auto getPosPoint =[&](size_t idx) -> std::string::size_type // ищем точку с номером idx { // условно номер 0 - это начало строки std::string::size_type pos = 0; for (size_t i = 0; i < idx; ++i) pos = cont.find('.', pos + 1); return pos; }; auto getPos = [&](size_t idx) // ищем границы целого с номером idx { std::string::size_type posL = getPosPoint(idx); std::string::size_type posR = cont.find('.', posL + 1); return std::make_tuple(posL, posR); }; auto [pos1, pos2] = getPos(idx); // получаем границы целого return std::stoul(cont.substr(pos1 == 0 ? 0 : pos1 + 1, pos2 - pos1)); // получаем целое } static void addItem(value_type& cont, int val) { cont += (cont.empty() ? "" : ".") + std::to_string(val); // точка впереди не нужна } }; // селектор политик template <typename T> struct Selector; template <> struct Selector<std::vector<int>> { using ValueType = VectorAccessor; }; template <> struct Selector<std::string> { using ValueType = StringAccessor; }; // это не моё using Vint = std::vector<int>; using Bolt = std::vector<Vint>; using Wood = std::vector<std::string>; Bolt raw = { {4,6}, {5,2}, {4,7,1}, {3,2,1}, {2,2} }; Wood dirty = { "4.6", "5.2", "4.7.1", "3.2.1", "2.2" }; // а это опять моё // Сравняльщик. Шаблонной лямбдой больно муторно template <typename T> struct Sorter { using selector = typename Selector<typename T::value_type>::ValueType; // политика // если длины разные, то меньше тот, кто длинее; // иначе меньше тот, чей int с наименьшим номером меньше, пока предыдущие int равны bool operator()(const typename selector::value_type& left, const typename selector::value_type& right) const { bool res = selector::getSize(left) != selector::getSize(right); // сравнить длины if (res) return selector::getSize(left) > selector::getSize(right); // не равны. for (size_t i = 0; i < selector::getSize(left); ++i) // иначе сравниваем int if (selector::getItem(left, i) != selector::getItem(right, i)) // по порядку, пока равны. return selector::getItem(left, i) < selector::getItem(right, i);// меньший int меньше return false; } }; // получить результат из source template <typename T> auto doTest(const T& source) { std::multiset<typename T::value_type, Sorter<T>> heap(source.begin(), source.end()); // сортируем std::set <typename T::value_type, Sorter<T>> product; using selector_type = decltype(heap)::key_compare::selector; // селектор // просто копируем source в результат поэлементно, попутно добавляем все подэлементы элемента // с меньшими длинами for (const auto& i : heap) { size_t j = selector_type::getSize(i); // длина текущего элемента product.insert(i); // добавить элемент while (--j != 0) // перебрать подэлементы { // конечно выгоднее удалять последний, decltype(product)::value_type newItem; // чем добавлять все, кроме последнего // но лень переписывать политики for (size_t k = 0; k < j; ++k) // добавить все, кроме последнего selector_type::addItem(newItem, selector_type::getItem(i, k)); product.insert(newItem); // добавить в результат } } return product; } // протестировать вектор векторов void testBold() { const auto& product = doTest(raw); // вывод for (const auto& i : product) { std::cout << '{'; for (const auto& j : i) std::cout << ' ' << j << ' '; std::cout << "};"; } std::cout << std::endl; } // протестировать вектор строк void testWood() { const auto& product = doTest(dirty); // вывод std::cout << '{'; for (const auto& i : product) std::cout << ' ' << i << ' '; std::cout << "};"; std::cout << std::endl; } int main() { testBold(); testWood(); dirty = {"1.12.1", "2.4.15", "1.11.1", "33.4"}; // и это тоже не моё testWood(); dirty = {"1.12", "2.4.15", "111.1.1", "3.4", "1.1"}; // ну вы поняли testWood(); } Добавлено Огромный простор для оптимизации. Особенно в Sorter<>::operator(), где можно закешировать всё, превратив Sorter<> в полноценный прокси. Зато сейчас все вспомогательные сущности иммутабельные, кому-то так больше нравится. Добавлено Кстати, Majestio, где тест с мульёном вложений подразделов? А то 3 как-то несерьёзно. |