How to enumerate all feasible combinations based on a binary feasibility table?

I would like to enumerate all feasible combinations based on table X. Table X is a square n x n matrix of binary elements containing a "1" on place (i,j) if route j can be visited after route i.

Based on this table, I would like to generate a table containing all feasible combinations of routes: an n x k matrix containing binary elements, where k = the total number of feasible routes. This table would then include in every column a combination of ones indicating which routes can be visited.

The problem for me arises in the pseudocode already. Logically, one would start in the first row, check whether there are any columns containing a onw in this row (call this set of columns 'set A'). Then, check for all rows in set A, whether there are any ones etc. All this while in the meanwhile storing the exponentially expanding number of columns in the matrix.

In this way I create an undetermined number of nested for-loops. Hence, a recursive function would intuitively make sense. Any suggestions?

Please note that this can be seen as converting a decision tree.

Small example:

 X = [0,1,0,1;0,0,1,0;0,0,0,0;0,0,0,0]

would become

Y = [1,1;1,0;1,0;0,1]

Thanks for any help!

Answer 1

[Walter Roberson]

http://uk.mathworks.com/matlabcentral/answers/216888-preallocation-of-matrix-with-undetermined-dimensions#comment_285569