specfun_subset — Generate all combinations of k values from x without replacement.
c = specfun_subset ( x , k ) c = specfun_subset ( x , k , d )
a n-by-1 matrix, the values to be combined
a 1-by-1 matrix of floating point integers, the number of elements in each combination
a 1-by-1 matrix of strings, the direction of the combinations. If d=="r", then each combination is in a row of c. If d=="c", each combination is in a column of c. Default d="r".
a cnk-by-k or k-by-cnk matrix, the combinations. Here, cnk is equal to the number of combinations of n elements from k. If d=="r", then c is a cnk-by-k matrix. If d=="c", then c is a k-by-cnk matrix.
Generate all subsets of k elements from x. Here, cnk=(n,k) is the binomial coefficient and n is the number of entries in x.
Notice that the combinations are computed without replacement. Use specfun_combine if all combinations with replacement are to be generated. Use perms if all permutations are to be generated.
Can process x if x is double, strings boolean and integer (signed,unsigned, 8-bits, 16-bits, 32-bits).
Implementation Notes
The algorithm proceeds as following. Assume that d=="c". The number of nchoosek is computed from c = specfun_nchoosek ( n , k ) For example, with n=5, k=3, we get c=10. The first possible combination is a = 1:k.
For example, with n=5 and k = 3, the first combination is
a = [1 2 3]'
We store in c the value of x(a), that is, the first column of c is [x(1) x(2) x(3)]'. Then a loop is performed for all remaining nchoosek, from 2 to c. The remaining combinations are enumerated in order.
For example, with n=5, k=3, we compute the remaining combinations in the following order :
a=[1 2 4]' a=[1 2 5]' a=[1 3 4]' a=[1 3 5]' a=[1 4 5]' a=[2 3 4]' a=[2 3 5]' a=[2 4 5]' a=[3 4 5]'
Once the combination vector a is computed, we store x(a) in the corresponding column of the matrix c. Let us detail how the nchoosek are computed, that is, how the vector a is updated. First, we search for i, the first digit to be updated. We use a backward search, starting from i = k and look for the condition a(i) == n - k + i. If that condition is satisfied, we continue the search and decrease i. If not, we stop. For example, if a=[1 3 4], we find i = 3 (because a(3)=4 is different from n=5) and if a=[1 4 5], we find i=1 (because a(3)=5=n and a(2)=4=n-1). Then we increase a(i) and update all the integers a(i+1), a(i+2), ..., a(k).
This procedure is as vectorized as possible : I guess that more speed will require to write compiled source code.
specfun_subset ( (1:4) , 3 ) specfun_subset ( [17 32 48 53] , 3 ) specfun_subset ( [17 32 48 53 72] , 3 ) // Compare combinerepeat, perms and subset specfun_subset((1:3),3) // combinerepeat computed combinations with replacement specfun_combinerepeat(1:3,3) // Scilab/perms compute permutations without replacement perms(1:3) // Indirectly combine strings x = ["a" "b" "c" "d" "e"]'; k = 3; n=size(x,"*"); map = specfun_subset((1:n),k); cnk = specfun_nchoosek(n,k); computed = matrix(x(map),cnk,k) // Directly combine strings computed = specfun_subset(["a" "b" "c" "d" "e" "f"],4) // Combinations of booleans computed = specfun_subset ( [%t %f %t %f] , 3 )