На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Преобразование массива
    Всем привет!

    Пришла моя очередь просить помощи :) Нужен компактный алгоритм на C++20 не выше, с максимальным задействованием стандартной библиотеки.
    Пока просто приведу пример, что есть и что должно получиться:

    ExpandedWrap disabled
      #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 @
        но лучше всё-таки объяснить, что имелось в виду

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

        Пример:

        1 Топчик
        1.1 Ниже
        1.1.1 Еще ниже
        ...
        3.2 Что-то там
        ...
        3.4 Что-то там еще

        Есть плоская таблица связи элементов с этим рубрикатором.

        Простой вариант - в таблице найдена одна связь 1.1.1. Значит нам нужно из нее (из связи) получить дополнительные связи 1.1 и 1. При этом будем считать самую "глубокую" связь 1.1.1 главной, остальные полученные - дополнительными. Что делать, если изначально имеем привязку не к одному элементу рубрикатора, а к нескольким? Тут придется привязывать как и в первом случае, но находить главную связь уже по своим правилам. А они будут такие:

        1) Все низ лежащие рубрики разворачиваем и дополняем в вектор
        2) Если появляются дубли - оставляем только один из элементов
        3) Производим сортировку по правилам - сперва по "длине" в порядке убывания, среди рубрик равной "длины" в порядке возрастания.

        Первую рубрику в полученном векторе считаем - главной. Остальные ... ну неглавными :lol:

        Ну вот как-то так.

        И да ... в самом начале вектор привязок от дублей изначально очищен. А в рубрикаторе в каждой ветке может быть своя глубина. А в таблице связей с рубрикатором могут быть связи только к самым низ лежащим рубрикам. В примере этого поста - связи к 1.1 или 1 быть не может, только 1.1.1.
          ОК, значит, я верно понял.

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

          Закладываем все полные вектора в очередь.
          На каждом шаге извлекаем вектор с верхушки очереди, на вывод его, удаляем последний элемент вектора, и если он не пуст - кладём обратно в кучу.
          Сообщение отредактировано: MBo -
            Цитата MBo @
            Тогда можно создать std::priority_queue

            Пасип! Никогда это не приходилось использовать - буду почитать :)
              Впрочем, может, это и лишнее. Все префиксы всё равно генерировать надо - так сгенерировать их, сложить в одно место, и отсортировать с тем же компаратором.
                Цитата MBo @
                Впрочем, может, это и лишнее. Все префиксы всё равно генерировать надо - так сгенерировать их, сложить в одно место, и отсортировать с тем же компаратором.

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

                  Сперва на Perl 5 :rolleyes: (https://ideone.com/M9UEve)

                  ExpandedWrap disabled
                    #!/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)

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

                  Вывод будет одинаков:

                  ExpandedWrap disabled
                    1.1.1
                    2.4.5
                    1.1
                    2.4
                    3.4
                    1
                    2
                    3

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

                      Я тебя понял. У меня таких нет - но предусмотреть нужно!
                        Описание не осилил, но если подгонять под пример и использовать одни векторы, то как-то так:
                        ExpandedWrap disabled
                          #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;
                          }
                          Я залетел в больничку, чисто на телефоне некузяво смотреть код. Вернусь - заценю.
                            Выписался с больнички с диагнозом "небольшой диабетик II" (неинсулиновый) :(

                            А по существу вопроса, shm, твой код немного косячит на следующем сетапе:

                            ExpandedWrap disabled
                              const std::vector<std::string> arr = {"1.12.1", "2.4.15", "1.11.1", "33.4"};

                            Выдает:

                            ExpandedWrap disabled
                              1.11.1
                              1.12.1
                              2.4.15
                              1.11
                              1.12
                              2.4
                              33.4
                              1
                              1
                              2
                              33

                            Дубль цифры "1". Ну а так, да - норм.
                              Цитата Qraizer @
                              От счас ещё пару постов и ей-богу захочется самому пописа́ть. А некогда, дидлаим.

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

                              Perl

                              ExpandedWrap disabled
                                #!/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++

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

                              Оба вывода идентичны, и так как мне надо ;)

                              ExpandedWrap disabled
                                2.4.15
                                111.1.1
                                1.1    
                                1.12  
                                2.4    
                                3.4    
                                111.1  
                                1      
                                2      
                                3      
                                111

                              Perl красивше! :lol:
                                Цитата Majestio @
                                Perl красивше!
                                Красивше русский. Особенно нелитературный. А Плюсы круче:
                                ExpandedWrap disabled
                                  #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 как-то несерьёзно.
                                Сообщение отредактировано: Qraizer -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0545 ]   [ 16 queries used ]   [ Generated: 8.11.24, 22:14 GMT ]