Преобразование массива

[Majestio]

Всем привет!

Пришла моя очередь просить помощи Нужен компактный алгоритм на 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;
}

Если логика преобразований не совсем очевидна - дайте занть, я распишу.

[MBo]

Лучше всё-таки помучиться © тов. Сухов

Можно предположить, что выдаются сортированные префиксы подмассивов, при этом длина - первый ключ сортировки по убыванию, но лучше всё-таки объяснить, что имелось в виду.

[Majestio]

Цитата MBo @ 19.01.24, 03:48

но лучше всё-таки объяснить, что имелось в виду

Хорошо, сделаю вам многобукв ...
Имеется некий многоуровневый рубрикатор.

Пример:

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.

[MBo]

ОК, значит, я верно понял.

Тогда можно создать std::priority_queue, содержащую vector<int>, и написать для очереди функцию сравнения, в которой первичный ключ - длина вектора, а вторичный при равенстве - набор значений.

Закладываем все полные вектора в очередь.
На каждом шаге извлекаем вектор с верхушки очереди, на вывод его, удаляем последний элемент вектора, и если он не пуст - кладём обратно в кучу.

Сообщение отредактировано: MBo - 19.01.24, 04:44

[Majestio]

Цитата MBo @ 19.01.24, 04:43

Тогда можно создать std::priority_queue

Пасип! Никогда это не приходилось использовать - буду почитать

[MBo]

Впрочем, может, это и лишнее. Все префиксы всё равно генерировать надо - так сгенерировать их, сложить в одно место, и отсортировать с тем же компаратором.

[Majestio]

Цитата MBo @ 19.01.24, 07:06

Впрочем, может, это и лишнее. Все префиксы всё равно генерировать надо - так сгенерировать их, сложить в одно место, и отсортировать с тем же компаратором.

Именно. Я, пока ехал домой, тоже об этом подумал. Сначала разворачиваем все префиксы и складываем в кучу. Потом удаляем дубли. Потом сортируем. Да, так будет проще.

[Majestio]

В общем, чтобы вопрос закрыть, опубликую свои реализации только для точечной нотации рубрикатора.

Сперва на 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

Собственно , что и требовалось. За сим вопрос считаю для себя закрытым. Но если кому будет интересно реализовать компактнее - вэлком. Равно как и реализовать алгоритм чисто на векторах, без точечной нотации.

[Qraizer]

Сортировка по длинам строк опасна, для двузначных номеров (под)разделов будет сбоить.

[Majestio]

Цитата Qraizer @ 19.01.24, 12:28

Сортировка по длинам строк опасна, для двузначных номеров (под)разделов будет сбоить.

Я тебя понял. У меня таких нет - но предусмотреть нужно!

[shm]

Описание не осилил, но если подгонять под пример и использовать одни векторы, то как-то так:

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

[Majestio]

Я залетел в больничку, чисто на телефоне некузяво смотреть код. Вернусь - заценю.

[Majestio]

Выписался с больнички с диагнозом "небольшой диабетик 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". Ну а так, да - норм.

[Majestio]

Цитата Qraizer @ 24.01.24, 17:13

От счас ещё пару постов и ей-богу захочется самому пописа́ть. А некогда, дидлаим.

Ну я вроде порешал этот вопрос

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 красивше!

[Qraizer]

Цитата Majestio @ 24.01.24, 22:17

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

Совершенно неоптимизировано. Собрано на коленке. Доводить до ума некогда, сорри.

Добавлено 06.02.24, 18:05
Огромный простор для оптимизации. Особенно в Sorter<>::operator(), где можно закешировать всё, превратив Sorter<> в полноценный прокси. Зато сейчас все вспомогательные сущности иммутабельные, кому-то так больше нравится.

Добавлено 06.02.24, 18:10
Кстати, Majestio, где тест с мульёном вложений подразделов? А то 3 как-то несерьёзно.

Сообщение отредактировано: Qraizer - 06.02.24, 18:10