Mercurial > octave-nkf
changeset 9695:9fba7e1da785
correct algorithm for perm matrix det (sign)
| author | Jaroslav Hajek <highegg@gmail.com> |
|---|---|
| date | Mon, 05 Oct 2009 17:03:13 +0200 |
| parents | 50db3c5175b5 |
| children | 01a1fd9167e0 |
| files | liboctave/ChangeLog liboctave/PermMatrix.cc |
| diffstat | 2 files changed, 26 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/ChangeLog Mon Oct 05 15:39:44 2009 +0200 +++ b/liboctave/ChangeLog Mon Oct 05 17:03:13 2009 +0200 @@ -1,3 +1,8 @@ +2009-10-05 Jaroslav Hajek <highegg@gmail.com> + + * PermMatrix.cc (PermMatrix::determinant): Implement a (hopefully) + working algorithm. + 2009-10-05 Jaroslav Hajek <highegg@gmail.com> * dim-vector.h (operator ==): Include fast case.
--- a/liboctave/PermMatrix.cc Mon Oct 05 15:39:44 2009 +0200 +++ b/liboctave/PermMatrix.cc Mon Oct 05 17:03:13 2009 +0200 @@ -28,6 +28,7 @@ #include "idx-vector.h" #include "error.h" #include "Array-util.h" +#include "oct-locbuf.h" static void gripe_invalid_permutation (void) @@ -100,16 +101,30 @@ octave_idx_type PermMatrix::determinant (void) const { - Array<octave_idx_type> pa = *this; - octave_idx_type len = pa.length (), *p = pa.fortran_vec (); - bool neg = false; + // Determine the sign of a permutation in linear time. + // Is this widely known? + + octave_idx_type len = perm_length (); + const octave_idx_type *pa = data (); + + OCTAVE_LOCAL_BUFFER (octave_idx_type, p, len); + OCTAVE_LOCAL_BUFFER (octave_idx_type, q, len); + for (octave_idx_type i = 0; i < len; i++) { - octave_idx_type j = p[i]; + p[i] = pa[i]; + q[p[i]] = i; + } + + bool neg = false; + + for (octave_idx_type i = 0; i < len; i++) + { + octave_idx_type j = p[i], k = q[i]; if (j != i) { - p[i] = p[j]; - p[j] = j; + p[k] = p[i]; + q[j] = q[i]; neg = ! neg; } }