Mercurial > hg > octave-nkf
annotate scripts/specfun/nchoosek.m @ 19251:83b88e20e9c1
nchoosek.m: Overhaul function.
* nchoosek.m: Update docstring. Use same variable names in function as in
documentation for clarity. Improve input validation. Don't manually
clear variables at end of function which will go out of scope anyways and
the memory reclaimed. Update built-in self tests.
| author | Rik <rik@octave.org> |
|---|---|
| date | Fri, 29 Aug 2014 16:30:11 -0700 |
| parents | 1514f5337781 |
| children | 4197fc428c7d |
| rev | line source |
|---|---|
|
17744
d63878346099
maint: Update copyright notices for release.
John W. Eaton <jwe@octave.org>
parents:
14363
diff
changeset
|
1 ## Copyright (C) 2001-2013 Rolf Fabian and Paul Kienzle |
|
8391
343f0fbca6eb
implement nchoosek without recursion
Jaroslav Hajek <highegg@gmail.com>
parents:
8361
diff
changeset
|
2 ## Copyright (C) 2008 Jaroslav Hajek |
| 5827 | 3 ## |
| 4 ## This file is part of Octave. | |
| 5 ## | |
| 6 ## Octave is free software; you can redistribute it and/or modify it | |
| 7 ## under the terms of the GNU General Public License as published by | |
| 7016 | 8 ## the Free Software Foundation; either version 3 of the License, or (at |
| 9 ## your option) any later version. | |
| 5827 | 10 ## |
| 11 ## Octave is distributed in the hope that it will be useful, but | |
| 12 ## WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 13 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 14 ## General Public License for more details. | |
| 15 ## | |
| 16 ## You should have received a copy of the GNU General Public License | |
| 7016 | 17 ## along with Octave; see the file COPYING. If not, see |
| 18 ## <http://www.gnu.org/licenses/>. | |
| 5827 | 19 |
| 20 ## -*- texinfo -*- | |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
21 ## @deftypefn {Function File} {@var{c} =} nchoosek (@var{n}, @var{k}) |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
22 ## @deftypefnx {Function File} {@var{c} =} nchoosek (@var{set}, @var{k}) |
| 5827 | 23 ## |
| 19251 | 24 ## Compute the binomial coefficient of @var{n} or list all possible |
| 25 ## combinations of a @var{set} of items. | |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
26 ## |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
27 ## If @var{n} is a scalar then calculate the binomial coefficient |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
28 ## of @var{n} and @var{k} which is defined as |
| 5827 | 29 ## @tex |
| 30 ## $$ | |
| 31 ## {n \choose k} = {n (n-1) (n-2) \cdots (n-k+1) \over k!} | |
| 6754 | 32 ## = {n! \over k! (n-k)!} |
| 5827 | 33 ## $$ |
| 34 ## @end tex | |
|
8517
81d6ab3ac93c
Allow documentation tobe built for other formats than tex and info
sh@sh-laptop
parents:
8506
diff
changeset
|
35 ## @ifnottex |
| 5827 | 36 ## |
| 37 ## @example | |
| 38 ## @group | |
| 39 ## / \ | |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
40 ## | n | n (n-1) (n-2) @dots{} (n-k+1) n! |
| 6754 | 41 ## | | = ------------------------- = --------- |
| 42 ## | k | k! k! (n-k)! | |
| 5827 | 43 ## \ / |
| 44 ## @end group | |
| 45 ## @end example | |
|
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10800
diff
changeset
|
46 ## |
|
8517
81d6ab3ac93c
Allow documentation tobe built for other formats than tex and info
sh@sh-laptop
parents:
8506
diff
changeset
|
47 ## @end ifnottex |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
48 ## @noindent |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
49 ## This is the number of combinations of @var{n} items taken in groups of |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
50 ## size @var{k}. |
| 5827 | 51 ## |
|
14093
050bc580cb60
doc: Various docstring improvements before 3.6.0 release.
Rik <octave@nomad.inbox5.com>
parents:
14090
diff
changeset
|
52 ## If the first argument is a vector, @var{set}, then generate all |
|
050bc580cb60
doc: Various docstring improvements before 3.6.0 release.
Rik <octave@nomad.inbox5.com>
parents:
14090
diff
changeset
|
53 ## combinations of the elements of @var{set}, taken @var{k} at a time, with |
|
050bc580cb60
doc: Various docstring improvements before 3.6.0 release.
Rik <octave@nomad.inbox5.com>
parents:
14090
diff
changeset
|
54 ## one row per combination. The result @var{c} has @var{k} columns and |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
55 ## @w{@code{nchoosek (length (@var{set}), @var{k})}} rows. |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
56 ## |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
57 ## For example: |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
58 ## |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
59 ## How many ways can three items be grouped into pairs? |
| 5827 | 60 ## |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
61 ## @example |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
62 ## @group |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
63 ## nchoosek (3, 2) |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
64 ## @result{} 3 |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
65 ## @end group |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
66 ## @end example |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
67 ## |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
68 ## What are the possible pairs? |
|
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
69 ## |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
70 ## @example |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
71 ## @group |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
72 ## nchoosek (1:3, 2) |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
73 ## @result{} 1 2 |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
74 ## 1 3 |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
75 ## 2 3 |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
76 ## @end group |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
77 ## @end example |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
78 ## |
| 19251 | 79 ## Programming Note: When calculating the binomial coefficient @code{nchoosek} |
| 80 ## works only for non-negative, integer arguments. Use @code{bincoeff} for | |
| 81 ## non-integer and negative scalar arguments, or for computing many binomial | |
| 82 ## coefficients at once with vector inputs for @var{n} or @var{k}. | |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
83 ## |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
84 ## @seealso{bincoeff, perms} |
| 5827 | 85 ## @end deftypefn |
| 86 | |
| 6316 | 87 ## Author: Rolf Fabian <fabian@tu-cottbus.de> |
| 88 ## Author: Paul Kienzle <pkienzle@users.sf.net> | |
|
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
89 ## Author: Jaroslav Hajek |
| 5827 | 90 |
| 19251 | 91 function C = nchoosek (v, k) |
| 5827 | 92 |
|
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
93 if (nargin != 2 |
| 19251 | 94 || ! (isreal (k) && isscalar (k)) |
| 95 || ! (isnumeric (v) && isvector (v))) | |
| 6316 | 96 print_usage (); |
| 5827 | 97 endif |
| 19251 | 98 if (k < 0 || k != fix (k)) |
| 99 error ("nchoosek: K must be an integer >= 0"); | |
| 100 elseif (isscalar (v) && (iscomplex (v) || v < k || v < 0 || v != fix (v))) | |
| 101 error ("nchoosek: N must be a non-negative integer >= K"); | |
|
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
102 endif |
| 5827 | 103 |
| 6318 | 104 n = length (v); |
| 105 | |
| 106 if (n == 1) | |
| 8506 | 107 ## Improve precision at next step. |
| 108 k = min (k, v-k); | |
| 19251 | 109 C = round (prod ((v-k+1:v)./(1:k))); |
| 110 if (C*2*k*eps >= 0.5) | |
| 111 warning ("nchoosek: possible loss of precision"); | |
|
8391
343f0fbca6eb
implement nchoosek without recursion
Jaroslav Hajek <highegg@gmail.com>
parents:
8361
diff
changeset
|
112 endif |
|
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
113 elseif (k == 0) |
| 19251 | 114 C = zeros (1,0); |
| 6318 | 115 elseif (k == 1) |
| 19251 | 116 C = v(:); |
|
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
117 elseif (k == n) |
| 19251 | 118 C = v(:).'; |
|
8391
343f0fbca6eb
implement nchoosek without recursion
Jaroslav Hajek <highegg@gmail.com>
parents:
8361
diff
changeset
|
119 elseif (k > n) |
| 19251 | 120 C = zeros (0, k, class (v)); |
| 10800 | 121 elseif (k == 2) |
| 122 ## Can do it without transpose. | |
| 123 x = repelems (v(1:n-1), [1:n-1; n-1:-1:1]).'; | |
| 124 y = cat (1, cellslices (v(:), 2:n, n*ones (1, n-1)){:}); | |
| 19251 | 125 C = [x, y]; |
| 10800 | 126 elseif (k < n) |
| 127 v = v(:).'; | |
| 19251 | 128 C = v(k:n); |
| 10800 | 129 l = 1:n-k+1; |
| 130 for j = 2:k | |
| 19251 | 131 c = columns (C); |
| 132 cA = cellslices (C, l, c*ones (1, n-k+1), 2); | |
| 10800 | 133 l = c-l+1; |
| 134 b = repelems (v(k-j+1:n-j+1), [1:n-k+1; l]); | |
| 19251 | 135 C = [b; cA{:}]; |
| 10800 | 136 l = cumsum (l); |
| 137 l = [1, 1 + l(1:n-k)]; | |
|
8391
343f0fbca6eb
implement nchoosek without recursion
Jaroslav Hajek <highegg@gmail.com>
parents:
8361
diff
changeset
|
138 endfor |
| 19251 | 139 C = C.'; |
| 6318 | 140 endif |
| 19251 | 141 |
|
8361
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
142 endfunction |
| 6318 | 143 |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
144 |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
145 %!assert (nchoosek (80,10), bincoeff (80,10)) |
|
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
146 %!assert (nchoosek (1:5,3), [1:3;1,2,4;1,2,5;1,3,4;1,3,5;1,4,5;2:4;2,3,5;2,4,5;3:5]) |
|
18983
1514f5337781
nchoosek.m: nchoosek(N,0) now returns [](1x0) when N is a vector (bug #41890).
Pedro Angelo <fonini@poli.ufrj.br>
parents:
17744
diff
changeset
|
147 %!assert (size (nchoosek (1:5,0)), [1 0]) |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
148 |
|
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
149 %% Test input validation |
| 19251 | 150 %!error nchoosek () |
| 151 %!error nchoosek (1) | |
| 152 %!error nchoosek (1,2,3) | |
| 153 | |
| 154 %!error nchoosek (100, 2i) | |
| 155 %!error nchoosek (100, [2 3]) | |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
156 %!error nchoosek ("100", 45) |
| 19251 | 157 %!error nchoosek (100*ones (2, 2), 45) |
| 158 %!error <K must be an integer .= 0> nchoosek (100, -45) | |
| 159 %!error <K must be an integer .= 0> nchoosek (100, 45.5) | |
| 160 %!error <N must be a non-negative integer .= K> nchoosek (100i, 2) | |
| 161 %!error <N must be a non-negative integer .= K> nchoosek (100, 145) | |
| 162 %!error <N must be a non-negative integer .= K> nchoosek (-100, 45) | |
| 163 %!error <N must be a non-negative integer .= K> nchoosek (100.5, 45) | |
| 164 %!warning <possible loss of precision> nchoosek (100, 45); | |
|
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
165 |