Problem Detail: I have $ntimes k$ matrix with $k<n$ and I would like to find all its $nchoose k$ submatrices which are $ktimes 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 $nchoose k$ indices. I found online a paper titled A Parallel Algorithm for Enumerating Combinations but they didn’t provide their code in that paper.
Asked By : user2987
Answered By : Knoothe
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10899
