From: <car...@us...> - 2012-04-23 21:14:41
|
Revision: 10317 http://octave.svn.sourceforge.net/octave/?rev=10317&view=rev Author: carandraug Date: 2012-04-23 20:22:00 +0000 (Mon, 23 Apr 2012) Log Message: ----------- combinatorics: removing package * combs() moved to specfun and deprecated * partcnt and partint moved to miscellaneous package * NEWS/INDEX/Makefile files updated Modified Paths: -------------- trunk/octave-forge/main/combinatorics/DESCRIPTION trunk/octave-forge/main/combinatorics/NEWS trunk/octave-forge/main/miscellaneous/INDEX trunk/octave-forge/main/miscellaneous/NEWS trunk/octave-forge/main/miscellaneous/src/Makefile trunk/octave-forge/main/specfun/NEWS Added Paths: ----------- trunk/octave-forge/main/combinatorics/inst/dummy trunk/octave-forge/main/miscellaneous/PKG_ADD trunk/octave-forge/main/miscellaneous/src/partint.cc trunk/octave-forge/main/miscellaneous/src/partint.h trunk/octave-forge/main/specfun/inst/combs.m Removed Paths: ------------- trunk/octave-forge/main/combinatorics/INDEX trunk/octave-forge/main/combinatorics/PKG_ADD trunk/octave-forge/main/combinatorics/inst/combs.m trunk/octave-forge/main/combinatorics/src/ Modified: trunk/octave-forge/main/combinatorics/DESCRIPTION =================================================================== --- trunk/octave-forge/main/combinatorics/DESCRIPTION 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/combinatorics/DESCRIPTION 2012-04-23 20:22:00 UTC (rev 10317) @@ -1,11 +1,11 @@ Name: Combinatorics Version: 1.0.9 Date: 2009-05-18 -Author: Torsten Finke <fi...@ig...> -Maintainer: Torsten Finke <fi...@ig...> +Author: various authors +Maintainer: Octave-Forge community <oct...@li...> Title: Combinatorics. Description: Combinatorics functions, incuding partitioning. -Depends: octave (>= 2.9.7) +Depends: specfun (>= 1.2.0), miscellaneous (>= 1.2.0) Autoload: no License: GPLv3+ Url: http://octave.sf.net Deleted: trunk/octave-forge/main/combinatorics/INDEX =================================================================== --- trunk/octave-forge/main/combinatorics/INDEX 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/combinatorics/INDEX 2012-04-23 20:22:00 UTC (rev 10317) @@ -1,5 +0,0 @@ -combinatorics >> Combinatorics -Partitions - partint - partcnt - combs Modified: trunk/octave-forge/main/combinatorics/NEWS =================================================================== --- trunk/octave-forge/main/combinatorics/NEWS 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/combinatorics/NEWS 2012-04-23 20:22:00 UTC (rev 10317) @@ -1,4 +1,20 @@ Summary of important user-visible changes for combinatorics 2.0.0: ------------------------------------------------------------------- + ** VERY IMPORTANT: the combinatorics package has been removed. Its + integer partition functions have moved to miscellaneous while + `combs' has been moved to the specfun package. To avoid transition + problems, this new release is merely a dummy package with no functions, + and dependent on the new version of the miscellaneous and specfun + packages. + + ** The function `combs' (now part of the specfun package) has been + deprecated in favour of `nchoosek' from Octave-core which should + perform faster. The only difference is that it does accept string + arrays (which does not make a lot of sense in the first place). To + workaround this, the following can be used: + + char (nchoosek (double (n_string), k)) + ** Package is no longer automatically loaded. + Deleted: trunk/octave-forge/main/combinatorics/PKG_ADD =================================================================== --- trunk/octave-forge/main/combinatorics/PKG_ADD 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/combinatorics/PKG_ADD 2012-04-23 20:22:00 UTC (rev 10317) @@ -1 +0,0 @@ -autoload ("partcnt", fullfile (fileparts (mfilename ("fullpath")), "partint.oct")); Deleted: trunk/octave-forge/main/combinatorics/inst/combs.m =================================================================== --- trunk/octave-forge/main/combinatorics/inst/combs.m 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/combinatorics/inst/combs.m 2012-04-23 20:22:00 UTC (rev 10317) @@ -1,98 +0,0 @@ -## Copyright (C) 2007 Muthiah Annamalai <mut...@ut...> -## -## This program is free software; you can redistribute it and/or modify it under -## the terms of the GNU General Public License as published by the Free Software -## Foundation; either version 3 of the License, or (at your option) any later -## version. -## -## This program is distributed in the hope that it will be useful, but WITHOUT -## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or -## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more -## details. -## -## You should have received a copy of the GNU General Public License along with -## this program; if not, see <http://www.gnu.org/licenses/>. - -## -*- texinfo -*- -## @deftypefn {Function File} @var{rval}= {} combs(@var{sym_set},@var{k}) -## Function generates the nchoosek(N,K) combinations, and returns it. -## compute the combinations nchoosek(length(@var{sym_set}), @var{k}) -## nchoosek() is a much faster variant of this function. -## @example -## @group -## -## combs([1,2,3],2) -## ##returns value [1 2; 1 3; 2 3] -## -## combs(['a','e','i','o','u'],2) -## ##returns value [['a', 'e']; ['a', 'i']; ['a','o']; ['a','u']; ['e', 'i']; -## ##['e','o']; ['e','u']; ['i','o']; ['i','u']; ['o', 'u'];] -## -## @end group -## @end example -## @end deftypefn -## @seealso {perms, nchoosek} - -## -## Code modified from answer by 'leapinglizard-ga' on -## Google Answers, posted on 01 Sep 2004 09:13 PDT, -## - -function L=combs(Set,K) - if ( nargin < 2 ) - print_usage() - end - - N=length(Set); - %%printf("# of combinations = %g\n",nchoosek(N,K)) - L=comb_worker(K,1,Set,[],true); - return -end - -## -## sub-function -## -function L=comb_worker(K,P,Set,combo,is_first) - persistent N - persistent Result - persistent count - - L={}; - - if isempty(N) - N=length(Set); - end - - if isempty(Result) - Result=[]; - end - - if (K == 0) - count=count+1; - Result=[Result; combo]; - %%combo; - return - else - for idx=P:N - C=Set(idx); - combo=[combo C]; - comb_worker(K-1,idx+1,Set,combo,false); - combo=combo(1:end-1); - end - - if ( is_first > 0 ) - L=Result; - - %reset - N=[]; - Result=[]; - count=[]; - - return - end - - return - end -end - -%!assert(combs([1,2,3],2),[1 2; 1 3; 2 3]) Added: trunk/octave-forge/main/combinatorics/inst/dummy =================================================================== --- trunk/octave-forge/main/combinatorics/inst/dummy (rev 0) +++ trunk/octave-forge/main/combinatorics/inst/dummy 2012-04-23 20:22:00 UTC (rev 10317) @@ -0,0 +1,2 @@ +## pkg install does not allow dummy packages (without files). This ensures +## that the package is installed without polluting the user's namespace Modified: trunk/octave-forge/main/miscellaneous/INDEX =================================================================== --- trunk/octave-forge/main/miscellaneous/INDEX 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/miscellaneous/INDEX 2012-04-23 20:22:00 UTC (rev 10317) @@ -19,6 +19,8 @@ normr nze partarray + partcnt + partint peano_curve publish read_options Modified: trunk/octave-forge/main/miscellaneous/NEWS =================================================================== --- trunk/octave-forge/main/miscellaneous/NEWS 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/miscellaneous/NEWS 2012-04-23 20:22:00 UTC (rev 10317) @@ -6,6 +6,12 @@ ** New functions: truncate.m : truncates a number to a given precision. + ** The following functions have been imported from the combinatorics + package which has been removed: + + partcnt partint + + =============================================================================== miscellaneous-1.1.0 Release Date: 2012-03-24 Release Manager: =============================================================================== Copied: trunk/octave-forge/main/miscellaneous/PKG_ADD (from rev 10314, trunk/octave-forge/main/combinatorics/PKG_ADD) =================================================================== --- trunk/octave-forge/main/miscellaneous/PKG_ADD (rev 0) +++ trunk/octave-forge/main/miscellaneous/PKG_ADD 2012-04-23 20:22:00 UTC (rev 10317) @@ -0,0 +1 @@ +autoload ("partcnt", fullfile (fileparts (mfilename ("fullpath")), "partint.oct")); Modified: trunk/octave-forge/main/miscellaneous/src/Makefile =================================================================== --- trunk/octave-forge/main/miscellaneous/src/Makefile 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/miscellaneous/src/Makefile 2012-04-23 20:22:00 UTC (rev 10317) @@ -1,7 +1,9 @@ -all: cell2cell.oct partarray.oct sample.oct text_waitbar.oct - MKOCTFILE = mkoctfile -Wall +PROGS = $(patsubst %.cc,%.oct,$(wildcard *.cc)) + +all: $(PROGS) + %.oct: %.cc $(MKOCTFILE) $< Copied: trunk/octave-forge/main/miscellaneous/src/partint.cc (from rev 10315, trunk/octave-forge/main/combinatorics/src/partint.cc) =================================================================== --- trunk/octave-forge/main/miscellaneous/src/partint.cc (rev 0) +++ trunk/octave-forge/main/miscellaneous/src/partint.cc 2012-04-23 20:22:00 UTC (rev 10317) @@ -0,0 +1,225 @@ +// Copyright (C) 2006 Torsten Finke <fi...@ig...> +// +// This program is free software; you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free Software +// Foundation; either version 3 of the License, or (at your option) any later +// version. +// +// This program is distributed in the hope that it will be useful, but WITHOUT +// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +// details. +// +// You should have received a copy of the GNU General Public License along with +// this program; if not, see <http://www.gnu.org/licenses/>. + +#include <octave/oct.h> +#include <octave/lo-ieee.h> + +#include "partint.h" + +unsigned long * pcnt(unsigned long n) +{ + unsigned long *s = new unsigned long[n]; + unsigned long *x = new unsigned long[n*n]; + unsigned long **p = new unsigned long*[n]; + for (unsigned long k=0; k<n; ++k) { + p[k] = x + (k*n); + s[k] = 0; + } + for (unsigned long k=0; k<n*n; ++k) x[k] = 0; + p[0][0] = 1; + for (unsigned long k=1; k<n; ++k) + { + // p[N][j] == numpart of N with max summand j + for (unsigned long j=1; j<=k; ++j) { + p[k][j] = p[k-1][j-1] + p[k-j][j]; + } + for (unsigned long j=1; j<=k; ++j) { + s[k] += p[k][j]; // S(k) = numpart(n) + } + } + return s; +} + +DEFUN_DLD (partcnt, args, , +"-*- texinfo -*-\n\ +@deftypefn{Loadable Function} {@var{p} =} partcnt(@var{n})\n\ +\n\ +@cindex partition count\n\ +\n\ +Calculate integer partition count. Argument @var{n} be scalar, vector\n\ +or matrix of non-negative numbers. A partition is the sum decomposition \n\ +of integers. \n\ +\n\ +Example:\n\ +@example \n\ +partcnt([1, 5; 17 -3])\n\ +@end example\n\ +@noindent\n\ +returns\n\ +@example\n\ +ans =\n\ + 1 7\n\ + 297 NaN\n\ +@end example\n\ +\n\ +Reference:\n\ +Joerg Arndt: Algorithms for programmers (http://www.jjj.de), 2006.\n\n\ +@end deftypefn\n\ +@seealso{partint}\n\ +") +{ + octave_value r; + + int nargin = args.length (); + if (nargin != 1) { + error("partcnt accepts exactly one argument"); + return r; + } + if ( ! args(0).is_numeric_type()) { + error("partcnt only accepts a numeric argument"); + return r; + } + + NDArray f(args(0).matrix_value()); + RowVector m(f.max()); + double mmax = m.max(); + if ( mmax < 1 ) { + error("partcnt is only defined for non-negative arguments"); + return r; + } + + unsigned long n = (unsigned long) mmax + 1; + unsigned long *s = pcnt(n); + unsigned long fr = (unsigned long) f.rows(); + unsigned long fc = (unsigned long) f.columns(); + for (unsigned long i=0; i<fr; i++) { + for (unsigned long k=0; k<fc; k++) { + unsigned long idx = (unsigned long) f(i, k); + if (0 < idx && idx < n) { + f(i, k) = s[idx]; + } else { + f(i, k) = lo_ieee_nan_value(); + } + } + } + r = f; + return r; +} + +/* + +%!assert(partcnt(1), 1); +%!assert(partcnt(17), 297); +%!fail("partcnt()", "partcnt"); +%!fail("partcnt(1,2)", "partcnt"); +%!fail("partcnt('xyz')", "partcnt"); +%!demo +%! p = partcnt([1, 5; 17 -5]) + +*/ + +DEFUN_DLD (partint, args, , +"-*- texinfo -*-\n\ +@deftypefn{Loadable Function} {@var{p} =} partint(@var{n})\n\ +\n\ +@cindex partition\n\ +\n\ +Calculate all integer partitions. Argument @var{n} be \n\ +a positive number. A partition is the sum decomposition \n\ +of integers. \n\ +\n\ +Example:\n\ +@example \n\ +partint(4)\n\ +@end example\n\ +@noindent\n\ +returns\n\ +@example\n\ +ans =\n\ + 4 0 0 0\n\ + 2 1 0 0\n\ + 0 2 0 0\n\ + 1 0 1 0\n\ + 0 0 0 1\n\ +@end example\n\ +\n\ +This means\n\n\ +@iftex\n\ +@tex\n\ +$$\eqalign{4 & = 4 \\cdot 1 \\cr\n\ + & = 2 \\cdot 1 + 1 \\cdot 2 \\cr\n\ + & = 2 \\cdot 2 \\cr\n\ + & = 1 \\cdot 1 + 1 \\cdot 3 \\cr\n\ + & = 1 \\cdot 1 \\cr\n\ +\\cr}$$\n\ +@end tex\n\ +@end iftex\n\ +@ifinfo\n\ +@example\n\ +4 = 4 * 1\n\ + = 2 * 1 + 1 * 2\n\ + = 2 * 2\n\ + = 1 * 1 + 1 * 3\n\ + = 1 * 4\n\ +@end example\n\ +@end ifinfo\n\ +\n\ +Note:\n\ +\n\ +partint(n) * [1:n]' == n\n\ +\n\ +Reference:\n\ +Joerg Arndt: Algorithms for programmers (http://www.jjj.de), 2006.\n\n\ +@end deftypefn\n\ +@seealso{partcnt}\n\ +") +{ + octave_value r; + + int nargin = args.length (); + if (nargin != 1 || + ! args(0).is_scalar_type() || + ! args(0).is_numeric_type() + ) { + error("partint only accepts one scalar positive integer argument"); + return r; + } + double arg0 = args(0).double_value(); + if ( arg0 < 1 ) { + error("partint is only defined for positive integer arguments"); + return r; + } + + unsigned long n = (unsigned long) arg0; + unsigned long *s = pcnt(n+1); + unsigned long k = s[n]; + Matrix pa(k, n, 0); + int_partition p(n); + unsigned long i = 0; + do { + const unsigned long *d = p.data(); + for (unsigned long j=0; j<n; j++) { + pa(i, j) = (unsigned long)d[j+1]; + } + i ++; + } while (p.next()); + r = pa; + return r; +} + +/* + +%!assert(partint(1), 1); +%!assert(all(partint(n=17) * [1:n]' == n) - 1, 0); +%!test +%! expected = [4,0,0,0; 2,1,0,0; 0,2,0,0; 1,0,1,0; 0,0,0,1]; +%! assert(partint(4), expected); +%!fail("partint()", "partint"); +%!fail("partint(1,2)", "partint"); +%!fail("partint('xyz')", "partint"); +%!demo +%! p = partint(4) + +*/ Copied: trunk/octave-forge/main/miscellaneous/src/partint.h (from rev 10315, trunk/octave-forge/main/combinatorics/src/partint.h) =================================================================== --- trunk/octave-forge/main/miscellaneous/src/partint.h (rev 0) +++ trunk/octave-forge/main/miscellaneous/src/partint.h 2012-04-23 20:22:00 UTC (rev 10317) @@ -0,0 +1,78 @@ +// Copyright (C) 2006 Torsten Finke <fi...@ig...> +// +// This program is free software; you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free Software +// Foundation; either version 3 of the License, or (at your option) any later +// version. +// +// This program is distributed in the hope that it will be useful, but WITHOUT +// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +// details. +// +// You should have received a copy of the GNU General Public License along with +// this program; if not, see <http://www.gnu.org/licenses/>. + +class int_partition +// Integer partitions +// Reference: +// Joerg Arndt: Algorithms for programmers +// (http://www.jjj.de), 2006. +{ +private: + unsigned long *c_; // partition: c[1]* 1 + c[2]* 2 + ... + c[n]* n == n + unsigned long *s_; // cumulative sums: s[j+1] = c[1]* 1 + c[2]* 2 + ... + c[j]* j + unsigned long n_; // partitions of n + +public: + int_partition(unsigned long n) + { + n_ = n; + c_ = new unsigned long[n+1]; + s_ = new unsigned long[n+1]; + s_[0] = 0; // unused + c_[0] = 0; // unused + first(); + } + + ~int_partition() + { + delete [] c_; + delete [] s_; + } + + void first() + { + c_[1] = n_; + for (unsigned long i=2; i<=n_; i++) { c_[i] = 0; } + s_[1] = 0; + for (unsigned long i=2; i<=n_; i++) { s_[i] = n_; } + } + + const unsigned long *data() const { return c_; } // one-based! + + bool next() + { + // This algorithm was given by Torsten Finke + if ( c_[n_]!=0 ) return false; // last == 1* n (c[n]==1) + + // Find first coefficient c[i], i>=2 that can be increased: + unsigned long i = 2; + while ( s_[i]<i ) ++i; + + ++c_[i]; + s_[i] -= i; + unsigned long z = s_[i]; + // Now set c[1], c[2], ..., c[i-1] to the first partition + // of z into i-1 parts, i.e. set to z, 0, 0, ..., 0: + while ( --i > 1 ) + { + s_[i] = z; + c_[i] = 0; + } + c_[1] = z; // z* 1 == z + // s_[1] unused + + return true; + } +}; Modified: trunk/octave-forge/main/specfun/NEWS =================================================================== --- trunk/octave-forge/main/specfun/NEWS 2012-04-23 19:55:13 UTC (rev 10316) +++ trunk/octave-forge/main/specfun/NEWS 2012-04-23 20:22:00 UTC (rev 10317) @@ -5,6 +5,13 @@ big_factorial lfactorial + ** The function `combs' (just imported from the combinatorics package) + has been deprecated in favour of `nchoosek' from Octave-core which + should perform faster. The only difference is that it does accept + string arrays (which does not make a lot of sense in the first place). + To workaround this, the following can be used: + + char (nchoosek (double (n_string), k)) Summary of important user-visible changes for specfun 1.1.0: ------------------------------------------------------------------- Copied: trunk/octave-forge/main/specfun/inst/combs.m (from rev 10315, trunk/octave-forge/main/combinatorics/inst/combs.m) =================================================================== --- trunk/octave-forge/main/specfun/inst/combs.m (rev 0) +++ trunk/octave-forge/main/specfun/inst/combs.m 2012-04-23 20:22:00 UTC (rev 10317) @@ -0,0 +1,105 @@ +## Copyright (C) 2007 Muthiah Annamalai <mut...@ut...> +## +## This program is free software; you can redistribute it and/or modify it under +## the terms of the GNU General Public License as published by the Free Software +## Foundation; either version 3 of the License, or (at your option) any later +## version. +## +## This program is distributed in the hope that it will be useful, but WITHOUT +## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +## FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +## details. +## +## You should have received a copy of the GNU General Public License along with +## this program; if not, see <http://www.gnu.org/licenses/>. + +## -*- texinfo -*- +## @deftypefn {Function File} @var{rval}= {} combs(@var{sym_set},@var{k}) +## Function generates the nchoosek(N,K) combinations, and returns it. +## compute the combinations nchoosek(length(@var{sym_set}), @var{k}) +## nchoosek() is a much faster variant of this function. +## @example +## @group +## +## combs([1,2,3],2) +## ##returns value [1 2; 1 3; 2 3] +## +## combs(['a','e','i','o','u'],2) +## ##returns value [['a', 'e']; ['a', 'i']; ['a','o']; ['a','u']; ['e', 'i']; +## ##['e','o']; ['e','u']; ['i','o']; ['i','u']; ['o', 'u'];] +## +## @end group +## @end example +## @end deftypefn +## @seealso {perms, nchoosek} + +## +## Code modified from answer by 'leapinglizard-ga' on +## Google Answers, posted on 01 Sep 2004 09:13 PDT, +## + +function L=combs(Set,K) + persistent warned = false; + if (! warned) + warned = true; + warning ("Octave:deprecated-function", + "`combs' has been deprecated in favor of `nchoosek'. This function will be removed from future versions of the `specfun' package"); + endif + + if ( nargin < 2 ) + print_usage() + end + + N=length(Set); + %%printf("# of combinations = %g\n",nchoosek(N,K)) + L=comb_worker(K,1,Set,[],true); + return +end + +## +## sub-function +## +function L=comb_worker(K,P,Set,combo,is_first) + persistent N + persistent Result + persistent count + + L={}; + + if isempty(N) + N=length(Set); + end + + if isempty(Result) + Result=[]; + end + + if (K == 0) + count=count+1; + Result=[Result; combo]; + %%combo; + return + else + for idx=P:N + C=Set(idx); + combo=[combo C]; + comb_worker(K-1,idx+1,Set,combo,false); + combo=combo(1:end-1); + end + + if ( is_first > 0 ) + L=Result; + + %reset + N=[]; + Result=[]; + count=[]; + + return + end + + return + end +end + +%!assert(combs([1,2,3],2),[1 2; 1 3; 2 3]) This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |