Mercurial > octave
annotate scripts/specfun/nchoosek.m @ 30218:750de16fd35c
nchoosek.m: Fix algorithm for even K in cset f5aba4d7e651 (bug #61191).
* nchoosek.m: When doing pairwise multiplication, flip the second range so that
an even number is always multiplied by an odd number.
author | Rik <rik@octave.org> |
---|---|
date | Wed, 29 Sep 2021 09:57:01 -0700 |
parents | f5aba4d7e651 |
children | 363fb10055df |
rev | line source |
---|---|
27923
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
1 ######################################################################## |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
2 ## |
29358
0a5b15007766
update Octave Project Developers copyright for the new year
John W. Eaton <jwe@octave.org>
parents:
27985
diff
changeset
|
3 ## Copyright (C) 2001-2021 The Octave Project Developers |
27918
b442ec6dda5c
use centralized file for copyright info for individual contributors
John W. Eaton <jwe@octave.org>
parents:
26376
diff
changeset
|
4 ## |
27923
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
5 ## See the file COPYRIGHT.md in the top-level directory of this |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
6 ## distribution or <https://octave.org/copyright/>. |
5827 | 7 ## |
8 ## This file is part of Octave. | |
9 ## | |
24534
194eb4bd202b
maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents:
23220
diff
changeset
|
10 ## Octave is free software: you can redistribute it and/or modify it |
5827 | 11 ## under the terms of the GNU General Public License as published by |
24534
194eb4bd202b
maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents:
23220
diff
changeset
|
12 ## the Free Software Foundation, either version 3 of the License, or |
22755
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22323
diff
changeset
|
13 ## (at your option) any later version. |
5827 | 14 ## |
15 ## Octave is distributed in the hope that it will be useful, but | |
16 ## WITHOUT ANY WARRANTY; without even the implied warranty of | |
22755
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22323
diff
changeset
|
17 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
3a2b891d0b33
maint: Standardize Copyright formatting.
Rik <rik@octave.org>
parents:
22323
diff
changeset
|
18 ## GNU General Public License for more details. |
5827 | 19 ## |
20 ## You should have received a copy of the GNU General Public License | |
7016 | 21 ## along with Octave; see the file COPYING. If not, see |
24534
194eb4bd202b
maint: Update punctuation for GPL v3 license text.
Rik <rik@octave.org>
parents:
23220
diff
changeset
|
22 ## <https://www.gnu.org/licenses/>. |
27923
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
23 ## |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
24 ######################################################################## |
5827 | 25 |
26 ## -*- texinfo -*- | |
20852
516bb87ea72e
2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents:
19833
diff
changeset
|
27 ## @deftypefn {} {@var{c} =} nchoosek (@var{n}, @var{k}) |
516bb87ea72e
2015 Code Sprint: remove class of function from docstring for all m-files.
Rik <rik@octave.org>
parents:
19833
diff
changeset
|
28 ## @deftypefnx {} {@var{c} =} nchoosek (@var{set}, @var{k}) |
5827 | 29 ## |
19059 | 30 ## Compute the binomial coefficient of @var{n} or list all possible |
31 ## 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
|
32 ## |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
33 ## 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
|
34 ## of @var{n} and @var{k} which is defined as |
5827 | 35 ## @tex |
36 ## $$ | |
37 ## {n \choose k} = {n (n-1) (n-2) \cdots (n-k+1) \over k!} | |
6754 | 38 ## = {n! \over k! (n-k)!} |
5827 | 39 ## $$ |
40 ## @end tex | |
8517
81d6ab3ac93c
Allow documentation tobe built for other formats than tex and info
sh@sh-laptop
parents:
8506
diff
changeset
|
41 ## @ifnottex |
5827 | 42 ## |
43 ## @example | |
44 ## @group | |
45 ## / \ | |
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
46 ## | n | n (n-1) (n-2) @dots{} (n-k+1) n! |
6754 | 47 ## | | = ------------------------- = --------- |
48 ## | k | k! k! (n-k)! | |
5827 | 49 ## \ / |
50 ## @end group | |
51 ## @end example | |
10821
693e22af08ae
Grammarcheck documentation of m-files
Rik <octave@nomad.inbox5.com>
parents:
10800
diff
changeset
|
52 ## |
8517
81d6ab3ac93c
Allow documentation tobe built for other formats than tex and info
sh@sh-laptop
parents:
8506
diff
changeset
|
53 ## @end ifnottex |
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
54 ## @noindent |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
55 ## 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
|
56 ## size @var{k}. |
5827 | 57 ## |
14093
050bc580cb60
doc: Various docstring improvements before 3.6.0 release.
Rik <octave@nomad.inbox5.com>
parents:
14090
diff
changeset
|
58 ## 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
|
59 ## 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
|
60 ## 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
|
61 ## @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
|
62 ## |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
63 ## For example: |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
64 ## |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
65 ## How many ways can three items be grouped into pairs? |
5827 | 66 ## |
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
67 ## @example |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
68 ## @group |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
69 ## nchoosek (3, 2) |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
70 ## @result{} 3 |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
71 ## @end group |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
72 ## @end example |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
73 ## |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
74 ## What are the possible pairs? |
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
75 ## |
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
76 ## @example |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
77 ## @group |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
78 ## nchoosek (1:3, 2) |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
79 ## @result{} 1 2 |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
80 ## 1 3 |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
81 ## 2 3 |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
82 ## @end group |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
83 ## @end example |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
84 ## |
19059 | 85 ## Programming Note: When calculating the binomial coefficient @code{nchoosek} |
86 ## works only for non-negative, integer arguments. Use @code{bincoeff} for | |
87 ## non-integer and negative scalar arguments, or for computing many binomial | |
88 ## 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
|
89 ## |
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
90 ## @seealso{bincoeff, perms} |
5827 | 91 ## @end deftypefn |
92 | |
19059 | 93 function C = nchoosek (v, k) |
5827 | 94 |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
95 if (nargin != 2) |
6316 | 96 print_usage (); |
5827 | 97 endif |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
98 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
99 if (! isvector (v)) |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
100 error ("nchoosek: first argument must be a scalar or a vector"); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
101 endif |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
102 if (! (isreal (k) && isscalar (k) && k >= 0 && k == fix (k))) |
19059 | 103 error ("nchoosek: K must be an integer >= 0"); |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
104 endif |
30206
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
105 if (isscalar (v)) |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
106 if (isnumeric (v) && (iscomplex (v) || v < k || v < 0 || v != fix (v))) |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
107 error ("nchoosek: N must be a non-negative integer >= K"); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
108 endif |
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
109 endif |
5827 | 110 |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
111 n = numel (v); |
6318 | 112 |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
113 if (n == 1 && isnumeric (v)) |
30217
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
114 ## Improve precision over direct call to prod(). |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
115 ## Steps: 1) Make a list of integers for numerator and denominator, |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
116 ## 2) filter out common factors, 3) multiply what remains. |
8506 | 117 k = min (k, v-k); |
30217
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
118 |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
119 ## For a ~25% performance boost, multiply values pairwise so there |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
120 ## are fewer elements in do/until loop which is the slow part. |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
121 ## Since Odd*Even is guaranteed to be Even, also take out a factor |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
122 ## of 2 from numerator and denominator. |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
123 if (rem (k, 2)) # k is odd |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
124 numer = [(v-k+1:v-(k+1)/2) .* (v-1:-1:v-(k-1)/2) / 2, v]; |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
125 denom = [(1:k/2) .* (k-1:-1:(k+1)/2) / 2, k]; |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
126 else # k is even |
30218
750de16fd35c
nchoosek.m: Fix algorithm for even K in cset f5aba4d7e651 (bug #61191).
Rik <rik@octave.org>
parents:
30217
diff
changeset
|
127 numer = (v-k+1:v-k/2) .* (v:-1:v-k/2+1) / 2; |
750de16fd35c
nchoosek.m: Fix algorithm for even K in cset f5aba4d7e651 (bug #61191).
Rik <rik@octave.org>
parents:
30217
diff
changeset
|
128 denom = (1:k/2) .* (k:-1:k/2+1) / 2; |
750de16fd35c
nchoosek.m: Fix algorithm for even K in cset f5aba4d7e651 (bug #61191).
Rik <rik@octave.org>
parents:
30217
diff
changeset
|
129 endif |
30217
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
130 |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
131 # Remove common factors from numerator and denominator |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
132 do |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
133 for i = numel (denom):-1:1 |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
134 factors = gcd (denom(i), numer); |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
135 [f, j] = max (factors); |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
136 denom(i) /= f; |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
137 numer(j) /= f; |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
138 endfor |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
139 denom = denom(denom > 1); |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
140 numer = numer(numer > 1); |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
141 until (isempty (denom)) |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
142 |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
143 C = prod (numer); |
f5aba4d7e651
nchoosek.m: New algorithm with more precision when N, K are scalars (bug #61199)
Rik <rik@octave.org>
parents:
30209
diff
changeset
|
144 if (C > flintmax) |
19059 | 145 warning ("nchoosek: possible loss of precision"); |
8391
343f0fbca6eb
implement nchoosek without recursion
Jaroslav Hajek <highegg@gmail.com>
parents:
8361
diff
changeset
|
146 endif |
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
147 elseif (k == 0) |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
148 C = v(zeros (1, 0)); # Return 1x0 object for Matlab compatibility |
6318 | 149 elseif (k == 1) |
19059 | 150 C = v(:); |
8404
868149aac690
nchoosek checks, warning, corner cases and tests
Francesco Potortì <pot@gnu.org>
parents:
8391
diff
changeset
|
151 elseif (k == n) |
19059 | 152 C = v(:).'; |
8391
343f0fbca6eb
implement nchoosek without recursion
Jaroslav Hajek <highegg@gmail.com>
parents:
8361
diff
changeset
|
153 elseif (k > n) |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
154 C = v(zeros (0, k)); # return 0xk object for Matlab compatibility |
10800 | 155 elseif (k == 2) |
156 ## Can do it without transpose. | |
30209
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
157 x = repelem (v(1:n-1), [n-1:-1:1]).'; |
10800 | 158 y = cat (1, cellslices (v(:), 2:n, n*ones (1, n-1)){:}); |
19059 | 159 C = [x, y]; |
10800 | 160 elseif (k < n) |
161 v = v(:).'; | |
19059 | 162 C = v(k:n); |
10800 | 163 l = 1:n-k+1; |
164 for j = 2:k | |
19059 | 165 c = columns (C); |
166 cA = cellslices (C, l, c*ones (1, n-k+1), 2); | |
10800 | 167 l = c-l+1; |
30209
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
168 b = repelem (v(k-j+1:n-j+1), l); |
19059 | 169 C = [b; cA{:}]; |
10800 | 170 l = cumsum (l); |
171 l = [1, 1 + l(1:n-k)]; | |
8391
343f0fbca6eb
implement nchoosek without recursion
Jaroslav Hajek <highegg@gmail.com>
parents:
8361
diff
changeset
|
172 endfor |
19059 | 173 C = C.'; |
6318 | 174 endif |
19059 | 175 |
8361
cf620941af1a
Set max_recursion_depth and use a subfunction in nchoosek
Francesco Potortì <pot@gnu.org>
parents:
7017
diff
changeset
|
176 endfunction |
6318 | 177 |
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
178 |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
179 %!assert (nchoosek (80, 10), bincoeff (80, 10)) |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
180 %!assert (nchoosek (1:5, 3), |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
181 %! [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]) |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
182 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
183 # Test basic behavior for various input types |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
184 %!assert (nchoosek ('a':'b', 2), 'ab') |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
185 %!assert (nchoosek ("a":"b", 2), "ab") |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
186 %!assert (nchoosek ({1,2}, 2), {1,2}) |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
187 %!test |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
188 %! s(1).a = 1; |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
189 %! s(2).a = 2; |
30209
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
190 %! assert (nchoosek (s, 1), s(:)); |
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
191 %! assert (nchoosek (s, 2), s); |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
192 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
193 # Verify Matlab compatibility of return sizes & types |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
194 %!test |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
195 %! x = nchoosek (1:2, 0); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
196 %! assert (size (x), [1, 0]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
197 %! assert (isa (x, "double")); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
198 %! x = nchoosek (1:2, 3); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
199 %! assert (size (x), [0, 3]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
200 %! assert (isa (x, "double")); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
201 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
202 %!test |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
203 %! x = nchoosek (single (1:2), 0); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
204 %! assert (size (x), [1, 0]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
205 %! assert (isa (x, "single")); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
206 %! x = nchoosek (single (1:2), 3); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
207 %! assert (size (x), [0, 3]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
208 %! assert (isa (x, "single")); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
209 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
210 %!test |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
211 %! x = nchoosek ('a':'b', 0); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
212 %! assert (size (x), [1, 0]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
213 %! assert (is_sq_string (x)); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
214 %! x = nchoosek ('a':'b', 3); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
215 %! assert (size (x), [0, 3]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
216 %! assert (is_sq_string (x)); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
217 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
218 %!test |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
219 %! x = nchoosek ("a":"b", 0); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
220 %! assert (size (x), [1, 0]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
221 %! assert (is_dq_string (x)); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
222 %! x = nchoosek ("a":"b", 3); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
223 %! assert (size (x), [0, 3]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
224 %! assert (is_dq_string (x)); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
225 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
226 %!test |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
227 %! x = nchoosek (uint8(1):uint8(2), 0); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
228 %! assert (size (x), [1, 0]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
229 %! assert (isa (x, "uint8")); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
230 %! x = nchoosek (uint8(1):uint8(2), 3); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
231 %! assert (size (x), [0, 3]); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
232 %! assert (isa (x, "uint8")); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
233 |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
234 %!test |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
235 %! x = nchoosek ({1, 2}, 0); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
236 %! assert (size (x), [1, 0]); |
30206
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
237 %! assert (iscell (x)); |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
238 %! x = nchoosek ({1, 2}, 3); |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
239 %! assert (size (x), [0, 3]); |
30206
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
240 %! assert (iscell (x)); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
241 |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
242 %!test |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
243 %! s.a = [1 2 3]; |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
244 %! s.b = [4 5 6]; |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
245 %! x = nchoosek (s, 0); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
246 %! assert (size (x), [1, 0]); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
247 %! assert (isstruct (x)); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
248 %! assert (fieldnames (x), {"a"; "b"}); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
249 %! x = nchoosek (s, 3); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
250 %! assert (size (x), [0, 3]); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
251 %! assert (isstruct (x)); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
252 %! assert (fieldnames (x), {"a"; "b"}); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
253 |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
254 %!test |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
255 %! s.a = [1 2 3]; |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
256 %! s.b = [4 5 6]; |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
257 %! s(2).a = 1; # make s a struct array rather than scalar struct |
30209
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
258 %! s(3).b = 2; # make s at least three elements for k == 2 test below |
30206
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
259 %! x = nchoosek (s, 0); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
260 %! assert (size (x), [1, 0]); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
261 %! assert (isstruct (x)); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
262 %! assert (fieldnames (x), {"a"; "b"}); |
30209
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
263 %! x = nchoosek (s, 2); |
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
264 %! assert (size (x), [3, 2]); |
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
265 %! assert (isstruct (x)); |
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
266 %! assert (fieldnames (x), {"a"; "b"}); |
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
267 %! x = nchoosek (s, 4); |
54774a713d7c
nchoosek.m: Improve struct input handling for k<n (bug #61119)
Nicholas R. Jankowski <jankowskin@asme.org>
parents:
30206
diff
changeset
|
268 %! assert (size (x), [0, 4]); |
30206
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
269 %! assert (isstruct (x)); |
aaee7b170cb1
nchoosek.m: Allow struct inputs (bug #61119)
Rik <rik@octave.org>
parents:
30205
diff
changeset
|
270 %! assert (fieldnames (x), {"a"; "b"}); |
14090
281ecc6fb431
nchoosek.m: Update documentation, fix input validation, add more %!tests
Rik <octave@nomad.inbox5.com>
parents:
14062
diff
changeset
|
271 |
19833
9fc020886ae9
maint: Clean up m-files to follow Octave coding conventions.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
272 ## Test input validation |
28886
d8318c12d903
test: remove unnecessary BIST tests in m-files checking for excessive number of inputs.
Rik <rik@octave.org>
parents:
27985
diff
changeset
|
273 %!error <Invalid call> nchoosek () |
d8318c12d903
test: remove unnecessary BIST tests in m-files checking for excessive number of inputs.
Rik <rik@octave.org>
parents:
27985
diff
changeset
|
274 %!error <Invalid call> nchoosek (1) |
30205
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
275 %!error <first argument must be a scalar or a vector> nchoosek (ones (3, 3), 1) |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
276 %!error <K must be an integer .= 0> nchoosek (100, 2i) |
23a907b2dbd5
nchoosek.m: Allow "char" and other non-numeric inputs (bug #61119)
Rik <rik@octave.org>
parents:
30204
diff
changeset
|
277 %!error <K must be an integer .= 0> nchoosek (100, [2 3]) |
19059 | 278 %!error <K must be an integer .= 0> nchoosek (100, -45) |
279 %!error <K must be an integer .= 0> nchoosek (100, 45.5) | |
280 %!error <N must be a non-negative integer .= K> nchoosek (100i, 2) | |
281 %!error <N must be a non-negative integer .= K> nchoosek (100, 145) | |
282 %!error <N must be a non-negative integer .= K> nchoosek (-100, 45) | |
283 %!error <N must be a non-negative integer .= K> nchoosek (100.5, 45) | |
284 %!warning <possible loss of precision> nchoosek (100, 45); |