CODEWITHSUNDEEP
matlab
smyslov
smyslov

Reputation: 1275

Matlab get all possible combinations less than a value

I have a matrix as follows:

id      value
=============
 1       0.5
 2       0.5
 3       0.8
 4       0.3
 5       0.2

From this array, I wish to find all the possible combinations that have a sum less than or equal to 1. That is,

result
======
1 2
1 4 5
2 4 5
3 5
1 5
1 4
2 4
2 5
...

In order to get the above result, my idea has been to initially compute all the possibilities of finding sum of elements in the array, like so:

for ii = 1 : length(a) % compute number of possibilities 
     no_of_possibilities = no_of_possibilities + nchoosek(length(a),ii);
end

Once this is done, then loop through all possible combinations. I would like to know if there's an easier way of doing this.

Upvotes: 2

Views: 841

Answers (3)

user5128199
user5128199

Reputation:

Here is potential solution, using inefficient steps, but borrowing efficient code from various SO answers. Credit goes to those original peeps.

data = [0.5, 0.5, 0.8, 0.3, 0.2];

First get all combinations of indices, not necessarily using all values.

combs = bsxfun(@minus, nchoosek(1:numel(data)+numel(data)-1,numel(data)), 0:numel(data)-1);

Then get rid of repeated indices in each combination, regardless of index order

[ii, ~, vv] = find(sort(combs,2));
uniq = accumarray(ii(:), vv(:), [], @(x){unique(x.')});

Next get unique combinations, regardless of index order... NOTE: You can do this step much more efficiently by restructuring the steps, but it'll do.

B = cellfun(@mat2str,uniq,'uniformoutput',false);
[~,ia] = unique(B);
uniq=uniq(ia);

Now sum all values in data based on cell array (uniq) of index combinations

idx = cumsum(cellfun('length', uniq));
x = diff(bsxfun(@ge, [0; idx(:)], 1:max(idx)));
x = sum(bsxfun(@times, x', 1:numel(uniq)), 2);  %'// Produce subscripts
y = data([uniq{:}]);                               % // Obtain values
sums_data = accumarray(x, y);

And finally only keep the index combinations that sum to <= 1

allCombLessThanVal = uniq(sums_data<=1)

Upvotes: 0

OmG
OmG

Reputation: 18838

It is not in easy way, however is a faster way, as I removed the combination which its subsets are not passed the condition. 

bitNo = length(A);         % number of bits
setNo = 2 ^ bitNo - 1;     % number of sets
subsets = logical(dec2bin(0:setNo, bitNo) - '0'); % all subsets
subsets = subsets(2:end,:); % all subsets minus empty set!
subsetCounter = 1;
resultCounter = 1;
result = {};
while(1)
    if( subsetCounter >= size(subsets,1))
         break;
    end
    if(sum(A(subsets(subsetCounter,:).',2)) <= 1)
         result{resultCounter} = A(subsets(subsetCounter,:).',1).';
         resultCounter = resultCounter + 1;
         subsetCounter = subsetCounter + 1;
    else
         % remove all bad cases related to the current subset
         subsets = subsets(sum((subsets & subsets(subsetCounter,:)) - subsets(subsetCounter,:),2) ~= 0,:);
    end       
end

Generate the subsets using this method. After that, check the condition for each subset. If the subset does not pass the condition, all its supersets are removed from the subsets. To do this, using sum((subsets & subsets(i,:)) - subsets(i,:),2) ~= 0 which mean get some rows from subsets which has not the same elements of the not passed subset. By doing this, we able to not to consider some bad cases anymore. Although, theoretically, this code is Θ(2^n).

Upvotes: 1

ammportal
ammportal

Reputation: 991

data = [0.5, 0.5, 0.8, 0.3, 0.2];
required = cell(1, length(data));
subsets = cell(1, length(data));
for k = 2:length(data)-1 % removes trivial cases (all numbers or one number at a time)
    % generate all possible k-pairs (if k = 3, then all possible triplets
    % will be generated)
    combination = nchoosek(1:length(data), k);
    % for every triplet generated, this function sums the corresponding
    % values and then decides whether then sum is less than equal to 1 or
    % not
    findRequired = @(x) sum(data(1, combination(x, :))) <= 1;
    % generate a logical vector for all possible combinations like [0 1 0]
    % which denotes that the 2nd combination satisfies the condition while
    % the others do not
    required{k} = arrayfun(findRequired, 1:size(combination, 1));
    % access the corresponding combinations from the entire set
    subsets{k} = combination(required{k}, :);
end

This produces the following subsets:

1     2
1     4
1     5
2     4
2     5
3     5
4     5
1     4     5
2     4     5

Upvotes: 2

Related Questions