Design Python Program for Tug of War

In this tutorial, you will learn to design a Python program for the Tug of War.

Python Program for Tug of War

In this problem, we are provided with a set of integers. We then need to break the given set into two different sets in such a way that there is a minimum difference in the sum of two subsets. That is we divide the team into two groups with equal strengths to participate in-game.

Consider total number of people (set) is N.

If N is even – Size of each team = N/2

If N is odd – Size of one team = (N-1)/2 while other contains (N+1)/2

Let us consider a small example :

1 )

Given set = {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}

Here, N= 10 (Even)

Thus team 1 = {4, 100, 1, 23, 20}; Sum = 148

Team 2 = {3, 5, -3, 89, 54}; Sum = 148

2)

Given set = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}

Here, N= 11 (Odd)

Thus team 1 = {45, -34, 12, 98, -1} ; Sum = 120

Team 2 = {23, 0, -99, 4, 189, 4}; Sum = 121

Algorithm :

Begin
   if position = n, then     
      return
   if (n/2-selected) > (n - position), then
      return
   TugOfWar(weight, n, current, selected, solution, difference, sum, total, position+1)
   selected := selected + 1
   total := total + weight[position]
   current[position] := true      

   if selected = n/2, then
      if difference of (sum/2 and total) < diff, then
         difference := difference of (sum/2 and total)
         for i := 0 to n, do
            solution[i] := current[i]
         done
   else
      TugOfWar(weight, n, current, selected, solution, difference, sum, total, position+1)
   current[position] := false    
End

1. Initialize the current set as empty. Now there are two solutions for every element, either it will be in the current set or else another subset.
2. Considering both possibilities, when current set is full(ie contains N/2 elements) check if it best solution out of all previous solution.
3. If yes, update the else discard.

Here is a sample code :

def TOW_Until(array, n, curr_elements, no_of_selected_elements,soln, min_diff, Sum, curr_sum, curr_position): 
   
  if (curr_position == n): 
    return
  if ((int(n / 2) - no_of_selected_elements) > (n - curr_position)): 
    return
  TOW_Until(array, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1) 

  no_of_selected_elements += 1
  curr_sum = curr_sum + array[curr_position] 
  curr_elements[curr_position] = True
 
  if (no_of_selected_elements == int(n / 2)): 
    
    if (abs(int(Sum / 2) - curr_sum) < min_diff[0]): 
      min_diff[0] = abs(int(Sum / 2) - curr_sum) 
      for i in range(n): 
        soln[i] = curr_elements[i] 
  else: 
    TOW_Until(array, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1) 

  curr_elements[curr_position] = False
 
def tugOfWar(array, n): 
  curr_elements = [None] * n 

  soln = [None] * n 

  min_diff = [999999999999] 

  Sum = 0
  for i in range(n): 
    Sum += array[i] 
    curr_elements[i] = soln[i] = False

  TOW_Until(array, n, curr_elements, 0, soln, min_diff, Sum, 0, 0) 

  print("First subset: ") 
  for i in range(n): 
    if (soln[i] == True): 
      print(array[i], end = " ") 
  print() 
  print("Second subset: ") 
  for i in range(n): 
    if (soln[i] == False): 
      print(array[i], end = " ")  
if __name__ == '__main__': 

  array = [3, 4, 5, -3, 100, 1, 89, 54, 23, 20]
  n = len(array) 
  tugOfWar(array, n) 

OUTPUT :

First subset: 
4 100 1 23 20 
Second subset: 
3 5 -3 89 54

You may also like :

• Predict Weather Report Using Machine Learning in Python