How to check all the combinations of P elements in a array with total N elements in Matlab?

Question

I want to ask how to check all the combinations possibilities of P elements in a array with total N elements in Matlab? I am now trying to use P element from an array which contains N elements, let's say array A, to test in another program. If this group of P elements fails in the program, I will go back to array A and try another group of P elements. So each time the program will only test one group of P. if the program processed the P elements successfully, it program will stop and return TURE, otherwise it continue testing till all the cases are tested.

My current solution is that: I always take the first P elements in array A each iteration. If this time fails, then I start to shift the array from the Pth element to the end(Nth element). So next time the there will be a different element in the first P elements of A. It will continue shifting until (N-P) times try. then I start to shift from the (P-1)th element to the end once, and do the same shift method from the Pth to the end to test all the different cases with 2 different elements in the first P element.

If all the cases are tested to change the last two elements of the P elements, then test the last three elements....until it finds a group of P element which can be processed by the program or all the possible combinations are tested( return false).

My solution is done with a switch function for different number of P. And the code is increasing with the P increasing.

I want to ask if you guys have a better way to test all the possible combinations of a array in matlab? Also if there is a better way to do the iteration without do a switch in matlab?

I thought about using "perms", but this function is limited with at most 10 elements.

Thank you in advance!

Answer 1

I was bored and might have something for you. An answer to the question combination and permutation in C++ lead me to a fast C++ implementation for_each_permutation. Instead of translating it into Matlab, we can write a MEX interface to it. The algorithm is by Howard Hinnant.

Example

The implementation that I’m giving below can be used like this

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

It’s important that the array is a row vector! For example, with

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

this would output

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

And with

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

this would output

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

Implementation

The first step is to copy the code from for_each_permutation (starts after the heading “Implementation”) into a file perms.h. Then create a file for_each_perm.cpp. Begin with the directives

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

and continue with the forward declarations

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

Then comes the functor that is applied to each combination. It will call the function you’ve passed:

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

Then comes the entry point that is called by 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));
}

Finally, implement the forwand-declared functions

// 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;
}

and

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

Finally, compile the MEX file with

mex for_each_perm.cpp