Optimizing computational cost on a task involving a multi-nested loop

Question

I am just a beginner of programming, and sorry in advance for bothering you by a (presumably) basic question.

I would like to perform the following task:

(I apologize for inconvenience; I don't know how to input a TeX-y formula in Stack Overflow ). I am primarily considering an implementation on MATLAB or Scilab, but language does not matter so much.

The most naive approach to perform this, I think, is to form an n-nested for loop, that is (the case n=2 on MATLAB is shown for example),

n=2;
x=[x1,x2];
for u=0:1
    y(1)=u;
    if x(1)>0 then
        y(1)=1;
    end
    for v=0:1
        y(2)=v;
        if x(2)>0 then
            y(2)=1;
        end
        z=Function(y);
    end
end

However, this implementation is too laborious for large n, and more importantly, it causes 2^n-2^k abundant evaluations of the function, where k is a number of negative elements in x. Also, naively forming a k-nested for loop with knowledge of which element in x is negative, e.g.

n=2;
x=[-1,2];
y=[1,1];
for u=0:1
    y(1)=u;
    z=Function(y);
end

doesn't seem to be a good way; if we want to perform the task for different x, we have to rewrite a code.

I would be grateful if you provide an idea to implement a code such that (a) evaluates the function only 2^k times (possible minimum number of evaluations) and (b) we don't have to rewrite a code even if we change x.

Answer 1

You can evaluate Function on y in Ax easily using recursion

function eval(Function, x, y, i, n) {
    if(i == n) {
        // break condition, evaluate Function
        Function(y);
    } else {
        // always evaluate y(i) == 1
        y(i) = 1;
        eval(Function, x, y, i + 1, n);
        // eval y(i) == 0 only if x(i) <= 0
        if(x(i) <= 0) {
            y(i) = 0;
            eval(Function, x, y, i + 1, n);
        }
    }
}

Turning that into efficient Matlab code is another problem.

As you've stated the number of evaluations is 2^k. Let's sort x so that only the last k elements are non-positive. To evaluate Function index y using the reverse of the permutation of the sort of x: Function(y(perm)). Even better the same method allows us to build Ax directly using dec2bin:

// every column of the resulting matrix is a member of Ax: y_i = Ax(:,i)
function Ax = getAx(x)
    n = length(x);
    // find the k indices of non-positives in x
    is = find(x <= 0);
    k = length(is);
    // construct Y (last k rows are all possible combinations of [0 1])
    Y = [ones(n - k, 2 ^ k); (dec2bin(0:2^k-1)' - '0')];
    // re-order the rows in Y to get Ax according to the permutation is (inverse is)
    perm([setdiff(1:n, is) is]) = 1:n;
    Ax = Y(perm, :);
end

Now rewrite Function to accept a matrix or iterate over the columns in Ax = getAx(x); to evaluate all Function(y).