Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to generate discrete combinations with fixed sum?

Subject: How to generate discrete combinations with fixed sum?

From: Jose

Date: 21 Sep, 2010 16:33:33

Message: 1 of 8

Good afternoon,

I am hoping someone in the community may be able to help me out with my problem.
I am using Matlab to generate combinations with constraints, as follows:

I have a fixed value, let's say 156, that I want to distribute amongst 20 slots in packages of 4. For each problem, I define the following constraints:
- the possible slots (out of the 20) amongst which these 156 may be distributed;
- the minimum amount of load on each slot
- the maximum amount of load on each slot

The problem is that I tried to generate all possible alternatives, then eliminate those that do not comply with the constraints. However, I get the OUT OF MEMORY error, so I really have to find a more efficient way of doing this.

Appreciate any kind of help!

Thanks,

JCF

Subject: How to generate discrete combinations with fixed sum?

From: Ross W

Date: 21 Sep, 2010 20:36:07

Message: 2 of 8

"Jose " <zeca_ferrao@hotmail.com> wrote in message <i7amot$s7$1@fred.mathworks.com>...
> Good afternoon,
>
> I am hoping someone in the community may be able to help me out with my problem.
> I am using Matlab to generate combinations with constraints, as follows:
>
> I have a fixed value, let's say 156, that I want to distribute amongst 20 slots in packages of 4. For each problem, I define the following constraints:
> - the possible slots (out of the 20) amongst which these 156 may be distributed;
> - the minimum amount of load on each slot
> - the maximum amount of load on each slot
>
> The problem is that I tried to generate all possible alternatives, then eliminate those that do not comply with the constraints. However, I get the OUT OF MEMORY error, so I really have to find a more efficient way of doing this.
>
> Appreciate any kind of help!
>
> Thanks,
>
> JCF

The query isn't clear to me. What is a package? What is load?

Might help to show a few acceptable and unacceptable combinations

Ross

Subject: How to generate discrete combinations with fixed sum?

From: Jose

Date: 21 Sep, 2010 22:37:03

Message: 3 of 8


>
> The query isn't clear to me. What is a package? What is load?
>
> Might help to show a few acceptable and unacceptable combinations
>
> Ross

Ok, I'll try to explain it better.

I have 20 slots on which to distribute a given total load of 156 kg;
I have discretised my total load in packages of 4kg each;
I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
- some of the slots cannot be used (they are identified by numbers)
- some of the slots have a minimum value of load
- some of the slots have a maximum value of load;

Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
[2 2 2 2 2]
[4 0 2 2 2]
[4 0 0 4 2]

But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.

I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.

I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.

Thanks a lot for your help!

JCF

Subject: How to generate discrete combinations with fixed sum?

From: Sean

Date: 21 Sep, 2010 22:56:19

Message: 4 of 8

"Jose " <zeca_ferrao@hotmail.com> wrote in message <i7bc2f$qer$1@fred.mathworks.com>...
>
> >
> > The query isn't clear to me. What is a package? What is load?
> >
> > Might help to show a few acceptable and unacceptable combinations
> >
> > Ross
>
> Ok, I'll try to explain it better.
>
> I have 20 slots on which to distribute a given total load of 156 kg;
> I have discretised my total load in packages of 4kg each;
> I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
> - some of the slots cannot be used (they are identified by numbers)
> - some of the slots have a minimum value of load
> - some of the slots have a maximum value of load;
>
> Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
> [2 2 2 2 2]
> [4 0 2 2 2]
> [4 0 0 4 2]
>
> But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
> On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.
>
> I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.
>
> I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.
>

There are an infinite number of combinations that meet the constraints.

Subject: How to generate discrete combinations with fixed sum?

From: John D'Errico

Date: 21 Sep, 2010 22:58:04

Message: 5 of 8

"Jose " <zeca_ferrao@hotmail.com> wrote in message <i7bc2f$qer$1@fred.mathworks.com>...
>
> >
> > The query isn't clear to me. What is a package? What is load?
> >
> > Might help to show a few acceptable and unacceptable combinations
> >
> > Ross
>
> Ok, I'll try to explain it better.
>
> I have 20 slots on which to distribute a given total load of 156 kg;
> I have discretised my total load in packages of 4kg each;
> I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
> - some of the slots cannot be used (they are identified by numbers)
> - some of the slots have a minimum value of load
> - some of the slots have a maximum value of load;
>
> Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
> [2 2 2 2 2]
> [4 0 2 2 2]
> [4 0 0 4 2]
>
> But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
> On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.
>
> I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.
>
> I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.
>

You will quickly find that the number of combinations
is quite large. But it IS simply done recursively.

Look at the first slot. Assume that it can take any of
these loads.

0,2,4,6,8,10

Now, simply compute the possible combinations for the
other slots, given what remains to be distributed for
each of those possibilities. At some point, there is either
nothing left to be distributed, or more than the remaining
slots can carry. In either case, you are done with that
thread of the recursion.

Simple recursion.

John

Subject: How to generate discrete combinations with fixed sum?

From: Jose

Date: 21 Sep, 2010 23:11:05

Message: 6 of 8

>
> You will quickly find that the number of combinations
> is quite large. But it IS simply done recursively.
>
> Look at the first slot. Assume that it can take any of
> these loads.
>
> 0,2,4,6,8,10
>
> Now, simply compute the possible combinations for the
> other slots, given what remains to be distributed for
> each of those possibilities. At some point, there is either
> nothing left to be distributed, or more than the remaining
> slots can carry. In either case, you are done with that
> thread of the recursion.
>
> Simple recursion.
>
> John

Ok, I'll do it recursively, it should work.
Thanks a lot for your help, John.

JCF

Subject: How to generate discrete combinations with fixed sum?

From: Ross W

Date: 21 Sep, 2010 23:16:08

Message: 7 of 8

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <i7bd9s$eqv$1@fred.mathworks.com>...
> "Jose " <zeca_ferrao@hotmail.com> wrote in message <i7bc2f$qer$1@fred.mathworks.com>...
> >
> > >
> > > The query isn't clear to me. What is a package? What is load?
> > >
> > > Might help to show a few acceptable and unacceptable combinations
> > >
> > > Ross
> >
> > Ok, I'll try to explain it better.
> >
> > I have 20 slots on which to distribute a given total load of 156 kg;
> > I have discretised my total load in packages of 4kg each;
> > I want to obtain all the possible combinations of package distributions amongst the 20 slots, subject to the following constraints:
> > - some of the slots cannot be used (they are identified by numbers)
> > - some of the slots have a minimum value of load
> > - some of the slots have a maximum value of load;
> >
> > Ill give a rough example: imagine 5 slots on which I want to distribute 10 kg in packages of 2; some possible combinations without constraints) would be:
> > [2 2 2 2 2]
> > [4 0 2 2 2]
> > [4 0 0 4 2]
> >
> > But, if I define that slot nr 2 cannot receive load, then the option [2 2 2 2 2] would not be considered.
> > On the other hand, if I define that slot 4 cannot handle more than 2 kg, then option [4 0 0 4 2] would also be discarded.
> >
> > I think that the problem is not too complex, but the number of combinations that arise when working with 20 slots and more than 100 kg of load in small packages makes it impossible to calculate all the combinations and then eliminate the ones that do not comply with the constraints.
> >
> > I was hoping that there'd be a way of calculating just the combinations that satisfy the constraints.
> >
>
> You will quickly find that the number of combinations
> is quite large. But it IS simply done recursively.
>
> Look at the first slot. Assume that it can take any of
> these loads.
>
> 0,2,4,6,8,10
>
> Now, simply compute the possible combinations for the
> other slots, given what remains to be distributed for
> each of those possibilities. At some point, there is either
> nothing left to be distributed, or more than the remaining
> slots can carry. In either case, you are done with that
> thread of the recursion.
>
> Simple recursion.
>
> John

As I understand it, John's nice suggestion is related to an optimisation technique called dynamic programming, which the OP might like to read up on.

Dynamic programming could be used to search for an optimal assignment of packages to slots (e.g. most evenly balanced, or most profitable, or whatever objective function you want to use),

Ross

Subject: How to generate discrete combinations with fixed sum?

From: Bruno Luong

Date: 22 Sep, 2010 00:41:25

Message: 8 of 8

The function implemented here does something pretty close to what you asked
http://www.mathworks.com/matlabcentral/fileexchange/17818

You can use it as template to implement the recursive algorithm.

Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us