Mercurial > hg > octave-lyh
annotate scripts/specfun/nchoosek.m @ 8361:cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
| author | Francesco Potortì <pot@gnu.org> |
|---|---|
| date | Sat, 29 Nov 2008 17:57:50 +0100 |
| parents | a1dbe9d80eee |
| children | 343f0fbca6eb 5032328e940b |
| rev | line source |
|---|---|
| 7017 | 1 ## Copyright (C) 2001, 2006, 2007 Rolf Fabian and Paul Kienzle |
| 5827 | 2 ## |
| 3 ## This file is part of Octave. | |
| 4 ## | |
| 5 ## Octave is free software; you can redistribute it and/or modify it | |
| 6 ## under the terms of the GNU General Public License as published by | |
| 7016 | 7 ## the Free Software Foundation; either version 3 of the License, or (at |
| 8 ## your option) any later version. | |
| 5827 | 9 ## |
| 10 ## Octave is distributed in the hope that it will be useful, but | |
| 11 ## WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 13 ## General Public License for more details. | |
| 14 ## | |
| 15 ## You should have received a copy of the GNU General Public License | |
| 7016 | 16 ## along with Octave; see the file COPYING. If not, see |
| 17 ## <http://www.gnu.org/licenses/>. | |
| 5827 | 18 |
| 19 ## -*- texinfo -*- | |
| 20 ## @deftypefn {Function File} {@var{c} =} nchoosek (@var{n}, @var{k}) | |
| 21 ## | |
| 6575 | 22 ## Compute the binomial coefficient or all combinations of @var{n}. |
| 5827 | 23 ## If @var{n} is a scalar then, calculate the binomial coefficient |
| 24 ## of @var{n} and @var{k}, defined as | |
| 25 ## | |
| 26 ## @iftex | |
| 27 ## @tex | |
| 28 ## $$ | |
| 29 ## {n \choose k} = {n (n-1) (n-2) \cdots (n-k+1) \over k!} | |
| 6754 | 30 ## = {n! \over k! (n-k)!} |
| 5827 | 31 ## $$ |
| 32 ## @end tex | |
| 33 ## @end iftex | |
| 34 ## @ifinfo | |
| 35 ## | |
| 36 ## @example | |
| 37 ## @group | |
| 38 ## / \ | |
| 6754 | 39 ## | n | n (n-1) (n-2) ... (n-k+1) n! |
| 40 ## | | = ------------------------- = --------- | |
| 41 ## | k | k! k! (n-k)! | |
| 5827 | 42 ## \ / |
| 43 ## @end group | |
| 44 ## @end example | |
| 45 ## @end ifinfo | |
| 46 ## | |
| 47 ## If @var{n} is a vector generate all combinations of the elements | |
| 48 ## of @var{n}, taken @var{k} at a time, one row per combination. The | |
| 49 ## resulting @var{c} has size @code{[nchoosek (length (@var{n}), | |
| 50 ## @var{k}), @var{k}]}. | |
| 51 ## | |
| 6316 | 52 ## @seealso{bincoeff} |
| 5827 | 53 ## @end deftypefn |
| 54 | |
| 6316 | 55 ## Author: Rolf Fabian <fabian@tu-cottbus.de> |
| 56 ## Author: Paul Kienzle <pkienzle@users.sf.net> | |
| 5827 | 57 |
| 6316 | 58 ## FIXME -- This function is identical to bincoeff for scalar |
| 5827 | 59 ## values, and so should probably be combined with bincoeff. |
| 60 | |
| 61 function A = nchoosek (v, k) | |
| 62 | |
| 6377 | 63 if (nargin != 2) |
| 6316 | 64 print_usage (); |
| 5827 | 65 endif |
| 66 | |
| 6318 | 67 n = length (v); |
| 68 | |
| 69 if (n == 1) | |
| 70 A = round (exp (sum (log (k+1:v)) - sum (log (2:v-k)))); | |
| 71 elseif (k == 0) | |
| 72 A = []; | |
| 73 elseif (k == 1) | |
| 74 A = v(:); | |
| 75 elseif (k == n) | |
| 76 A = v(:).'; | |
| 77 else | |
|
8361
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
78 oldmax = max_recursion_depth (); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
79 unwind_protect |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
80 max_recursion_depth (n); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
81 A = nck (v, k); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
82 unwind_protect_cleanup |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
83 max_recursion_depth (oldmax); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
84 end_unwind_protect |
| 6318 | 85 endif |
|
8361
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
86 endfunction |
| 6318 | 87 |
|
8361
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
88 function A = nck (v, k) |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
89 n = length (v); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
90 if (n == 1 || k < 2 || k == n) |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
91 A = nchoosek (v, k); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
92 else |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
93 m = nchoosek (n-1, k-1); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
94 A = [v(1)*ones(m,1), nck(v(2:n),k-1); |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
95 nck(v(2:n), k)]; |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
96 endif |
| 5827 | 97 endfunction |
|
8361
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
98 |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
99 %!assert (nchoosek(100,45), bincoeff(100,45)) |
|
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
100 %!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]) |