On Tue, 5 Jul 2005, Soren Hauberg wrote:
I can't seem to wrap my mind around a very simple problem.
I need to find all possible subsets of a set.
Example:
All possible subsets of
[1, 2, 3]
is
{ [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] }
Here is something that I wrote recently that is similar to what you're
wanting. You'd have to call it multiple times, but separating each row of:
a = combinations(3,1)
b = combinations(3,2)
c = combinations(3,3)
will give you the set you're wanting. It should be a trivial
modification to make it accept [1 2 3] instead of just 3 as the input set.
(Consider this code licensed under the GPL.)
Bill
------------------------------------------------------------------------
function result = combinations(n, multiple, varargin)
% result = combinations(n, multiple, <repeat>, <current>)
%
% make all pairs of n combinations with or without repeating patterns.
%
% n - the number of choices in the combination set (i.e. if there
% are 5 things to combine this would be 5).
% multiple - the number of choices to combine at once
% repeat - do we allow repetition within the pattern (i.e. is [1 1] a
% valid combindation?) set to 'repeat'
% current - (DO NOT USE) An internal variable to keep track of the current
% set of combinations.
if (length(varargin) >= 2)
if ischar(varargin{1})
repeats = varargin{1};
current = varargin{2};
else
repeats = '';
current = varargin{2};
end
elseif (length(varargin) == 1)
if ischar(varargin{1})
repeats = varargin{1};
current = [];
else
repeats = '';
current = varargin{1};
end
else
repeats = '';
current = [];
end
if (multiple <= 0)
result = current;
return;
end
if (n == multiple)
%FIXME there shouldn't really be a special case for n==multiple, but I
%don't feel like fixing it correctly.
result = 1:n;
return
elseif isempty(current)
multiple = multiple - 1;
if strcmpi(repeats, 'repeat')
result = [1:n]';
else
result = [1:n-multiple]';
end
else
multiple = multiple - 1;
result = [];
for i = 1:length(current)
startpoint = current(i,end) + 1;
if strcmpi(repeats, 'repeat')
startpoint = startpoint - 1;
end
for j = startpoint:n-multiple
result(end+1,:) = [current(i,:) j];
end
end
end
result = combinations(n, multiple, repeats, result);