Я работаю над алгоритмом сортировки векторов для своих личных исследований физики элементарных частиц, но я очень новичок в кодировании.
Прохождение отдельных сценариев (конкретных размеров векторов и их комбинаций) методом грубой силы становится чрезвычайно хаотичным для большего количества элементов сетевого вектора, тем более что весь этот код будет зацикливаться до 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);
}
Но я не могу конкретизировать это.
Разбейте свою проблему на более мелкие части. Сначала выясните, как создать коллекцию всех комбинаций V+ и V-. Это называется декартовым произведением. Затем объедините декартовы произведения A-xA+ и B-xB+ в единую коллекцию, чтобы получить все жизнеспособные пары. Наконец, вы сортируете или максимизируете эту коллекцию по k, когда вам нужно. Я предлагаю заглянуть в библиотеку range-v3. Он позволяет создавать необходимые коллекции, не сохраняя их в памяти, поэтому он должен работать с относительно большими коллекциями без большой нагрузки на память.
Было бы полезно, если бы вы могли предоставить более подробную информацию: что делает функция k? Можете ли вы привести примеры векторов или функций? Попробуйте предоставить минимальный пример кода на допустимом C++ со всеми необходимыми (но без ненужных) деталями.
Вероятно, вы можете использовать жадный алгоритм для решения этой проблемы. Начните с сортировки векторов в порядке убывания суммы их элементов. Затем соедините в пары первые элементы каждого вектора, затем вторые элементы каждого вектора и так далее.
Если я правильно понял ваш вопрос,
k
, которая отображает два double
s (или 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-) максимизируется [...]
Что меня немного смущает.
Я предлагаю разбить вашу проблему на три подзадачи:
Vplus
и Vminus
. Это часто обозначается как декартово произведение Vplus x Vminus
.aplus x aminus
и bplus x bminus
, чтобы получить диапазон всех жизнеспособных пар в вашем домене.Библиотека 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, у вас есть два варианта:
to_vector(view::transform(pairs_view, to_std_pair))
, concat
и cartesian_product
предположительно будут добавлены в грядущий стандарт C++23.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, все работает отлично. Еще раз спасибо!
k
это функция?