I am working on a vector sorting algorithm for my personal particle physics studies but I am very new to coding.
Going through individual scenarios (specific vector sizes and combinations) by brute force becomes extremely chaotic for greater numbers of net vector elements, especially since this whole code will be looped up to 1e5 times.
Take four vectors of 'flavors' A and B: A , A-, B , and B-. I need to find two total pairs of elements such that some value k(V , V-) is maximized with the restriction that different flavors cannot be combined! (V is just a flavor placeholder)
For example:
A = {a1 } A- = {a1-}
B = {b1 , b2 } B- = {b1-}
Since A and A- only have one element each, the value k(A , A-) -> k(a1 , a1-). But for flavor B, there are two possible combinations.
k(b1 , b1-) OR k(b2 , b1-)
I would like to ensure that the combination of elements with the greater value of k is retained. As I said previously, this specific example is not TOO bad by brute force, but say B and B- had two elements each? The possible values would be:
k(b1 , b1-) or k(b2 ,b2-) or k(b1 , b2-) or k(b2 , b1-)
where only one of these is correct. Furthermore, say two of those four B B- combinations had greater k than that of A A-. This would also be valid!
Any help would be appreciated!!! I can clarify if anything above is overly confusing!
I tried something like this,
#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);
}
But I can't flesh it out.
CodePudding user response：
If I understand your question correctly,
- you have a function
kwhich maps twodoubles (or astd::pair<double, double>) to a singledouble. I am assumingdouble, it wasn't clear from the question. It also isn't strictly at the core of your problem. - you have four
std::vector<double>s:aplus,aminus,bplusandbminus. - Your domain are all
std::pair<double, double>s that you can form by combining the elements inaplusandaminusas well as all combinations frombplusandbminusrespectively. - you want to either
- find the pair in your domain that maximizes
k - get a collection of all pairs in your domain, sorted by the value of
k
- find the pair in your domain that maximizes
Did I get this right? You state in your question
I need to find two total pairs of elements such that some value k(V , V-) is maximized [...]
which confuses me a bit.
My suggestion is to break down your problem into three subtasks:
- Create a range of all combinations of elements in the vectors
VplusandVminus. This is often denoted as a cartesian productVplus x Vminus. - Concatenate the ranges created in step 1 for
aplus x aminusandbplus x bminusto get a range of all viable pairs in your domain. - Maximize/sort the range from step 2.
Implementation using range-v3
The range-v3 library provides some very convenient tools for this kind of task. Let's assume your k function looks like this:
double k(double x, double y) { return x*x y*y; }
and your vectors look like this:
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.};
Let's define a range representing our domain:
using namespace ranges;
auto pairs_view = view::concat(
view::cartesian_product(ap, am),
view::cartesian_product(bp, bm)
);
The pairs_view instance doesn't actually create the pairs anywhere in memory. It is just an adaptor object that let's you iterate over all pairs that you can construct in the specified way. The pairs are created "lazily" on the fly as you - or an algorithm - iterates over it.
Let's print all pairs from our domain:
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);
Output:
[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
Finding the maximum element
Let's start by defining a convenience function (here, in the form of a lambda expression) that evaluates k for a tuple of doubles:
auto k_proj = [](auto const& p){
return k(std::get<0>(p), std::get<1>(p));
};
You can find an iterator to the pair in your domain that maximizes k with just the single line:
auto it = max_element(pairs_view, less{}, k_proj);
print(*it);
Output:
[4, 2] k = 20
The function max_element gets two additional arguments. The first is a comparison function that returns true, if two elements are in order. We provide the default less functor. The second argument is an optional projection that is to be applied on each element before the comparison. We pass k_proj.
Read the above line of code as "Find the element in pairs_view of which the projection onto its k value is maximal, where we want to compare the projected values with the standard less function."
Getting a sorted range of your domain
If you want to have all sorted range of all pairs in your domain, we must create an std::vector<std::pair<double, double>> for your domain first and then sort it. You cannot sort views created with the range-v3 library, because they are just a view into existing objects, they cannot be mutated. In addition, we have to map the special pair types created by the range-v3 library in the cartesian_product functions to actual std::pair<double, double to copy the values into our new container:
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;
Note that the "pipe" operator | is short-hand notation for the function composition to_vector(view::transform(pairs_view, to_std_pair)).
The invokation of the sorting algorithm looks very similar to the invokation of the max_element algorithm:
sort(pairs_vec, less{}, k_proj);
Let's print the result:
for_each(pairs_vec, print);
Output:
[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
Here is a complete live code example: https://godbolt.org/z/6zo8oj3ah
If you don't want to use the range-v3 library you have two options:
- You can wait. Large parts of the range-v3 library have been added to the standard library in C 20. The relevant functions
concat,cartesian_productandto_vectorwill presumably be added in the upcoming standard C 23. - The standard library has
max_elementandsort. So you could just implement the concatenation and cartesian product on your own: https://godbolt.org/z/7Y5dG16WK
CodePudding user response：
Thank you to everyone who commented!!! I really appreciate your effort. The solution ended up being much simpler than I was making it out to be.
Essentially, from the physics program I'm using, the particles are given in a listed form (ie. 533 e-, 534 p , 535 e , etc.). I couldn't figure out how to get range-v3 working (or any external libraries for that matter but thank you for the suggestion) so I figured out to make a tuple out of the indices of combined particles and their associated k value.
#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;
}
It's not quite perfect but since I'm only looking for the first two highest k values it works out just fine. Thanks again!