Edit (13 Jan 2012):
Your example can be solved in smaller number of iterations. I will try to code you an algorithm. But, for the time being consider the following where I reach the same solution as your example in 4 iterations:
- We ignore the column where SU = T. For example, we don't touch M2, M4, M9
in this example.
- We proceed from left to right (M1 to M11). Everything on the left will
have SU = T
The basic functions are:
- Find_Odd_Any() will find the first column where SU != T
- Find_Odd_Greater_Than_T(Mx, T) will return the first column where SU > T
- Find_Odd_Smaller_Than_T(Mx, T) will return the first column where SU < T
- Exchange_One_ManDay(Mx, My) will take one man-day from the highest row in Mx and put it in the lowest row in My
Threshold (T) = 7
M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11
Start A1 3 1 3 1 3 3 3 3 3 3 1
A2 3 3 2 3 1 3 1 2 1 3 1
A3 3 3 1 3 2 2 1 3 3 2 3
SU 9 7 6 7 6 8 5 8 7 8 5
Iteration 1:
1. Find the first odd column where SU != T.
Find_Odd_Any():
- Will return M1=9
2. M1 = 9. So we have to reduce and donate 2 man-days into some other
column(s) where SU < T. So, now we find the next odd column where SU < T.
for (i = 0; i < absolute(M1[SU] - T); i++): // this loop runs twice
{
Find_Odd_Smaller_Than_T(M2, 7):
* This function will start checking from column M2 and return
the column for which SU < T=7
* Starting from M2 because it is next to M1 and we are
operating on M1
* Will return M3=6 (at loop i=0), M5=6 (at loop i=1)
Exchange_One_ManDay(M1, M3): // at loop i = 0
* This function will take 1 from M1 (from max row A1) and put
it inside M3 (to min row A2) at loop i=0
Exchange_One_ManDay(M1, M5): // at loop i = 1
* This function will take 1 from M1 (from max row A2) and put
it inside M5 (to min row A2) at loop i=1
}
* By the end of the loop, the distribution will look like the
following:
M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11
Start A1 2 1 3 1 3 3 3 3 3 3 1
A2 2 3 2 3 2 3 1 2 1 3 1
A3 3 3 2 3 2 2 1 3 3 2 3
SU 7 7 7 7 7 8 5 8 7 8 5
Iteration 2:
1. Find the first odd column where SU != T.
Find_Odd_Any():
* Will return M6=8
2. M6 = 8. So, we have to reduce and donate 1 man-day from M6 into some
other column(s) where SU < T. So, now we find the next odd column where
SU < T.
for (i = 0; i < absolute(M6[SU] - T); i++): // this loop runs once
{
Find_Odd_Smaller_Than_T(M7, 7):
* This function will start checking from column M7 and return
the column for which SU < T=7
* Starting from M7 because it is next to M6 and we are
operating on M6
* Will return M7=5 (loop i=0)
Exchange_One_ManDay(M6, M7):
* This function will take 1 from M6 (from max row A1) and put
it inside M7 (to min row A2) at loop i=0
}
* By the end of the loop, the distribution will look like the
following:
M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11
Start A1 2 1 3 1 3 2 3 3 3 3 1
A2 2 3 2 3 2 3 2 2 1 3 1
A3 3 3 2 3 2 2 1 3 3 2 3
SU 7 7 7 7 7 7 6 8 7 8 5
Iteration 3:
1. Find the first odd column where SU != T.
Find_Odd_Any():
* Will return M7=6
2. M7 = 6. So, we have to increase and borrow 1 man-day from some other
column(s) where SU > T. So, now we find the next odd column where SU > T.
for (i = 0; i < absolute(M6[SU] - T); i++): // this loop runs once
{
Find_Odd_Greater_Than_T(M8, 7):
* This function will start checking from column M8 and return
the column for which SU > T=7
* Starting from M8 because it is next to M7 and we are
operating on M7
* Will return M8=8 (loop i=0)
Exchange_One_ManDay(M8, M7):
* This function will take 1 from M8 (from max row A1) and put
it inside M7 (to min row A3) at loop i=0
}
* By the end of the loop, the distribution will look like the
following:
M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11
Start A1 2 1 3 1 3 2 3 2 3 3 1
A2 2 3 2 3 2 3 2 2 1 3 1
A3 3 3 2 3 2 2 2 3 3 2 3
SU 7 7 7 7 7 7 7 7 7 8 5
Iteration 4:
1. Find the first odd column where SU != T.
Find_Odd_Any():
- Will return M10=8
2. M10 = 8. So, we have to reduce and donate 1 man-day into some other
column(s) where SU < T. So, now we find the next odd column where SU < T.
for (i = 0; i < absolute(M10[SU] - T); i++): // this loop runs once
{
Find_Odd_Smaller_Than_T(M11, 7):
* This function will start checking from column M11 and return
the column for which SU > T=7
* Starting from M11 because it is next to M10 and we are
operating on M10
* Will return M11=5 (loop i=0)
Exchange_One_ManDay(M10, M11):
* This function will take 1 from M10 (from max row A1) and put
it inside M11 (to min row A1) at loop i=0
}
- By the end of the loop, the distribution will look like the
following:
M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11
Start A1 2 1 3 1 3 2 3 2 3 2 2
A2 2 3 2 3 2 3 2 2 1 3 1
A3 3 3 2 3 2 2 2 3 3 2 3
SU 7 7 7 7 7 7 7 7 7 7 6
Python code that Implements above:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def find_odd_any():
su = 0
i = 0
for m in x:
for a in m:
su = su + a
if su != t:
return i
else:
su = 0
i = i + 1
return None
def find_odd_greater(k):
su = 0
i = k
for m in x[k:]:
for a in m:
su = su + a
if su > t:
return i
else:
su = 0
i = i + 1
return None
def find_odd_smaller(k):
su = 0
i = k
for m in x[k:]:
for a in m:
su = su + a
if su < t:
return i
else:
su = 0
i = i + 1
return None
def exchange_one_manday(src_i, dst_i):
src_m = x[src_i]
dst_m = x[dst_i]
# Reduce 1 man-day from source
src_m[src_m.index(max(src_m))] = src_m[src_m.index(max(src_m))] - 1
# Increase 1 man-day in destination
dst_m[dst_m.index(min(dst_m))] = dst_m[dst_m.index(min(dst_m))] + 1
def print_x():
print "[",
for m in x:
su = 0
for a in m:
su = su + a
print su, m, "|",
print "] \n"
t = 7 # threshold
x = [
[3,3,3], # 9
[1,3,3], # 7
[3,2,1], # 6
[1,3,3], # 7
[3,1,2], # 6
[3,3,2], # 8
[3,1,1], # 5
[3,2,3], # 8
[3,1,3], # 7
[3,3,2], # 8
[1,1,3] # 5
]
print "start =>",
print_x()
su = 0
i = 0
c = 0
while find_odd_any() is not None and (i+2) < len(x):
i = find_odd_any()
m = x[i]
for a in m: # find SU for the current M
su = su + a
if su != t:
d = abs(su - t) # absolute displacement from T
for j in range(0, d):
if su > t: # current M's SU is greater than T
odd = find_odd_smaller(i+1)
if odd is not None:
print "gotta exchange=", i,x[i], "with", odd,x[odd]
exchange_one_manday(i, odd)
if su < t: # current M's SU is smaller than T
odd = find_odd_greater(i+1)
if odd is not None:
print "gotta exchange=", i,x[i], "with", odd,x[odd]
exchange_one_manday(odd, i)
su = 0
c = c + 1
print "round", c,"=>",
print_x()
#raw_input()
If you run the code above with python file.py, the output should be:
start => [ 9 [3, 3, 3] | 7 [1, 3, 3] | 6 [3, 2, 1] | 7 [1, 3, 3] | 6 [3, 1, 2] | 8 [3, 3, 2] | 5 [3, 1, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]
gotta exchange= 0 [3, 3, 3] with 2 [3, 2, 1]
gotta exchange= 0 [2, 3, 3] with 4 [3, 1, 2]
round 1 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 8 [3, 3, 2] | 5 [3, 1, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]
gotta exchange= 5 [3, 3, 2] with 6 [3, 1, 1]
round 2 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 6 [3, 2, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]
gotta exchange= 6 [3, 2, 1] with 7 [3, 2, 3]
round 3 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 7 [3, 2, 2] | 7 [2, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]
gotta exchange= 9 [3, 3, 2] with 10 [1, 1, 3]
round 4 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 7 [3, 2, 2] | 7 [2, 2, 3] | 7 [3, 1, 3] | 7 [2, 3, 2] | 6 [2, 1, 3] | ]