octave_packages/m/specfun/perms.m

   1 ## Copyright (C) 2001-2012 Paul Kienzle
   2 ## Copyright (C) 2009 VZLU Prague
   3 ##
   4 ## This file is part of Octave.
   5 ##
   6 ## Octave is free software; you can redistribute it and/or modify it
   7 ## under the terms of the GNU General Public License as published by
   8 ## the Free Software Foundation; either version 3 of the License, or (at
   9 ## your option) any later version.
  10 ##
  11 ## Octave is distributed in the hope that it will be useful, but
  12 ## WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 ## General Public License for more details.
  15 ##
  16 ## You should have received a copy of the GNU General Public License
  17 ## along with Octave; see the file COPYING.  If not, see
  18 ## <http://www.gnu.org/licenses/>.
  19
  20 ## -*- texinfo -*-
  21 ## @deftypefn {Function File} {} perms (@var{v})
  22 ##
  23 ## Generate all permutations of @var{v}, one row per permutation.  The
  24 ## result has size @code{factorial (@var{n}) * @var{n}}, where @var{n}
  25 ## is the length of @var{v}.
  26 ##
  27 ## As an example, @code{perms([1, 2, 3])} returns the matrix
  28 ##
  29 ## @example
  30 ## @group
  31 ##   1   2   3
  32 ##   2   1   3
  33 ##   1   3   2
  34 ##   2   3   1
  35 ##   3   1   2
  36 ##   3   2   1
  37 ## @end group
  38 ## @end example
  39 ## @end deftypefn
  40
  41 function A = perms (v)
  42   if (nargin != 1)
  43     print_usage ();
  44   endif
  45   v = v(:);
  46   n = length (v);
  47
  48   if (n == 0)
  49     A = [];
  50   else
  51     A = v(1);
  52     for j = 2:n
  53       B = A;
  54       A = zeros (prod (2:j), n, class (v));
  55       k = size (B, 1);
  56       idx = 1:k;
  57       for i = j:-1:1
  58         A(idx,1:i-1) = B(:,1:i-1);
  59         A(idx,i) = v(j);
  60         A(idx,i+1:j) = B(:,i:j-1);
  61         idx += k;
  62       endfor
  63     endfor
  64   endif
  65 endfunction
  66
  67 %!error perms ();
  68 %!error perms (1, 2);
  69
  70 %!assert (perms ([1,2,3]), [1,2,3;2,1,3;1,3,2;2,3,1;3,1,2;3,2,1]);
  71 %!assert (perms (1:3), perms ([1,2,3]));
  72
  73 %!assert (perms (int8([1,2,3])), int8([1,2,3;2,1,3;1,3,2;2,3,1;3,1,2;3,2,1]));