Generating combinations under certain constraints

8 次查看（过去 30 天）
Amira Akra
Amira Akra 2015-3-8
评论： Amira Akra 2015-3-9
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 个评论
显示 9更早的评论
John D'Errico
John D'Errico 2015-3-8
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?
Amira Akra
Amira Akra 2015-3-8
编辑：Amira Akra 2015-3-8
@John D'Errico no, they should remain in the same order
1) x1=[0 1 0 0]', x2=[0 0 0 0]',x3=[0 0 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =1 <10
2) x1=[1 0 0 0]', x2=[1 0 0 0]',x3=[0 0 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =1<10
3) x1=[1 1 1 1]', x2=[1 1 1 1]',x3=[0 0 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =8<10
4)x1=[1 1 1 1]', x2=[1 1 1 1]',x3=[0 1 0 0]',x4=[0 0 0 0]' and x5=[0 0 0 0]' since (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) =9<10
and so on....I want to generate all the possible values of x1 till x5 that will satisfy this mechanism.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2015-3-8
编辑：Matt J 2015-3-8
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 个评论
显示 1更早的评论
Matt J
Matt J 2015-3-9
编辑：Matt J 2015-3-9
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.
Amira Akra
Amira Akra 2015-3-9
ok that was very helpful..Thank you! one last question please, if i changed the threshold, i can still follow the same method,right?

请先登录，再进行评论。

更多回答（2 个）

Guillaume
Guillaume 2015-3-8
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
John D'Errico 2015-3-8
编辑：John D'Errico 2015-3-8
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.

类别

在 Help Center 和 File Exchange 中查找有关 Numerical Integration and Differentiation 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by