Generating combinations under certain constraints
2 views (last 30 days)
Show older comments
I have 5 variables x1,x2,x3,x4 and x5. each is a 4x1 column vector and I want to generate a matrix that holds the different possible combinations of these 5 variables such that the sum of their product(x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) is less than 10. the elements of the 5 variables x are non-negative integers.
11 Comments
John D'Errico
on 8 Mar 2015
Not yet. You need to clarify if order matters. Thus, suppose we find a solution
{x1,x2,x3,x4,x5}
then is the set
{x2,x1,x3,x4,x5}
a different solution?
Accepted Answer
Matt J
on 8 Mar 2015
Edited: Matt J
on 8 Mar 2015
It might be helpful to recognize that the problem is equivalent simply to selecting a sequence of 20 square integers. Because of your constraints, the set of square integers you can choose from are {0,1,4,9}. There are only about 7 ways the non-zero square integers can be distributed disregarding order,
- 9
- 9 1
- 4 4
- 4 4 1
- 4 4 1 1
- One 4 and up to 6 ones
- Up to 10 ones
It should be a simple matter to use nchoosek() to identify all the possible selections for each case.
3 Comments
Matt J
on 9 Mar 2015
Edited: Matt J
on 9 Mar 2015
Your constraint is a sum of squares
sum_k X(k).^2 <=10
where X=[x1;x2;x3;x4;x5] is the vector you get from concatenating all your x_j vectors. We have therefore rewritten the problem in terms of new variables s(k) = X(k).^2, k=1...20. The new variables s(k) can only have values that are squared integers {0,1,4,9}.
Once you have solved in terms of s, you can always convert back to X later.
More Answers (2)
Guillaume
on 8 Mar 2015
Here is one way to try the brute force approach:
allx = {x1, x2, x3, x4, x5);
sumprodofset = @(cx) sum(cellfun(@(x) x' * x, cx));
combinations = num2cell(logical(dec2bin(1:2^numel(allx)-1, numel(allx)) - '0'), 2);
combsum = cellfun(@(c) sumprodofset(allx(c)), combinations);
validcombtf = combinations(combsum < 10)
Not sure what you want as an output, maybe this:
validcombx = cellfun(@(v) cell2mat(allx(v)), validcombtf, 'UniformOutput', false)
Or this:
valicombtf = cell2mat(validcombtf);
John D'Errico
on 8 Mar 2015
Edited: John D'Errico
on 8 Mar 2015
There are a fair number of possible solutions, depending on the answers to my questions. We can view the solution in a simple way, regardless. Your clarification of my questions will impact the possible set of solutions.
View this problem as the sum of squares of 20 non-negative integers, such that the sum is no greater than 10. There are only a very restricted set of possibilities we can have for that solution. We can worry about how those integers will be distributed among the vectors afterwards.
So essentially, this problem reduces initially to the set of partitions of the integers 0:10, as a sum of the integers {0,1,4,9}. I'll write that sum in terms of the multiplicity of each square in the sum, where the total multiplicity is exactly 20. So we can have many solutions. Here are a few:
20*0, 19*0+1, 18*0+2*1, ... , 18*0+1*1+1*9.
It looks like there are 23 such fundamental ways we can write the integers 0:10 as such a sum of squares of exactly 20 integers.
Now, for each of those 23 fundamental partitions, now you need only see how the non-zero elements can be distributed among the 5 distinct vectors, and you are done.
0 Comments
See Also
Categories
Find more on Elementary Math in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!