Mercurial > jwe > octave
changeset 31122:46e15523ca06
perms.m: Small cleanups for Octave coding conventions (bug #60364)
* perms.m: Wrap long lines in documentation to < 80 characters. Change
output in documentation example to match what Octave actually produces.
Use true/false for boolean variable "unique_v" rather than 0/1. Cuddle
parentheses when doing indexing and use a space when calling a function.
Add FIXME notes requesting an explanation of the apparently complicated
algorithm being used for permutations and unque permutations.
Remove period at end of error() message text per Octave conventions.
Change BIST input validation to more precisely check error() message.
author | Rik <rik@octave.org> |
---|---|
date | Tue, 05 Jul 2022 08:57:15 -0700 |
parents | 7d3bda173b63 |
children | 18b8f73595e0 |
files | scripts/specfun/perms.m |
diffstat | 1 files changed, 52 insertions(+), 49 deletions(-) [+] |
line wrap: on
line diff
--- a/scripts/specfun/perms.m Mon Jul 04 21:38:15 2022 +0200 +++ b/scripts/specfun/perms.m Tue Jul 05 08:57:15 2022 -0700 @@ -32,7 +32,7 @@ ## @code{factorial (@var{n}) * @var{n}}, where @var{n} is the length of ## @var{v}. Any repeated elements are included in the output. ## -## If the optional argument @qcode{"unique"} is given, then only unique +## If the optional argument @qcode{"unique"} is given then only unique ## permutations are returned, using less memory and generally taking less time ## than calling @code{unique (perms (@var{v}), "rows")}. ## @@ -57,18 +57,19 @@ ## @group ## perms ([1, 1, 2, 2], "unique") ## @result{} -## 2 2 1 1 -## 2 1 2 1 +## 1 1 2 2 +## 1 2 1 2 +## 1 2 2 1 ## 2 1 1 2 -## 1 2 2 1 -## 1 2 1 2 -## 1 1 2 2 +## 2 1 2 1 +## 2 2 1 1 ## @end group ## @end example ## ## Programming Note: If the @qcode{"unique"} option is not used, the length of ## @var{v} should be no more than 10-12 to limit memory consumption. Even with -## @qcode{"unique"}, there should be no more than 10-12 unique elements in @var{v}. +## @qcode{"unique"}, there should be no more than 10-12 unique elements in +## @var{v}. ## @seealso{permute, randperm, nchoosek} ## @end deftypefn @@ -82,13 +83,12 @@ print_usage (); endif - unique_v = 0; + unique_v = false; if (nargin == 2) if (! strcmpi (opt, "unique")) - error ('perms: option must be the string "unique".'); - else - unique_v = 1; + error ('perms: option must be the string "unique"'); endif + unique_v = true; endif v = v(:).'; # convert to row vector @@ -113,69 +113,72 @@ if (unique_v) P = unique (P, "rows"); endif - else - if (! unique_v) - v = v(end:-1:1); - n-= 1; + + elseif (! unique_v) + ## FIXME: Brief explanation of the algorithm being used would be useful. + v = v(end:-1:1); + n-= 1; - idx = zeros (factorial (n), n); - idx(1:6, n-2:n) = [1, 2, 3;1, 3, 2;2, 1, 3;2, 3, 1;3, 1, 2;3, 2, 1]+(n-3); - f = 2; # jump-start for efficiency with medium n - for j = 3:n-1 - b = 1:n; - f *= j; - perm = idx(1:f, n-(j-1):n); - idx(1:(j+1)*f, n-j) = (n-j:n)(ones (f, 1),:)(:); - for i=0:j - b(i+n-j) -= 1; - idx((1:f)+i*f, n-(j-1):n) = b(perm); - endfor + idx = zeros (factorial (n), n); + idx(1:6, n-2:n) = [1, 2, 3;1, 3, 2;2, 1, 3;2, 3, 1;3, 1, 2;3, 2, 1]+(n-3); + f = 2; # jump-start for efficiency with medium n + for j = 3:n-1 + b = 1:n; + f *= j; + perm = idx(1:f, n-(j-1):n); + idx(1:(j+1)*f, n-j) = (n-j:n)(ones (f, 1),:)(:); + for i = 0:j + b(i+n-j) -= 1; + idx((1:f)+i*f, n-(j-1):n) = b(perm); endfor + endfor - n += 1; - f *= n-1; - P = v(1)(ones (factorial (n), n)); - P(:,1) = v(ones (f, 1),:)(:); + n += 1; + f *= n-1; + P = v(1)(ones (factorial (n), n)); + P(:,1) = v(ones (f, 1),:)(:); - for i = 1:n - b = v([1:i-1 i+1:n]); - P((1:f)+(i-1)*f, 2:end) = b(idx); - endfor - else # user wants unique permutations - [v, i, j] = unique(v); - h = accumarray (j, 1)'; - idx = m_perms (h); - P = v (sortrows (idx')); - endif + for i = 1:n + b = v([1:i-1 i+1:n]); + P((1:f)+(i-1)*f, 2:end) = b(idx); + endfor + + else # unique permutations + [v, ~, j] = unique (v); + h = accumarray (j, 1)'; + idx = m_perms (h); + P = v(sortrows (idx')); endif endfunction function out_perms = m_perms (multis) + ## FIXME: Brief explanation of the algorithm being used would be useful. l = numel (multis); if (l == 1) out_perms = uint8 (ones (multis, 1)); else p1 = m_perms (multis (1:floor (l/2))); - p2 = m_perms (multis (floor(l/2)+1:l)) + max (p1 (:, 1)); + p2 = m_perms (multis (floor (l/2+1):l)) + max (p1(:, 1)); l1 = rows (p1); l2 = rows (p2); cp1 = columns (p1); cp2 = columns (p2); p = nchoosek (1:l1+l2, l1); - rp = rows(p); + rp = rows (p); ii = false (l1+l2, rp); ii(p + (0:rp - 1)' * (l1 + l2)) = true; out_perms = zeros (l1 + l2, cp1 * cp2 * rp, "uint8"); - out_perms (repmat ( ii, cp1 * cp2, 1)(:)) = repmat (p1, cp2, rp)(:); - out_perms (repmat (!ii, cp1 * cp2, 1)(:)) = repmat (p2, 1, cp1 * rp)(:); + out_perms(repmat ( ii, cp1 * cp2, 1)(:)) = repmat (p1, cp2, rp)(:); + out_perms(repmat (!ii, cp1 * cp2, 1)(:)) = repmat (p2, 1, cp1 * rp)(:); endif endfunction + %!assert (rows (perms (1:6)), factorial (6)) %!assert (perms (pi), pi) %!assert (perms ([pi, e]), [pi, e; e, pi]) @@ -190,8 +193,8 @@ %!assert (size (perms ([1 1 1 1 2 2 2 3 3], "unique")), [1260 9]) %!assert (size (perms (int8([1 1 1 1 1 2 2 2 2 3 3 3]), "unique")), [27720 12]) -## Should work for any array type, such as cells and structs, and not -## only for numeric data. +## Should work for any array type, such as cells and structs, +## and not only for numeric data. %!assert <*52431> (perms ({1}), {1}) %!assert <*52431> (perms ({0.1, "foo"}), {"foo", 0.1; 0.1, "foo"}) @@ -230,6 +233,6 @@ ## Test input validation %!error <Invalid call> perms () -%!error <option must be the string> perms (1:5, "foobar") -%!error <option must be the string> perms (1:5, {"foo"}) +%!error <option must be the string "unique"> perms (1:5, "foobar") +%!error <option must be the string "unique"> perms (1:5, {"foo"})