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] | ]