Got Questions? Get Answers.
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:
Balancing arrays matlab command

Subject: Balancing arrays matlab command

From: Mark

Date: 31 Jul, 2007 19:58:56

Message: 1 of 8

Hi,

I have 2 egg boxes. I note the weight of each egg as I place it a box. Once both boxes are full I want to find which eggs to swap to acheive the smallest difference in mass between boxes.

Are there Matlab commands that would help solve this problem?

Thanks.

Mark.

Subject: Balancing arrays matlab command

From: ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford)

Date: 1 Aug, 2007 00:16:37

Message: 2 of 8

In article <f8o4a0$mdp$1@fred.mathworks.com>, "Mark "
<medwar19.nospam@hotmail.com> wrote:

> Hi,
>
> I have 2 egg boxes. I note the weight of each egg as I place it a box.
Once both boxes are full I want to find which eggs to swap to acheive the
smallest difference in mass between boxes.
>
> Are there Matlab commands that would help solve this problem?
>
> Thanks.
> Mark.
---------------------
  It isn't clear to me how finding the smallest individual egg mass
difference between boxes will directly solve the problem of "balancing"
the two boxes. The best swapping might conceivably come from a number of
larger differences.

  However, as to finding the smallest difference, you could always compare
every possible pairing between eggs in the two boxes, which would be an
order n^2 algorithm. If the numbers of your eggs are very large, you
might want a faster algorithm method.

  One way is to do a sort on the combined egg weights and only compare
cases where an egg in one box is immediately followed weight-wise by an
egg of the other box. This constitutes an algorithm of order n*log(n)
instead. Let x be a row array of egg weights from the first box and y a
row array of egg weights in the second box. Do the following:

 m = size(x,2); n = size(y,2);
 [t,p] = sort([x,y]); % Sort the combined weights
 q = 1:m+n; q(p) = q; % Get the inverse of p
 u = zeros(1,m+n); % Put 0's where y-weights are located and
 u(q(1:m)) = 1; % 1's where x-weights are located in t
 f = find(diff(u)==-1); % Find where x-weights are followed by y-weights
 ix1 = p(f); iy1 = p(f+1)-m; % Get the corresponding indices in x and y
 g = find(diff(u)==1); % Find where y-weights are followed by x-weights
 ix2 = p(g+1); iy2 = p(g)-m; % Get corr. indices in x and y

The ix1 and iy1 arrays are indices of pairs of x and y weights in which
the x-weight immediately precedes the y-weight in order of the combined
ascending weights. With ix2 and iy2, it is the same except that the
y-weight immediately precedes the x-weight in size.

  If it is minimum absolute weight difference you seek, you could find it with

 min([y(iy1)-x(ix1),x(ix2)-y(iy2)]).

On the other hand if you are after, say, the smallest positive weight
difference between the y-weights and the x-weights - that is, the y-weight
is the larger - you would want

 min(y(iy1)-x(ix1)).

It all depends on what you want.

Roger Stafford

Subject: Balancing arrays matlab command

From: dpb

Date: 31 Jul, 2007 19:24:59

Message: 3 of 8

Mark wrote:
> Hi,
>
> I have 2 egg boxes. I note the weight of each egg as I place it a
> box.
Once both boxes are full I want to find which eggs to swap to acheive
the smallest difference in mass between boxes.
>
> Are there Matlab commands that would help solve this problem?

There are Matlab commands that will help solve virtually _any_ problem... :)

Interesting problem/question -- Roger has one approach, so I'll ask
about the constraints on the operation(s)...

Are you talking of swapping two only or more to achieve the smallest
difference?

I'm almost late to a committee/board meeting so don't have the time to
consider it more than the "passing fancy" thought, but is strikes me it
would be possible to select the carton during the loading based on
current conditions rather than wait until the end to try to balance the
end result...

--

Subject: Balancing arrays matlab command

From: Mark

Date: 1 Aug, 2007 13:04:40

Message: 4 of 8

ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford) wrote in message <ellieandrogerxyzzy-3107071716360001@dialup-4.232.15.222.dial1.losangeles1.level3.net>...
> In article <f8o4a0$mdp$1@fred.mathworks.com>, "Mark "
> <medwar19.nospam@hotmail.com> wrote:
>
> > Hi,
> >
> > I have 2 egg boxes. I note the weight of each egg as I place it a box.
> Once both boxes are full I want to find which eggs to swap to acheive the
> smallest difference in mass between boxes.
> >
> > Are there Matlab commands that would help solve this problem?
> >
> > Thanks.
> > Mark.
> ---------------------
> It isn't clear to me how finding the smallest individual egg mass
> difference between boxes will directly solve the problem of "balancing"
> the two boxes. The best swapping might conceivably come from a number of
> larger differences.
>
> However, as to finding the smallest difference, you could always compare
> every possible pairing between eggs in the two boxes, which would be an
> order n^2 algorithm. If the numbers of your eggs are very large, you
> might want a faster algorithm method.
>
> One way is to do a sort on the combined egg weights and only compare
> cases where an egg in one box is immediately followed weight-wise by an
> egg of the other box. This constitutes an algorithm of order n*log(n)
> instead. Let x be a row array of egg weights from the first box and y a
> row array of egg weights in the second box. Do the following:
>
> m = size(x,2); n = size(y,2);
> [t,p] = sort([x,y]); % Sort the combined weights
> q = 1:m+n; q(p) = q; % Get the inverse of p
> u = zeros(1,m+n); % Put 0's where y-weights are located and
> u(q(1:m)) = 1; % 1's where x-weights are located in t
> f = find(diff(u)==-1); % Find where x-weights are followed by y-weights
> ix1 = p(f); iy1 = p(f+1)-m; % Get the corresponding indices in x and y
> g = find(diff(u)==1); % Find where y-weights are followed by x-weights
> ix2 = p(g+1); iy2 = p(g)-m; % Get corr. indices in x and y
>
> The ix1 and iy1 arrays are indices of pairs of x and y weights in which
> the x-weight immediately precedes the y-weight in order of the combined
> ascending weights. With ix2 and iy2, it is the same except that the
> y-weight immediately precedes the x-weight in size.
>
> If it is minimum absolute weight difference you seek, you could find it with
>
> min([y(iy1)-x(ix1),x(ix2)-y(iy2)]).
>
> On the other hand if you are after, say, the smallest positive weight
> difference between the y-weights and the x-weights - that is, the y-weight
> is the larger - you would want
>
> min(y(iy1)-x(ix1)).
>
> It all depends on what you want.
>
> Roger Stafford

Hi Roger,

Thanks for that detailed thought process.

You were correct in your second case.

I aim is to balance full egg boxes within a tolerance.
The weight of each egg is only known after it is placed in a box (as the boxes are on a scale. Both boxes must be full (the same number of eggs) after we are finished loading and swopping eggs takes time so swapping should be minimized.

I started with the n^2 solution and thought there might be a matlab command for generating that matrix. I could then sort the matrix and see if any swap would take me within the tolerance.

It's a nice brain teaser!

Thanks,

Mark.

Subject: Balancing arrays matlab command

From: ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford)

Date: 1 Aug, 2007 08:29:13

Message: 5 of 8

In article <f8q0d8$g2d$1@fred.mathworks.com>, "Mark "
<medwar19.nospam@hotmail.com> wrote:

> Hi Roger,
>
> Thanks for that detailed thought process.
>
> You were correct in your second case.
>
> I aim is to balance full egg boxes within a tolerance.
> The weight of each egg is only known after it is placed in a box (as the
boxes are on a scale. Both boxes must be full (the same number of eggs)
after we are finished loading and swopping eggs takes time so swapping
should be minimized.
>
> I started with the n^2 solution and thought there might be a matlab
command for generating that matrix. I could then sort the matrix and see
if any swap would take me within the tolerance.
>
> It's a nice brain teaser!
>
> Thanks,
> Mark.
---------------------
  I should have read your original article more carefully, Mark. In my
haste, I misinterpreted the phrase, "which eggs to swap to acheive the
smallest difference in mass between boxes" to mean "between EGGS!", which
is what the code I described accomplishes. So toss out that code and
begin again.

  For your actual problem, let x and y again be row vectors of the two
sets of egg weights. Let w be the total weight difference between box x
and box y which you are trying to best adjust with a single swap. Do
this:

 D = repmat(x,size(y,2),1)-repmat(y',1,size(x,2)); % All x-y differences
 [c,lx] = min(abs(D(:)-w/2)); % Get the closest match with w/2
 [iy,ix] = ind2sub(size(D),lx); % Get the corresponding indices

c will be the smallest discrepancy in box weights attainable with a single
swap, and (ix,iy) will be the respective x and y indices for the
corresponding eggs to be swapped.

  If you contemplate more than one swap to achieve the needed correction,
the problem becomes more difficult. For example, to solve the two-swap
problem might require finding the differences between every possible pair
of x-box eggs with every possible pair of y-box eggs, an n^4 size matrix
of differences. If your boxes contain only, say, a dozen eggs each, this
approach would not be out of the question, however. Triple or quadruple
swaps would probably begin to require more sophisticated algorithms. Let
us know if you seriously envision going beyond single swaps.

Roger Stafford

Subject: Balancing arrays matlab command

From: Mark

Date: 1 Aug, 2007 22:41:32

Message: 6 of 8

Hi Roger,

Thanks so much for your help, it was 'repmat' that I needed, not 'meshgrid' as I was experimenting with.

So, I added your lines to my eggs problem to see what happens. After the boxes are full a single swap usually get sufficent balance. I added a loop to swap a second time if needed and that was always successful. Interestingly I need to swap at least once around 50% of the time. I put that down to the normal distribution of the rand command.

Thanks again for your help, I very much appreciate it.
Here's the solution in a test script:

% --- Balancing two egg boxes ---
MIN_MASS = 10;
MAX_MASS = 25;
EGGBOX_CAPACITY = 20;
MAX_MASS_TOLERANCE = 20;

TotalTests = 100;

for i = 1:TotalTests
   % Start with random assortment of eggs between 10-25g
   Eggs = rand(1,EGGBOX_CAPACITY * 2) * (MAX_MASS - MIN_MASS) + MIN_MASS;
   % Put half the eggs in each box
   Box1 = Eggs(1:EGGBOX_CAPACITY);
   Box2 = Eggs(1 + EGGBOX_CAPACITY:EGGBOX_CAPACITY + EGGBOX_CAPACITY);
   
   % Set up some vars
   ix = 0;
   Swaps = 0;
   % Create a copy of the original data for comparison later
   Box3 = Box1;
   Box4 = Box2;
   % Swap eggs until the egg boxes are within MAX_MASS_TOLERANCE of each
   % other (limit number of swaps to 5 in case we fail)
   while ix == 0 && Swaps < 5;
        % Let w = initial difference between cassette masses
        w = sum(Box3) - sum(Box4);
        if abs(sum(Box3) - sum(Box4)) < MAX_MASS_TOLERANCE
            % No swap necessary
            ix = 0;
            iy = 0;
            break;
        end
        d = repmat(Box3,size(Box4,2),1)-repmat(Box4',1,size(Box3,2)); % All x-y differences
        [c,lx] = min(abs(d(:)-w/2)); % Get the closest match with w/2
        [iy,ix] = ind2sub(size(d),lx); % Get the corresponding indices

        if c > MAX_MASS_TOLERANCE
            % Unable to get within tolerance with a swap
            ix = -1;
            iy = -1;
            break;
        end
        
        if ix > 0
           % perform swap in the boxes
           t = Box3(ix);
           Box3(ix) = Box4(iy);
           Box4(iy) = t;
           Swaps = Swaps + 1;
       else
           % no swop necessary
           break;
       end
       if abs(sum(Box3) - sum(Box4)) > MAX_MASS_TOLERANCE
           % Still not in tolerance after swap so force another go
           ix = 0;
       end
   end
   % save the egg data, original sums, sums after swap(s), and number of
   % swaps needed
   Dat(i,:) = [Eggs, Box1, Box2, sum(Box1) - sum(Box2), ix, iy, sum(Box3) - sum(Box4), Swaps];
end

% Percentage of times that swaps were needed
PercentSwapped = (sum(Dat(:,end)) / TotalTests) * 100

Subject: Balancing arrays matlab command

From: ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford)

Date: 1 Aug, 2007 17:51:34

Message: 7 of 8

In article <f8r26s$drv$1@fred.mathworks.com>, "Mark "
<medwar19.nospam@hotmail.com> wrote:

> Hi Roger,
>
> Thanks so much for your help, it was 'repmat' that I needed, not
'meshgrid' as I was experimenting with.
>
> So, I added your lines to my eggs problem to see what happens. After the
boxes are full a single swap usually get sufficent balance. I added a loop
to swap a second time if needed and that was always successful.
Interestingly I need to swap at least once around 50% of the time. I put
that down to the normal distribution of the rand command.
>
> Thanks again for your help, I very much appreciate it.
> Here's the solution in a test script:
>
> % --- Balancing two egg boxes ---
> MIN_MASS = 10;
> MAX_MASS = 25;
> EGGBOX_CAPACITY = 20;
> MAX_MASS_TOLERANCE = 20;
>
> TotalTests = 100;
>
> for i = 1:TotalTests
> % Start with random assortment of eggs between 10-25g
> Eggs = rand(1,EGGBOX_CAPACITY * 2) * (MAX_MASS - MIN_MASS) + MIN_MASS;
> % Put half the eggs in each box
> Box1 = Eggs(1:EGGBOX_CAPACITY);
> Box2 = Eggs(1 + EGGBOX_CAPACITY:EGGBOX_CAPACITY + EGGBOX_CAPACITY);
>
> % Set up some vars
> ix = 0;
> Swaps = 0;
> % Create a copy of the original data for comparison later
> Box3 = Box1;
> Box4 = Box2;
> % Swap eggs until the egg boxes are within MAX_MASS_TOLERANCE of each
> % other (limit number of swaps to 5 in case we fail)
> while ix == 0 && Swaps < 5;
> % Let w = initial difference between cassette masses
> w = sum(Box3) - sum(Box4);
> if abs(sum(Box3) - sum(Box4)) < MAX_MASS_TOLERANCE
> % No swap necessary
> ix = 0;
> iy = 0;
> break;
> end
> d = repmat(Box3,size(Box4,2),1)-repmat(Box4',1,size(Box3,2)); %
All x-y differences
> [c,lx] = min(abs(d(:)-w/2)); % Get the closest match with w/2
> [iy,ix] = ind2sub(size(d),lx); % Get the corresponding indices
>
> if c > MAX_MASS_TOLERANCE
> % Unable to get within tolerance with a swap
> ix = -1;
> iy = -1;
> break;
> end
>
> if ix > 0
> % perform swap in the boxes
> t = Box3(ix);
> Box3(ix) = Box4(iy);
> Box4(iy) = t;
> Swaps = Swaps + 1;
> else
> % no swop necessary
> break;
> end
> if abs(sum(Box3) - sum(Box4)) > MAX_MASS_TOLERANCE
> % Still not in tolerance after swap so force another go
> ix = 0;
> end
> end
> % save the egg data, original sums, sums after swap(s), and number of
> % swaps needed
> Dat(i,:) = [Eggs, Box1, Box2, sum(Box1) - sum(Box2), ix, iy,
sum(Box3) - sum(Box4), Swaps];
> end
>
> % Percentage of times that swaps were needed
> PercentSwapped = (sum(Dat(:,end)) / TotalTests) * 100
------------------
  It occurred to me that, in case you run into trouble making one or two
swaps alone do the trick, you could make the first step be a sorting of x
and y so that, if necessary, you could do the following. Swap the maximum
x's with the minimum y's, or visa versa, with a sufficient number of egg
pairs until just before that reverses the sign of the discrepancy. Then
with the remaining eggs you could do as before with one, possibly two,
more swaps which take into account all possible pairings. This way you
first remove any relatively large offset so that the final swaps have a
much larger probability of succeeding since they would be "centered"
better.

  Also instead of just repeating a swap to get a second swap in this
second phase, you could compute all possible pairs of x's along with all
possible pairs of y's. If, for example, you have 20 eggs in each box,
that gets 190 x-pairs to be compared with 190 y-pairs in a 190 x 190
matrix. That's instead of a 20 x 20 matrix of single x-eggs compared with
single y-eggs. Then do as before with this larger matrix. It's not
really very much harder to do than for a single swap, though it involves a
larger matrix. With so many possible combinations (36100 in this case)
the likelihood of satisfying your tolerance should be quite high.

  Of course all this software messing around with the egg locations
requires some careful indexing so that the programs manages to keep track
of the original location of all eggs to be swapped. This allows a final
swapping to be carried out that does not reflect all the computational
maneuvers that were required to arrive at it.

Roger Stafford

Subject: Balancing arrays matlab command

From: Mark

Date: 2 Aug, 2007 13:08:17

Message: 8 of 8

ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford) wrote in message <ellieandrogerxyzzy-0108071751340001@dialup-4.233.114.104.dial1.losangeles1.level3.net>...
> In article <f8r26s$drv$1@fred.mathworks.com>, "Mark "
> <medwar19.nospam@hotmail.com> wrote:
>
> > Hi Roger,
> >
> > Thanks so much for your help, it was 'repmat' that I needed, not
> 'meshgrid' as I was experimenting with.
> >
> > So, I added your lines to my eggs problem to see what happens. After the
> boxes are full a single swap usually get sufficent balance. I added a loop
> to swap a second time if needed and that was always successful.
> Interestingly I need to swap at least once around 50% of the time. I put
> that down to the normal distribution of the rand command.
> >
> > Thanks again for your help, I very much appreciate it.
> > Here's the solution in a test script:
> >
> > % --- Balancing two egg boxes ---
> > MIN_MASS = 10;
> > MAX_MASS = 25;
> > EGGBOX_CAPACITY = 20;
> > MAX_MASS_TOLERANCE = 20;
> >
> > TotalTests = 100;
> >
> > for i = 1:TotalTests
> > % Start with random assortment of eggs between 10-25g
> > Eggs = rand(1,EGGBOX_CAPACITY * 2) * (MAX_MASS - MIN_MASS) + MIN_MASS;
> > % Put half the eggs in each box
> > Box1 = Eggs(1:EGGBOX_CAPACITY);
> > Box2 = Eggs(1 + EGGBOX_CAPACITY:EGGBOX_CAPACITY + EGGBOX_CAPACITY);
> >
> > % Set up some vars
> > ix = 0;
> > Swaps = 0;
> > % Create a copy of the original data for comparison later
> > Box3 = Box1;
> > Box4 = Box2;
> > % Swap eggs until the egg boxes are within MAX_MASS_TOLERANCE of each
> > % other (limit number of swaps to 5 in case we fail)
> > while ix == 0 && Swaps < 5;
> > % Let w = initial difference between cassette masses
> > w = sum(Box3) - sum(Box4);
> > if abs(sum(Box3) - sum(Box4)) < MAX_MASS_TOLERANCE
> > % No swap necessary
> > ix = 0;
> > iy = 0;
> > break;
> > end
> > d = repmat(Box3,size(Box4,2),1)-repmat(Box4',1,size(Box3,2)); %
> All x-y differences
> > [c,lx] = min(abs(d(:)-w/2)); % Get the closest match with w/2
> > [iy,ix] = ind2sub(size(d),lx); % Get the corresponding indices
> >
> > if c > MAX_MASS_TOLERANCE
> > % Unable to get within tolerance with a swap
> > ix = -1;
> > iy = -1;
> > break;
> > end
> >
> > if ix > 0
> > % perform swap in the boxes
> > t = Box3(ix);
> > Box3(ix) = Box4(iy);
> > Box4(iy) = t;
> > Swaps = Swaps + 1;
> > else
> > % no swop necessary
> > break;
> > end
> > if abs(sum(Box3) - sum(Box4)) > MAX_MASS_TOLERANCE
> > % Still not in tolerance after swap so force another go
> > ix = 0;
> > end
> > end
> > % save the egg data, original sums, sums after swap(s), and number of
> > % swaps needed
> > Dat(i,:) = [Eggs, Box1, Box2, sum(Box1) - sum(Box2), ix, iy,
> sum(Box3) - sum(Box4), Swaps];
> > end
> >
> > % Percentage of times that swaps were needed
> > PercentSwapped = (sum(Dat(:,end)) / TotalTests) * 100
> ------------------
> It occurred to me that, in case you run into trouble making one or two
> swaps alone do the trick, you could make the first step be a sorting of x
> and y so that, if necessary, you could do the following. Swap the maximum
> x's with the minimum y's, or visa versa, with a sufficient number of egg
> pairs until just before that reverses the sign of the discrepancy. Then
> with the remaining eggs you could do as before with one, possibly two,
> more swaps which take into account all possible pairings. This way you
> first remove any relatively large offset so that the final swaps have a
> much larger probability of succeeding since they would be "centered"
> better.
>
> Also instead of just repeating a swap to get a second swap in this
> second phase, you could compute all possible pairs of x's along with all
> possible pairs of y's. If, for example, you have 20 eggs in each box,
> that gets 190 x-pairs to be compared with 190 y-pairs in a 190 x 190
> matrix. That's instead of a 20 x 20 matrix of single x-eggs compared with
> single y-eggs. Then do as before with this larger matrix. It's not
> really very much harder to do than for a single swap, though it involves a
> larger matrix. With so many possible combinations (36100 in this case)
> the likelihood of satisfying your tolerance should be quite high.
>
> Of course all this software messing around with the egg locations
> requires some careful indexing so that the programs manages to keep track
> of the original location of all eggs to be swapped. This allows a final
> swapping to be carried out that does not reflect all the computational
> maneuvers that were required to arrive at it.
>
> Roger Stafford

Indeed, as I know the mass of each egg after it's been put in a box I tried centering the mass of the eggs during loading by always adding the next egg to the lighter box. This usually meant that the boxes stayed within a tolerance of each other during loading, sometimes resulting in a space or two in one box when the other was full. I ran this load-sorting test along with a alternating-load strategy and found no difference in the number of swaps required (~50%).

My next challange is to modify the code for partially loaded boxes. I can see a case when the number of eggs is small where moving a single egg from one box to another will balance the boxes but a swop will not.

Thanks again for your help with my eggs.

Mark.

Tags for this Thread

No tags are associated with 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