Generate all combinations of k values from x without replacement.
c = specfun_subset ( x , k ) c = specfun_subset ( x , k , d )
a 1-by-n or n-by-1 matrix, the values to be combined. If d=="r" (default), then x must be 1-by-n. If d=="c" (default), then x must be n-by-1.
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" (default), 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" (default), 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.
Any optional argument equal to the empty matrix [] is replaced by its default value.
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
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 :
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 ) // Produce column-by-column combinations specfun_subset ( [17 32 48 53 72]' , 3 , "c" ) // Produce row-by-row combinations (default) specfun_subset ( [17 32 48 53 72] , 3 , "r" ) // Generates an error: x must be consistent with d specfun_subset ( [17 32 48 53 72]' , 3 , "r" ) specfun_subset ( [17 32 48 53 72] , 3 , "c" ) // 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 ) | ![]() | ![]() |
http://home.att.net/~srschmitt/script_nchoosek.html
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 284-286.