ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford) wrote in message <ellieandrogerxyzzy0108071751340001@dialup4.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 1025g
> > 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 xy 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 xpairs to be compared with 190 ypairs in a 190 x 190
> matrix. That's instead of a 20 x 20 matrix of single xeggs compared with
> single yeggs. 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 loadsorting test along with a alternatingload 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.
