Сортировка пар элементов из векторов для максимизации функции

Я работаю над алгоритмом сортировки векторов для своих личных исследований физики элементарных частиц, но я очень новичок в кодировании.

Прохождение отдельных сценариев (конкретных размеров векторов и их комбинаций) методом грубой силы становится чрезвычайно хаотичным для большего количества элементов сетевого вектора, тем более что весь этот код будет зацикливаться до 1e5 раз.

Возьмем четыре вектора «ароматов» A и B: A+, A-, B+ и B-. Мне нужно найти две полные пары элементов, такие, что некоторое значение k(V+, V-) максимизируется с ограничением, что разные вкусы не могут быть объединены! (V — это просто заполнитель вкуса)

Например:

А+ = {а1+} А- = {а1-}

В+ = {b1+, b2+} В- = {b1-}

Поскольку A+ и A- содержат только по одному элементу, значение k(A+, A-) -> k(a1+, a1-). Но для аромата B есть две возможные комбинации.

K(b1+, b1-) ИЛИ k(b2+, b1-)

Я хотел бы убедиться, что комбинация элементов с большим значением k сохраняется. Как я уже говорил ранее, этот конкретный пример не СЛИШКОМ плох с точки зрения грубой силы, но, скажем, B+ и B- содержат по два элемента? Возможные значения:

K(b1+, b1-) или k(b2+,b2-) или k(b1+, b2-) или k(b2+, b1-)

Где только один из них правильный. Более того, предположим, что у двух из этих четырех комбинаций B+B- k больше, чем у A+A-. Это тоже будет справедливо!

Любая помощь будет оценена!!! Я могу уточнить, если что-то выше слишком запутанно!

Я пробовал что-то вроде этого,

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

using namespace std;

static bool sortbypair(const pair<double, double> &a, const pair<double, double> &b)
{
    return (k(a.first, a.second) > k(b.first, b.second)) && k(a.first, b.second) < k(a.second, b.first);
}

Но я не могу конкретизировать это.

k это функция?
Giogre 20.11.2022 22:38

Разбейте свою проблему на более мелкие части. Сначала выясните, как создать коллекцию всех комбинаций V+ и V-. Это называется декартовым произведением. Затем объедините декартовы произведения A-xA+ и B-xB+ в единую коллекцию, чтобы получить все жизнеспособные пары. Наконец, вы сортируете или максимизируете эту коллекцию по k, когда вам нужно. Я предлагаю заглянуть в библиотеку range-v3. Он позволяет создавать необходимые коллекции, не сохраняя их в памяти, поэтому он должен работать с относительно большими коллекциями без большой нагрузки на память.

joergbrech 20.11.2022 22:54

Было бы полезно, если бы вы могли предоставить более подробную информацию: что делает функция k? Можете ли вы привести примеры векторов или функций? Попробуйте предоставить минимальный пример кода на допустимом C++ со всеми необходимыми (но без ненужных) деталями.

joergbrech 20.11.2022 23:00

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

Igor 20.11.2022 23:29
Как настроить Tailwind CSS с React.js и Next.js?
Как настроить Tailwind CSS с React.js и Next.js?
Tailwind CSS - единственный фреймворк, который, как я убедился, масштабируется в больших командах. Он легко настраивается, адаптируется к любому...
LeetCode запись решения 2536. Увеличение подматриц на единицу
LeetCode запись решения 2536. Увеличение подматриц на единицу
Увеличение подматриц на единицу - LeetCode
Переключение светлых/темных тем
Переключение светлых/темных тем
В Microsoft Training - Guided Project - Build a simple website with web pages, CSS files and JavaScript files, мы объясняем, как CSS можно...
Отношения &quot;многие ко многим&quot; в Laravel с методами присоединения и отсоединения
Отношения &quot;многие ко многим&quot; в Laravel с методами присоединения и отсоединения
Отношения "многие ко многим" в Laravel могут быть немного сложными, но с помощью Eloquent ORM и его моделей мы можем сделать это с легкостью. В этой...
В PHP
В PHP
В большой кодовой базе с множеством различных компонентов классы, функции и константы могут иметь одинаковые имена. Это может привести к путанице и...
Карта дорог Беладжар PHP Laravel
Карта дорог Беладжар PHP Laravel
Laravel - это PHP-фреймворк, разработанный для облегчения разработки веб-приложений. Laravel предоставляет различные функции, упрощающие разработку...
2
4
60
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Если я правильно понял ваш вопрос,

  • у вас есть функция k, которая отображает два doubles (или std::pair<double, double>) в один double. Я предполагаю double, это не было ясно из вопроса. Это также не строго в основе вашей проблемы.
  • у вас есть четыре std::vector<double>: aplus, aminus, bplus и bminus.
  • Ваш домен — это все std::pair<double, double>, которые вы можете сформировать, комбинируя элементы в aplus и aminus, а также все комбинации из bplus и bminus соответственно.
  • ты хочешь либо
    • найдите пару в своем домене, которая максимизирует k
    • получить коллекцию всех пар в вашем домене, отсортированных по значению k

Я правильно понял? Вы указываете в своем вопросе

Мне нужно найти две полные пары элементов, такие что некоторое значение k(V+, V-) максимизируется [...]

Что меня немного смущает.


Я предлагаю разбить вашу проблему на три подзадачи:

  1. Создайте диапазон всех комбинаций элементов в векторах Vplus и Vminus. Это часто обозначается как декартово произведение Vplus x Vminus.
  2. Объедините диапазоны, созданные на шаге 1, для aplus x aminus и bplus x bminus, чтобы получить диапазон всех жизнеспособных пар в вашем домене.
  3. Развернуть/отсортировать диапазон из шага 2.

Реализация с использованием range-v3

Библиотека range-v3 предоставляет несколько очень удобных инструментов для такого рода задач. Предположим, что ваша функция k выглядит так:

double k(double x, double y) { return x*x + y*y; }

И ваши векторы выглядят так:

std::vector<double> ap{0., 4., 2., 3., 1.};
std::vector<double> am{2., -1.};

std::vector<double> bp{1., 0.5};
std::vector<double> bm{-1., 2.};

Давайте определим диапазон, представляющий наш домен:

using namespace ranges;

auto pairs_view = view::concat(
    view::cartesian_product(ap, am),
    view::cartesian_product(bp, bm)
);

Экземпляр pairs_view на самом деле не создает пары где-либо в памяти. Это просто объект-адаптер, который позволяет перебирать все пары, которые можно построить указанным способом. Пары создаются «лениво» на лету, когда вы или алгоритм повторяете их.

Выведем все пары из нашего домена:

auto print = [](auto const& p){
    auto first = std::get<0>(p);
    auto second = std::get<1>(p);
    std::cout << "[" << first << ", " << second << "] k = " << k(first, second) << std::endl;
};

for_each(pairs_view, print);

Вывод:

[0, 2] k = 4
[0, -1] k = 1
[4, 2] k = 20
[4, -1] k = 17
[2, 2] k = 8
[2, -1] k = 5
[3, 2] k = 13
[3, -1] k = 10
[1, 2] k = 5
[1, -1] k = 2
[1, -1] k = 2
[1, 2] k = 5
[0.5, -1] k = 1.25
[0.5, 2] k = 4.25

Нахождение максимального элемента

Начнем с определения функции удобства (здесь в форме лямбда-выражения), которая вычисляет k для кортежа двойников:

auto k_proj = [](auto const& p){
    return k(std::get<0>(p), std::get<1>(p));
};

Вы можете найти итератор для пары в своем домене, который максимизирует k всего одной строкой:

auto it = max_element(pairs_view, less{}, k_proj);
print(*it);

Вывод:

[4, 2] k = 20

Функция max_element получает два дополнительных аргумента. Первая — это функция сравнения, которая возвращает true, если два элемента находятся в порядке. Мы предоставляем функтор less по умолчанию. Второй аргумент — необязательная проекция, которая должна применяться к каждому элементу перед сравнением. Проходим k_proj.

Прочитайте приведенную выше строку кода как «Найдите элемент, в котором проекция на его значение pairs_view максимальна, где мы хотим сравнить проецируемые значения со стандартной функцией меньше».

Получение отсортированного диапазона вашего домена

Если вы хотите иметь весь отсортированный диапазон всех пар в вашем домене, мы должны сначала создать k для вашего домена, а затем отсортировать его. Вы не можете сортировать представления, созданные с помощью библиотеки range-v3, потому что они являются просто представлением существующих объектов, их нельзя изменить. Кроме того, мы должны сопоставить специальные типы пар, созданные библиотекой range-v3 в функциях std::vector<std::pair<double, double>>, с фактическими cartesian_product, чтобы скопировать значения в наш новый контейнер:

auto to_std_pair = [](auto const& p){
    return std::pair<double, double>{std::get<0>(p), std::get<1>(p)};
};
auto pairs_vec = pairs_view | view::transform(to_std_pair) | to_vector;

Обратите внимание, что оператор «конвейер» std::pair<double, double является сокращенным обозначением композиции функций |.

Вызов алгоритма сортировки очень похож на вызов алгоритма max_element:

sort(pairs_vec, less{}, k_proj);

Распечатаем результат:

for_each(pairs_vec, print);

Вывод:

[0, -1] k = 1
[0.5, -1] k = 1.25
[1, -1] k = 2
[1, -1] k = 2
[0, 2] k = 4
[0.5, 2] k = 4.25
[2, -1] k = 5
[1, 2] k = 5
[1, 2] k = 5
[2, 2] k = 8
[3, -1] k = 10
[3, 2] k = 13
[4, -1] k = 17
[4, 2] k = 20

Вот полный пример живого кода: https://godbolt.org/z/6zo8oj3ah

Если вы не хотите использовать библиотеку range-v3, у вас есть два варианта:

  1. Ты можешь подождать. Большие части библиотеки range-v3 были добавлены в стандартную библиотеку C++20. Соответствующие функции to_vector(view::transform(pairs_view, to_std_pair)), concat и cartesian_product предположительно будут добавлены в грядущий стандарт C++23.
  2. В стандартной библиотеке есть to_vector и max_element. Таким образом, вы можете просто реализовать конкатенацию и декартово произведение самостоятельно: https://godbolt.org/z/7Y5dG16WK
Ответ принят как подходящий

Спасибо всем, кто прокомментировал!!! Я очень ценю ваши усилия. Решение оказалось намного проще, чем я думал.

По сути, в физической программе, которую я использую, частицы представлены в виде списка (т.е. 533 e-, 534 р+, 535 е+ и др.). Я не мог понять, как заставить работать range-v3 (или любые внешние библиотеки, если на то пошло, но спасибо за предложение), поэтому я решил создать кортеж из индексов объединенных частиц и связанного с ними значения k.

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

using namespace std;

static bool weirdsort(const tuple<int, int, double> &a, const tuple<int, int, double> &b)
{
    return get<2>(a) > get<2>(b);
}

int main()
{
    vector<tuple<int, int, double>> net;
// Sample ptcl list
// 
//      A+    A-    B+    B-
// 0    a1+      
// 1          a1-
// 2                      b1-
// 3                b1+
// 4    a2+
// 5          a2-
    
     
    for(int i = 0; i < A+.size(); i++)
    {
        for (int j = 0; j < A-.size(); j++)
        {
            net.push_back(A+[i], A-[j], k(A+[i], A-[j]));
        }
    }
    sort(net.begin(), net.end(), weirdsort);
    //Now another for loop that erases a tuple (with a lower k value) if it has a repeated ptcl index.
    for (int i = 0; i < net.size(); i++)
    {
        if (get<0>(net[i]) == get<0>(net[i + 1]) || get<1>(net[i]) == get<1>(net[i + 1]))
        {
            net.erase(net.begin() + i + 1);
        }
    }
    //Now can plot third tuple element of net[0] and net[1]

    return 0;
}

Это не совсем идеально, но поскольку я ищу только первые два самых высоких значения k, все работает отлично. Еще раз спасибо!

Другие вопросы по теме