c++ 对向量中的元素对进行排序以最大化函数

fcg9iug3  于 2022-11-27  发布在  其他
关注(0)|答案(2)|浏览(97)

我正在为我个人的粒子物理研究做一个矢量排序算法,但我对编码非常陌生。
对于更大数量的网络矢量元素,通过蛮力遍历单个场景(特定矢量大小和组合)会变得非常混乱,特别是因为整个代码将循环多达1 e5次。
取“风味”A和B的四个向量:A+、A-、B+和B-。我需要找到总共两对元素,使得某个值k(V+,V-)在不同风味不能组合的限制下最大化!(V只是风味占位符)
例如:
A+ = {a1+} A- = {a1-}
B+ = {b1+,b2+} B- = {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-组合中的两个具有比A+A-更大的k。这也将是有效的!
任何帮助都将不胜感激!!!我可以澄清,如果上面的任何东西是过于混乱!
我试过这样的方法,

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

但我不能具体描述。

ttvkxqim

ttvkxqim1#

如果我没理解错你的问题,

  • 你有一个函数k,它将两个double(或一个std::pair<double, double> Map到一个double。* 我假设是double,这在问题中并不清楚,严格来说,它也不是问题的核心。*
  • 您有四个std::vector<double>:第一个元素是aplus,第二个元素是aminus,第三个元素是bplus和第四个元素是bminus
  • 你的域是所有std::pair<double, double>,你可以通过组合aplusaminus中的元素以及分别来自bplusbminus的所有组合来形成。
  • 您可以选择
  • 在您的域中找到使k最大化的对
  • 获取域中所有对的集合,按k的值排序

我说的对吗?你在问题里说
我需要找到两个总对的元素,使某个值k(V+,V-)最大化[...]
这让我有点困惑。
我的建议是把你的问题分解成三个子任务:
1.创建向量VplusVminus中元素的所有组合的范围,通常表示为笛卡尔积Vplus x Vminus
1.连接步骤1中为aplus x aminusbplus x bminus创建的范围,以获得域中所有可行对的范围。
1.最大化/排序步骤2中的范围。

使用范围-v3实现

range-v3库为这类任务提供了一些非常方便的工具。

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

查找最大元素

让我们先定义一个方便函数 (这里是lambda expression的形式),该函数计算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值最大的元素,其中我们要将投影值与标准less函数进行比较。"

获取域的排序范围

如果你想在你的域中拥有所有对的排序范围,我们必须先为你的域创建一个std::vector<std::pair<double, double>>,然后再排序它。你不能对用range-v3库创建的视图进行排序,因为它们只是一个现有对象的视图,它们不能被改变。另外,我们必须将cartesian_product函数中的range-v3库创建的特殊对类型Map到实际的std::pair<double, double,以便将值复制到新容器中:

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;

注意,“管道”运算符|是函数组合to_vector(view::transform(pairs_view, to_std_pair))的简写。
排序算法的调用与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库的大部分已经被添加到C20的标准库中。相关函数concatcartesian_productto_vector可能会被添加到即将到来的标准C23中。
1.标准库有max_elementsort,所以你可以自己实现级联和笛卡尔积:https://godbolt.org/z/7Y5dG16WK

wqnecbli

wqnecbli2#

谢谢每一个评论的人!!!我真的很感谢你的努力。解决方案最终比我想象的要简单得多。
从本质上讲,从我使用的物理程序,粒子是以列表的形式给出的(即533 e-,534 p+,535 e+等)。我不知道如何让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值,它的工作刚刚好。再次感谢!

相关问题