Mercurial > octave

comparison scripts/specfun/perms.m @ 31031:8629bb61ef17

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
maint: perms.m: Copyedit docstring and comments to match Octave codestyle perms.m: Copyedit docstring, add some spacing, remove commented-out fprintf.
author Arun Giridhar <arungiridhar@gmail.com>
date Thu, 26 May 2022 13:12:31 -0400
parents f03e1eebf46d
children b949f8a631e2
comparison
equal deleted inserted replaced
31030:ded93e72418d 31031:8629bb61ef17
28 ## @deftypefnx {} {@var{P} =} perms (@var{v}, "unique") 28 ## @deftypefnx {} {@var{P} =} perms (@var{v}, "unique")
29 ## Generate all permutations of vector @var{v} with one row per permutation. 29 ## Generate all permutations of vector @var{v} with one row per permutation.
30 ## 30 ##
31 ## Results are returned in inverse lexicographic order. The result has size 31 ## Results are returned in inverse lexicographic order. The result has size
32 ## @code{factorial (@var{n}) * @var{n}}, where @var{n} is the length of 32 ## @code{factorial (@var{n}) * @var{n}}, where @var{n} is the length of
33 ## @var{v}. Any repetitions are included in the output. 33 ## @var{v}. Any repeated elements are included in the output.
34 ## 34 ##
35 ## If the optional second argument is the string "unique", then only unique 35 ## If the optional argument "unique" is given, then only unique permutations
36 ## permutations are returned, using a method that uses less memory than 36 ## are returned, using less memory and generally taking less time than calling
37 ## @code{unique (perms (@var{v}), "rows")} and can be faster for 37 ## @code{unique (perms (@var{v}), "rows")}. In this case, the results are
38 ## certain inputs. In this case, the results are not guaranteed to be in any 38 ## not guaranteed to be in any particular order.
39 ## particular order.
40 ## 39 ##
41 ## Example 1 40 ## Example 1
42 ## @example 41 ## @example
43 ## @group 42 ## @group
44 ## perms ([1, 2, 3]) 43 ## perms ([1, 2, 3])
64 ## 1 2 1 2 63 ## 1 2 1 2
65 ## 1 1 2 2 64 ## 1 1 2 2
66 ## @end group 65 ## @end group
67 ## @end example 66 ## @end example
68 ## 67 ##
69 ## Programming Notes: If the "unique" argument is not used, the length of 68 ## Programming Note: If the "unique" option is not used, the length of @var{v}
70 ## @var{v} should be no more than 10-12 to limit memory consumption. To get 69 ## should be no more than 10-12 to limit memory consumption. Even with
71 ## unique results, test both @code{perms (@var{v}, "unique")} and 70 ## "unique", there should be no more than 10-12 unique elements in @var{v}.
72 ## @code{unique (perms (@var{v}), "rows")} to compare speed and
73 ## memory usage.
74 ## @seealso{permute, randperm, nchoosek} 71 ## @seealso{permute, randperm, nchoosek}
75 ## @end deftypefn 72 ## @end deftypefn
76 73
77 ## FIXME: In principle it should be more efficient to do indexing using uint8 74 ## FIXME: In principle it should be more efficient to do indexing using uint8
78 ## type. However, benchmarking shows doubles are faster. If this changes in 75 ## type. However, benchmarking shows doubles are faster. If this changes in
159 for i = ulen:-1:1 156 for i = ulen:-1:1
160 freq (i) = nnz (v == uvec(i)); 157 freq (i) = nnz (v == uvec(i));
161 endfor 158 endfor
162 159
163 ## Performance is improved by handling the most frequent elements first. 160 ## Performance is improved by handling the most frequent elements first.
164 ## This can mess with the output order though. Currently we do not promise 161 ## This can change the output order though. Currently we do not promise
165 ## the results will be in any specific order. 162 ## the results will be in any specific order.
166 [freq, order] = sort (freq, "descend"); 163 [freq, order] = sort (freq, "descend");
167 uvec = uvec (order); 164 uvec = uvec (order);
168 165
169 ## Call nchoosek for each choice and do a Cartesian set product, 166 ## Call nchoosek for each choice and do a Cartesian set product,
181 tmp = tmp (all (tmp ~= k, 2), :); 178 tmp = tmp (all (tmp ~= k, 2), :);
182 endfor 179 endfor
183 180
184 r = rows (tmp); 181 r = rows (tmp);
185 c = columns (tmp); 182 c = columns (tmp);
186 if (pos + r > rows(new)) # allocate more memory on the fly 183 if (pos + r > rows(new)) # Allocate more memory on the fly
187 new (pos+r+1e5, 1) = 0; 184 new (pos + r + 1e5, 1) = 0;
188 endif 185 endif
189 186
190 new ((pos+1):(pos+r), 1:c) = tmp; 187 new ((pos+1):(pos+r), 1:c) = tmp;
191 new ((pos+1):(pos+r), (c+1):end) = repmat (this(j,:), r, 1); 188 new ((pos+1):(pos+r), (c+1):end) = repmat (this(j,:), r, 1);
192 pos += r; 189 pos += r;
193
194 # fprintf (1, "%d\t%d\t%d\t%d\t%d\t%f\n", i, j, r, pos, rows(new), toc);
195 endfor 190 endfor
196 indx = new (1:pos, :); 191 indx = new (1:pos, :);
197 endfor 192 endfor
198 clear new tmp this # clear large variables before building P 193 clear new tmp this # Clear large variables before building P
199 194
200 indx = (indx-1) * rows (indx) + (1:rows (indx))'; 195 indx = (indx-1) * rows (indx) + (1:rows (indx))';
201 196
202 ## Initialize P to be the same size as indx with the same class as v. 197 ## Initialize P to be the same size as indx with the same class as v.
203 P = repmat (v, rows(indx), 1); 198 P = repmat (v, rows(indx), 1);