Generating combinations under certain constraints

2015 3 8
3 个回答
回答已采纳
更新时间：2015 3 9
7 次查看（30 天）

0 个投票

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更早的评论 隐藏 9更早的评论

Matt J
Matt J 2015-3-8
It's impossible as currently stated. The minimum value of the sum is 20, attained when all x1(i)...x5(i)=1.
Amira Akra
Amira Akra 2015-3-8
Why is that? the values can be 0, so if i have one 1 in each variable, I can get a minimum of 4...right?
Guillaume
Guillaume 2015-3-8
编辑：Guillaume 2015-3-8
positive normally means greater than zero. non negative would be a more appropriate term if your integers can be 0.
John D'Errico
John D'Errico 2015-3-8
Um, you state in one place that the values can be as small as zero, in another place that they be positive integers. Which is it?
John D'Errico
John D'Errico 2015-3-8
编辑：John D'Errico 2015-3-8
Matt's question is a valid one though. If x1 is a POSITIVE integer vector of length 4, as is x2, x3, etc., then
x1'*x1 = sum(x1.^2)
has a minimum value of 4.
The sum of 5 such terms has a minimum value of 20.
To quote your own explanation...
"the elements of the 5 variables x are positive integers."
So you need either to explain the problem more clearly, or accept that it cannot be solved as such.
Amira Akra
Amira Akra 2015-3-8
编辑：Amira Akra 2015-3-8
ok. what if x1=[0 1 0 0]', x2=[0 0 0 0]',x3=[0 0 0 0]',x4=[1 0 0 0]' and x5=[0 0 0 0]'? this will give 8..are there any possibilities than these?
Image Analyst
Image Analyst 2015-3-8
OK, so zero is allowed. But for a given set of x, (x1'*x1 +x2'*x2+ x3'*x3 +x4'*x4+ x5'*x5) is a single number. So what do you mean by "combinations" ? Do you mean like x1 might be multiplied by x3 sometimes and x2 other times? Also, what is the use case for this? In other words, why do you need it?
Amira Akra
Amira Akra 2015-3-8
@Image Analyst : I am trying to write an optimization problem with constraints and i need to test all possibilities. one of these constraints is related to my question.
regarding what I mean with combination: x1=[0 1 0 0]', x2=[0 0 0 0]',x3=[0 0 0 0]',x4=[1 0 0 0]' and x5=[0 0 0 0]' is a possible combination between the 5 variables. changinf the values of the variables will provide another combination and so on.... hope this clarifies it??
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

0 个投票

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更早的评论 隐藏 1更早的评论

Amira Akra
Amira Akra 2015-3-9
why is 2 not included in the set? If i have one of the variables, let us say x1=[1 1 0 0], then x1'*x1 = 2?
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

1 个投票

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

0 个投票

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.

类别

在 帮助中心 和 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