// Arup Guha
// 7/13/2011
// This file will illustrate the idea of mapping reducibility via
// several methods. In particular, solutions to different problems
// will be obtained by transforming the input of one problem to the
// input of another problem, such that both problems always have 
// the same answer.

public class Reductions {
	
	// Returns true iff index i stores the minimum value in array.
	public static boolean isMin(int[] array, int i) {
		
		// Invalid index, so it can't store the min.
		if (i < 0 || i >= array.length)
			return false;
			
		// Find an index that stores the min.
		int minIndex = 0;
		for (int loop=1; loop<array.length; loop++)
			if (array[loop] < array[minIndex])
				minIndex = loop;
				
		// i stores a minimum value only if these two values are equal.
		return array[minIndex] == array[i];
	}
	
	// This is our function that will help us map the max array problem to
	// the min array problem. It returns a new array that has values that
	// are the negated values of array.
	public static int[] maxToMin(int[] array) {
		
		int[] newarray = new int[array.length];
		
		// Store the negative of each value in the new array.
		for (int i=0; i<array.length; i++)
			newarray[i] = -array[i];
			
		return newarray;
	}
	
	// Solves the max array problem via a problem reduction.
	// Namely, we transform our input array, and then find 
	// the minimum in our input array, which corresponds to
	// the maximum in the original array.
	public static boolean isMax(int[] array, int i) {
		
		// We call isMin on a transformed input which always
		// gives us the correct answer.
		return isMin(maxToMin(array), i);
	}
	
	// Wrapper function that solves the subset sum problem.
	public static boolean subsetSum(int[] values, int target) {
    	return subsetSumHelp(values, values.length, target);
  	}

  	// Recursive function that returns truee iff there exist some subset of
  	// values in values[0..size-1] that add up exactly to target.
  	public static boolean subsetSumHelp(int[] values, int size, int target) {

    	// Empty set's elements sum to 0 - return true.
    	if (target == 0)
      		return true;

    	// Considering an empty set and our target is non-zero.
    	if (size == 0)
      		return false;
   
    	// Check both possibilities of adding in values[startindex] and
    	// not doing so into the subset.
    	return  subsetSumHelp(values, size-1, target) ||
	   			subsetSumHelp(values, size-1, target-values[size-1]);
 
  	}
  	
  	// Returns the appropriate target for SubsetSum for array, so that
  	// the partition problem can be solved.
  	public static int getTarget(int[] array) {
  		
  		// Sum up the values in the array.
  		int sum = 0, sum2 = 0;
  		for (int i=0; i<array.length; i++) {
  			sum += array[i];
  			sum2 += Math.abs(array[i]);
  		}
  			
  		// Return half of this value if it's even.
  		if (sum%2 == 0)
  			return sum/2;
  			
  		// Return an impossible target.
  		return sum2+1;
  	}
  	
  	// This function is used to do a mapping reduction from subset sum
  	// to partition. 
  	// This is only guaranteed to work if all values in array are positive.
  	public static int[] getPartition(int[] array, int target) {
  		
  		int[] newarray = new int[array.length+1];
  		
  		// Copy in original values and calculate sum.
  		int sum = 0;
  		for (int i=0; i<array.length; i++) {
  			newarray[i] = array[i];
  			sum += array[i];
  		}
  		
  		// Fill in this last value.
  		// The idea is this: If the target exists in the original,
  		// then some items add up to T, the rest add up to S - T, where
  		// S is the sum of all the original items. Add to this, the 
  		// term S - 2T. The new sum is S + S - 2T = 2S - 2T. Half of
  		// this is S - T. The term S - 2T will exist in one half of the 
  		// partition. The rest of the elements add up to T as desired.
  		// Similarly, if no elements in the original set add up to T,
  		// none will add upto S - T in the new set.
  		newarray[newarray.length-1] = sum - 2*target;
  		
  		return newarray;
  		
  	}
  	
  	// Solves the subset sum problem via a mapping reduction to partition.
  	public static boolean subsetSumSolveRed(int[] array, int target) {
  		return partition(getPartition(array, target));
  	}
  	
  	// Solves the partition problem via a mapping reduction to Subset Sum.
  	public static boolean partition(int[] array) {
  		
  		// Calls subset sum with the appropriate target.
  		return subsetSum(array, getTarget(array));
  	}
	
	public static void main(String[] args) {
		
		int[] values = {3, 8, -5, 4, 9, 2, -3, -1, 3};
		
		// Solve max for this instance.
		if (isMax(values, 4))
			System.out.println("Max value in the array is at index 4.");
		else
			System.out.println("Max value of the array is NOT at index 4.");
			
		// Solve partition for this instance.
		if (partition(values))
			System.out.println("The array can be partitioned.");
		else
			System.out.println("The array can NOT be partitioned.");
			
		// Solve subset sum via the reduction
		if (subsetSumSolveRed(values, 28))
			System.out.println("There's a subset that adds to 28.");
		else
			System.out.println("No subset adds to 28.");
	}
}