0

i need Given a set of numbers on the command line (partition an array)
It should check whether a solution exists and if so  print the two sets

upto now the code i have seems to parttion each integer, what i need is for it to partition the array as a whole, for example lets take the array[1,2,3] this can be divided as [1,2] and [3], we can see that these two subsets have an equal sum.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication2;

import java.util.ArrayList;
import java.util.Collection;

public class Partition {
    private static int arrayNumber = 0;
    private static Collection<Integer> s1 = new ArrayList<Integer>();
    private static Collection<Integer> s2 = new ArrayList<Integer>();

    public static void partition(int n) {
        partition(n, n, "");
    }
    
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            arrayNumber++;
            String[] s = prefix.split(" ");
            if (arrayNumber == 2) {
                addtoArray(s, s1);
            } else if(arrayNumber == 3) {
                addtoArray(s, s2);
            }
            //System.out.println("--------------");
            //System.out.println(prefix);

            return;
        }

        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }

    private static void addtoArray(String s[], Collection<Integer> col) {
        for (int i = 0; i < s.length; i++) {
            String numStr = s[i];
            if (numStr.equals("")) {
                continue;
            }
            int num = Integer.parseInt(numStr);
            col.add(num);
        }
    }


    public static void main(String[] args1) {
        String[] args = {"6", "2", "4"};

        for (int i = 0; i < args.length; i++) {
            arrayNumber = 0;
            String str = args[i];
            int n = Integer.parseInt(str);
            partition(n);
        }

        for (int number : s1) {
            System.out.print(number + " ");
        }

        System.out.println("");
        for (int number : s2) {
            System.out.print(number + " ");
        }
        System.out.println("");
    }

}

PLEASE HELP

4
Contributors
10
Replies
14
Views
6 Years
Discussion Span
Last Post by thamilvaanan
0

check whether a solution exists

Could you define what a solution is? How are the numbers to be partitioned?

Sounds like you need an algorithm for solving the problem? What do you have so far?

0

Partition Problem
“The problem is to decide whether a given multiset of  integers can be partitioned into two "halves" that have  the same sum. More precisely, given a multiset S of  integers, is there a way to partition S into two subsets S1  and S2 such that the sums of the numbers in each  subset are equal? The subsets S1 and S2 must form a  partition in the sense that they are disjoint and they  cover S.”

what i need fr my code to do is
solve the partition problem
Given a set of numbers on the command line
It should check whether a solution exists and if so  print the two sets

0

Ok. Got it. For example given {10, 6, 4} the results would be: {10} and {4,6}
What is your design so far?

0

exactly.

i sent u my code above. but that doesnt work. it seems to divide off numbers, say array[2,4,6], it comes as 1,1 2,2 3,3, doesnt divide the array only the integers one by one

0

Before you code a program you need to design it. Writing code before getting a design wastes a lot of time.
Do you have a design for how you are going to read and partition a set of numbers?

0

Do you have a design or algorithm on how to solve this problem? Given that, we can help you write a java program to do it.

Have you tried Google for an algorithm that shows the logic needed to solve this?

0

Yes finding the proper algorithm is the key to solve this problem,
I just tried with a straight forward algorithm(i.e to checck all possible sums in a proper sequence).

This may not be the best but works fine.

Sorry for not using comments.

Here is the code.
I also placed the sample output here.

Cool.

/*
 * 
 * author thamilvaanan
 * 
 * 
 */



import java.util.ArrayList;
import java.util.Collection;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Collections;

public class Partition {
	
 //private ArrayList<Integer> inputArray = new ArrayList<Integer>(); 
	
	
 public Partition(){
	 
 
 findPair(getInput());
	
	 
 }

 
 
	private void findPair(List<Integer>  arrayInput) {
		 List<Integer> dynamicArrayPosition= new ArrayList<Integer>();
		 int totalSum=0;	 
		 totalSum=findTotalSum(arrayInput);
	     int currentSum=0; 
	     int length=arrayInput.size()/2;
	     int inputArrayLength=arrayInput.size();
	     boolean isSubsetsFound=false;
		 for(int i=1; i<=length; i++)
		 {
			 dynamicArrayPosition= getDynamicArrayPosition(i);
			 
			 
			 for(int j=1; j<=getcombinations(arrayInput.size(),i); j++)
			 {
				 currentSum=0;
	             int k=0;
				 while ( k<i && dynamicArrayPosition.get(k)< inputArrayLength)
				 {
					//System.out.println("i"+i+", k"+k+"dynamicArrayPosition.get(k)"+dynamicArrayPosition.get(k)); 
					 //System.out.println("sdfsdf"+arrayInput.get(dynamicArrayPosition.get(k)));
					currentSum +=  arrayInput.get(dynamicArrayPosition.get(k)) ;
					//System.out.println("currentSumIn"+currentSum);
				    k++;
				 }
				 //System.out.println("currentSum"+currentSum);
				 if(currentSum==totalSum-currentSum)
				 {
					isSubsetsFound=true; 
					
					outputAnswer(dynamicArrayPosition,arrayInput);
					
					break; 
				 }
				 
				//System.out.println("dynamicArrayPosition.get(k)"+dynamicArrayPosition.get(i-1)); 
				//System.out.println("inputArrayLength"+inputArrayLength); 		 
				 if( dynamicArrayPosition.get(i-1) >= inputArrayLength -1  )
				 {
					 //System.out.println("inputArrayLength");
					 dynamicArrayPosition = dynamicArrayPositionHandler(i,inputArrayLength, dynamicArrayPosition);
				 }
				 else
				 {
					 dynamicArrayPosition.set(i-1,dynamicArrayPosition.get(i-1)+1);
				 }
				 
			 }
	                  
		 	 if(isSubsetsFound)
		 	 {
		 		break; 
		 	 }
		 }
	 	 if(!isSubsetsFound)
	 	 {
			System.out.println("........................");
			System.out.println("Equal sum subsets not found");	
	 	 }
	}

	private void outputAnswer(List<Integer> dynamicArrayPosition, List<Integer>  arrayInput) {
		List<Integer> set1= new ArrayList<Integer>();
		List<Integer> set2= new ArrayList<Integer>();
		System.out.println("........................");
		System.out.println("Equal sum subsets found");	
		int length=dynamicArrayPosition.size();
		 for(int i=0; i<length; i++)
		 {
		 	set1.add(arrayInput.get(dynamicArrayPosition.get(i)));				 
		 }
		Iterator<Integer> iterator= arrayInput.iterator();
		while (iterator.hasNext())
		{
			if (set1.contains(iterator.next()))
				iterator.remove();
		}
		set2= arrayInput;
		System.out.println(set1+" = "+set2+" = "+findTotalSum(arrayInput));
			
		
	}

	public int factorial(int number)
	{
		int result=1;
		for(int i=number; i> 1; i--)
		{
			result*=i;
		}
		return result;
	}
	
	public int getcombinations(int var1,int var2 )
	{
		int result=1;		
		result= factorial(var1)/(factorial(var1-var2)*factorial(var2));
		return result;
	}
	
	public void totalPossibleTwoPairSets(List<Integer>  arrayIn)
	{
		List<Integer> arrayInput= arrayIn;
		int numberOfCombinations=0;
		 
		

		Collections.sort(arrayInput);
		
		 for(int i=1; i<=arrayInput.size()/2; i++){
		 	 
		 numberOfCombinations+= getcombinations(arrayInput.size(),i); 
				                  
		 
		 }
		System.out.println("Total Possible Two Pair Sets:"+numberOfCombinations); 
	}
	
	
	
	public int findTotalSum(List<Integer>  arrayIn)
	{
		int result=0;
		
		 for(int i=0; i<arrayIn.size(); i++)
		 {
			 result+= arrayIn.get(i);	                  			 
		 }
		
		return result;
	}
	
	public List<Integer> getDynamicArrayPosition(int index)
	{
		List<Integer> dynamicArrayPosition= new ArrayList<Integer>();
		 for(int i=0; i<index; i++)
		 {        
			 dynamicArrayPosition.add(i);
		 }
		return dynamicArrayPosition;
	}

	public List<Integer> dynamicArrayPositionHandler(int index,int length,List<Integer> lastPositions)
	{
		 
		 for(int i=index-1; i>=0; i--)
		 {  
			// System.out.println("lastPositions.get(i)"+lastPositions.get(i)); 
			//  System.out.println("length-(index-i)"+(length-(index-i))); 
			//  System.out.println(lastPositions.get(i)==((length-(index-i)))); 
		   if(lastPositions.get(i) == (length-(index-i)) && i>0 )
		   {
			 //  System.out.println("length-(index-i)"+(length-(index-i))); 
			   lastPositions.set(i-1, lastPositions.get(i-1)+1);
			   lastPositions.set(i, lastPositions.get(i-1)+1);
		   }   
			 
		 }
		// System.out.println("lastPositions"+lastPositions); 
		return lastPositions;
	}
 
 private List<Integer>  getInput() throws InputMismatchException {
  
	List<Integer> tempList = new ArrayList<Integer>(); 
    Scanner sc = new Scanner(System.in);
    
    int currentInt;
    
   
    System.out.println("Enter Numbers with a space");
	 
    
    String numberString= sc.nextLine();
    
	StringTokenizer st1 = new StringTokenizer(numberString);	
 
    while (st1.hasMoreTokens() )
	{   	 
     currentInt= Integer.parseInt(st1.nextToken());      
	 tempList.add(currentInt);	 	   
    }
 
    
	System.out.println("Your Input : "+tempList);
	return tempList;
}
 


 public static void main(String args[])
 {
 
    Partition partition= new Partition();
	 
	 
 }
 	

}

Enter Numbers with a space
5 3 9 6 1
Your Input : [5, 3, 9, 6, 1]
........................
Equal sum subsets found
[3, 9] = [5, 6, 1] = 12

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.