octave_packages/m/set/powerset.m

   1 ## Copyright (C) 2010-2012 Jaroslav Hajek
   2 ##
   3 ## This file is part of Octave.
   4 ##
   5 ## Octave is free software; you can redistribute it and/or modify it
   6 ## under the terms of the GNU General Public License as published by
   7 ## the Free Software Foundation; either version 3 of the License, or (at
   8 ## your option) any later version.
   9 ##
  10 ## Octave is distributed in the hope that it will be useful, but
  11 ## WITHOUT ANY WARRANTY; without even the implied warranty of
  12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 ## General Public License for more details.
  14 ##
  15 ## You should have received a copy of the GNU General Public License
  16 ## along with Octave; see the file COPYING.  If not, see
  17 ## <http://www.gnu.org/licenses/>.
  18
  19 ## -*- texinfo -*-
  20 ## @deftypefn  {Function File} {} powerset (@var{a})
  21 ## @deftypefnx {Function File} {} powerset (@var{a}, "rows")
  22 ##
  23 ## Return a cell array containing all subsets of the set @var{a}.
  24 ##
  25 ## @end deftypefn
  26 ## @seealso{unique, union, setxor, setdiff, ismember}
  27
  28 function p = powerset (a, byrows_arg)
  29
  30   byrows = false;
  31
  32   if (nargin == 2)
  33     if (! strcmpi (byrows_arg, "rows"))
  34       error ('powerset: expecting third argument to be "rows"');
  35     elseif (iscell (a))
  36       warning ('powerset: "rows" not valid for cell arrays');
  37     else
  38       byrows = true;
  39     endif
  40   elseif (nargin != 1)
  41     print_usage ();
  42   endif
  43
  44   if (byrows)
  45     a = unique (a, byrows_arg);
  46     n = rows (a);
  47   else
  48     a = unique (a);
  49     n = numel (a);
  50   endif
  51
  52   if (n == 0)
  53     p = [];
  54   else
  55     if (n > 32)
  56       error ("powerset: not implemented for more than 32 elements");
  57     endif
  58
  59     ## Logical rep
  60     b = reshape (bitunpack (uint32 (0:2^n-1)), 32, 2^n)(1:n,:);
  61     ## Convert to indices and lengths.
  62     [i, k] = find (b);
  63     k = sum (b, 1);
  64
  65     ## Index and split.
  66     if (byrows)
  67       p = mat2cell (a(i,:), k, columns (a));
  68     else
  69       if (rows (a) == 1)
  70         p = mat2cell (a(i), 1, k);
  71       else
  72         p = mat2cell (a(i), k, 1);
  73       endif
  74     endif
  75   endif
  76
  77 endfunction
  78
  79
  80 %!test
  81 %! c = sort (cellstr ({ [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]}));
  82 %! p = sort (cellstr (powerset ([1, 2, 3])));
  83 %! assert (p, c);