Vec partitions

From QETLAB
Jump to: navigation, search
vec_partitions
Produces all possible partitions of a vector

Other toolboxes required none
Function category Helper functions
This is a helper function that only exists to aid other functions in QETLAB. If you are an end-user of QETLAB, you likely will never have a reason to use this function.

vec_partitions is a function that returns all partitions a given vector into a specified number of parts. Note that, for this function, the order of the parts does matter, but the order of the elements within the parts does not matter (for example, when partitioning the vector [1,2,3,4], the partition {[1],[2,3,4]} is the same as {[1],[3,2,4]}, but distinct from {[2,3,4],[1]}).

Syntax

  • PT = vec_partitions(V,P)
  • PT = vec_partitions(V,P,SZ)

Argument descriptions

  • V: A vector to be partitioned.
  • P: A positive integer: the number of parts to partition P into.
  • SZ (optional, default [1,1,...,1]): A vector such that only the partitions with the property that the j-th part contains at least SZ(j) elements (for all j) are returned.

Examples

The following code generates all 14 partitions of the vector [1,2,3,4] into two parts. It then displays two of those partitions (the first and sixth).

>> pt = vec_partitions(1:4,2);
>> length(pt)
 
ans =
 
    14
 
>> celldisp(pt{1})
 
ans{1} =
 
     1
 
 
 
ans{2} =
 
     2     3     4
 
 
>> celldisp(pt{6})
 
ans{1} =
 
     1     3
 
 
 
ans{2} =
 
     2     4

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

  1. %%  VEC_PARTITIONS    Produces all possible partitions of a vector
  2. %
  3. %   PT = vec_partitions(V,P,SZ) computes all partitions of the vector V
  4. %   into P parts. PT is a cell, each of whose entries is a 1-by-P cell
  5. %   containing the P different parts.
  6. %
  7. %   This function has one optional argument:
  8. %     SZ (default [1,1,...,1])
  9. %   
  10. %   PT = vec_partitions(V,P,SZ) computes all partitions of the vector V
  11. %   into P parts, with the restriction that, for all j, the j-th part must
  12. %   have at least SZ(j) elements.
  13. %
  14. %   URL: http://www.qetlab.com/vec_partitions
  15.  
  16. %   requires: opt_args.m
  17. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  18. %   package: QETLAB
  19. %   last updated: October 18, 2014
  20.  
  21. function pt = vec_partitions(v,p,varargin)
  22.  
  23. % set optional argument defaults: sz = [1,1,...,1]
  24. [sz] = opt_args({ ones(1,p) },varargin{:});
  25.  
  26. if(p > 1) % if p > 1 then we still have work to do
  27.     pt = cell(0);
  28.     ub = length(v) - sum(sz(2:end));
  29.     for jj = sz(1):ub
  30.         tpt = nchoosek(v,jj);
  31.         for kk = 1:size(tpt,1) % recurse through the other parties
  32.             tpt2 = vec_partitions(setdiff(v,tpt(kk,:)),p-1,sz(2:end));
  33.             for ll = 1:length(tpt2)
  34.                 pt{end+1} = {tpt(kk,:), tpt2{ll}{:}};
  35.             end
  36.         end
  37.     end
  38. else % we are on the last party: only one option left
  39.     pt{1}{1} = v;
  40. end