arrays - 如何在 Matlab 中检查数组中 P 元素的所有组合与总 N 元素？

Question

请问如何在Matlab中检查一个共N个元素的数组中P个元素的所有组合可能性？我现在正尝试使用包含 N 个元素的数组中的 P 元素，比方说数组 A，以在另一个程序中进行测试。如果这组P元素在程序中失败了，我就回到数组A，尝试另一组P元素。所以每次程序只会测试一组P。如果程序成功处理了P个元素，程序将停止并返回TURE，否则继续测试直到所有情况都测试完。

我目前的解决方案是:每次迭代我总是取数组 A 中的前 P 个元素。如果这次失败了，那么我开始将数组从第 P 个元素移动到末尾(第 N 个元素)。所以下次 A 的前 P 个元素中会有一个不同的元素。它将继续移位直到 (N-P) 次尝试。然后我开始从第 (P-1) 个元素移到末尾一次，并从第 P 个元素到末尾执行相同的移位方法，以测试第一个 P 元素中具有 2 个不同元素的所有不同情况。

如果所有的case都测试到改变P元素的最后两个元素，那么再测试最后三个元素....直到找到一组可以被程序处理的P元素或者所有可能的组合已测试(返回 false)。

我的解决方案是针对不同数量的 P 使用 switch 函数。代码随着 P 的增加而增加。

请问各位有没有更好的方法在matlab中测试一个数组所有可能的组合？另外，如果没有在 matlab 中进行切换，是否有更好的方法来进行迭代？

我考虑过使用“perms”，但这个函数最多只能有 10 个元素。

提前致谢!

Answer 1

我很无聊，可能有一些东西给你。 An answer问题combination and permutation in C++引导我进行快速 C++ 实现 for_each_permutation .我们可以为其编写一个 MEX 接口(interface)，而不是将其转换为 Matlab。该算法由 Howard Hinnant 提出。

例子

我下面给出的实现可以这样使用

>> for_each_perm([1 2 3 4 5], 2, @your_function);

重要的是数组是行向量!例如，用

function stop = your_function(combination)
    disp(combination);
    stop = false; % never stop
end

这会输出

 1     2
 1     3
 1     4
 1     5
 2     3
 2     4
 2     5
 3     4
 3     5
 4     5

与

function stop = your_function(combination)
    disp(combination);
    stop = all(combination == [2 4]); % stop after [2 4]
end

这会输出

 1     2
 1     3
 1     4
 1     5
 2     3
 2     4

实现

第一步是从for_each_permutation复制代码(在标题“实现”之后开始)到文件 perms.h 中。然后创建一个文件 for_each_perm.cpp。从指令开始

#include "mex.h"
#include "matrix.h"
#include <iostream>   
#include "perms.h"

并继续前向声明

mxArray * getMexArray(const std::vector<double>&);
bool apply(const mxArray *function, const std::vector<double>& combination);

然后是应用于每个组合的仿函数。它将调用您传递的函数:

class Functor
{
    const mxArray *function;
public:
    explicit Functor(const mxArray *f) : function(f) {}

    template <class It>
    bool operator()(It first, It last) // called for each combination
    {
        std::vector<double> combination;
        std::copy(first, last, std::back_inserter(combination));
        return apply(function, combination);
    }
};

然后是Matlab调用的入口点:

void mexFunction(int nlhs, mxArray *[], int nrhs, const mxArray *prhs[])
{
    // You should check the arguments here. Skipped for brevity.

    // Get the input arguments
    double *A = mxGetPr(prhs[0]);
    size_t m = mxGetM(prhs[0]);  
    size_t n = mxGetN(prhs[0]);
    size_t r = *mxGetPr(prhs[1]);
    mxArray *function = const_cast<mxArray*>(prhs[2]);

    // Call the actual implementation
    std::vector<double> v(A, A + n);
    for_each_combination(v.begin(), v.begin() + r, v.end(), Functor(function));
}

最后，实现forwand声明的函数

// from https://stackoverflow.com/a/9641296
mxArray * getMexArray(const std::vector<double>& v){
    mxArray * mx = mxCreateDoubleMatrix(1, v.size(), mxREAL);
    std::copy(v.begin(), v.end(), mxGetPr(mx));
    return mx;
}

和

bool apply(const mxArray *function, const std::vector<double>& combination)
{
    mxArray *lhs, *rhs[2];
    bool l;

    rhs[0] = const_cast<mxArray*>(function);
    rhs[1] = getMexArray(combination);

    mexCallMATLAB(1, &lhs, 2, rhs, "feval");
    l = *mxGetLogicals(lhs);

    mxDestroyArray(lhs);
    mxDestroyArray(rhs[1]);

    return l;
}

最后，编译MEX文件

mex for_each_perm.cpp