2
$\begingroup$

I have $n\times k$ matrix with $k<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried to do it with Matlab but it takes too long time specially when $n>20$ and I couldn't find a way how to generate in parallel the $n\choose k$ indices.

I found online a paper titled A Parallel Algorithm for Enumerating Combinations but they didn't provide their code in that paper.

$\endgroup$
5
$\begingroup$

Since you just need to select $k$ rows, this becomes the same as choosing $k$ elements of a given set of $n$ elements, say $\{1,2,\dots,n\}$.

You can generate $n \choose k$ combinations in lexicographic order (i.e. starting with $\{1,2,3, \dots, k\}$ and ending with $\{n-k+1, ..., n-1,n\}$), with the next one depending only on the previous one.

The fact that the order is predictable, and that you only need the previous state, allows you to split the output space, and apply independent parallel computations to each.

There are plenty of algorithms available on the web for lexicographic generation, for instance Frank Ruskey's book: Combinatorial Generation has a chapter (4) on lexicographic algorithms, and for your purposes, you can use Algorithm 4.4 which appears on page 58.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.