Hi ya'll, I am a new to Java and I need your hlep. Need to write a Java program called “split” that reads a text file, input.txt, that contains a list of positive integers (duplicates are possible) separated by spaces and/or line breaks. After reading the integers, the program prints out Yes if the set of integers can be split into two subsets such that the average of the first subset is a multiple of the average of the second subset. Otherwise (if the list if integers cannot be splited into two sets satisfying the condition above), the program prints out No. Assume that input.txt contains at least 2 integers. e.g. If in.txt contains 2 2, the program must print out Yes. The two splits are {2} and {2}, with the same average of 2. Obviously 2 is a multiple of 2. e.g. If in.txt contains 2 4, the program must print out Yes. The two splits are {2} and {4}. The first average is 2, the second average is 4, and 4 is a multiple of 2. e.g. If in.txt contains 9 5 7 2, the program must print out No. {2, 5} with an average of 3.5 and {7, 9} with an average of 8. 8 is not a multiple of 3.5 To do: 1. Implement a linked list. 2. Program should read the integers from input.txt and store them into the linked list. The output in this step should be same as input i.e. in this step we are just reading input. 3. In this step we check if we can split input into two subsets such that the average of the first set is a multiple of the average of the second set. No additional data structures are allowed. All computations must be done in place on the original data structure. No additional data structures are allowed, such as a second linked list, an array, etc. d) Check the output and print Yes or No. e) The program shouldn't change the linked list i.e. it should remain in its original form as it was read from the input file input.txt. We are supposed to implement the linked list from scratch without using language libraries. For example, we are not allowed to use any built-in dynamic data structures, such as ArrayList or LinkedList. Thank you.
priya_k · Oct 14, 2011 2:39 PM · 939 views
In your 3rd example, 9 5 7 2, why r u making set of {2, 5} and {7, 9}, should it be ordered first and split into two subsets(i didn't see that requirement) or is it to be sequentially read. I thought if the file has 9 5 7 2 , the sets will be {9,5} and {7,2} or am i missing something? Also what will be the subsets of 9 5 7? Last edited: 14-Oct-11 03:29 PM
bange · Oct 14, 2011 3:26 PM
If input.txt contains 9 5 7 2, the program must print out No. All possible splits are as follows: - {2} with an average of 2 and {5, 7, 9} with an average of 7. 7 is not a multiple of 2 - {5} with an average of 5 and {2, 7, 9} with an average of 9. 9 is not a multiple of 5. - {7} with an average of 7 and {2, 5, 9} with an average of 5.33. 7 is not a multiple of 5.33 - {9} with an average of 9 and {2, 5, 7} with an average of 7. 9 is not a multiple of 7 - {2, 5} with an average of 3.5 and {7, 9} with an average of 8. 8 is not a multiple of 3.5 - {2, 9} with an average of 5.5 and {5, 7} with an average of 6 6 is not a multiple of 5.5 I think this problem should be a good practise for all of us :) Please come up with the solution code :) Last edited: 14-Oct-11 03:41 PM
priya_k · Oct 14, 2011 3:40 PM
If input.txt contains 13 2 7 3, the program must print out Yes. In this case, the splits are {2, 3} and {7, 13}. The average of {7, 13} is 10 and it is a multiple of 2.5, the average of {2, 3}.
priya_k · Oct 14, 2011 3:43 PM
Hi Priya ! I have succesfully solved your problem. Email me your email address, I will send you the code. Please send me $50 for the code <I will reply you back my paypal email address >. It took me some time to solve and I hope you don't mind giving me the value for the time I spent on your problem. P.S. If don't want to appreciate my hardword solve ur own problem BEE-YOTCH Thanks, Dalle MOMO Last edited: 14-Oct-11 03:54 PM
dalle_momo · Oct 14, 2011 3:53 PM
@ dalle_momo, I am a student and I cant afford to pay u, all I can do is thank you and appreciate for your hard work. Also please mind ur language.
priya_k · Oct 14, 2011 4:25 PM
Also if someone can do the problem, please pose the code here or message me and I will send my email address. It will be of great help! Thanks, Priya Last edited: 14-Oct-11 04:30 PM
priya_k · Oct 14, 2011 4:29 PM
If you cant do ur assignments may be this is not the field fo u dude!!, dont try to just get by try and learn, if u cant do this now how will u do this on a regular basis when u are expected to do it or get done!!! paisa tirera padna ga ho ni pasia tirera chorna ga hora ??
SajhaHelpUSer · Oct 14, 2011 5:14 PM
Is this an NP Complete problem? It sounds similar to Subset Sum. If it is then it can be optimized by using a customized linkedlist. Good Luck.
EastSidaz · Oct 14, 2011 5:31 PM
priya !! nice name..kta nai bhaye pani I ll give a credit on that.., responses seem to flow towards gals...its nature!! ok lets get to the point,, prolem doesnt seem that complicated, i would do it, but i got my own stuffs to worry about.....if things dont go well for you ,,i ll sure do it for u...and at no cost ;) now, the thought process: hope u kno, use scanner in util package to read ur txt file store it in any collection class.. once u have the array,,iterate over each element ,,,, have nested for statement so that would give you all possible combinatins required by the problem statement..(remember that 3 by 3 matrix in C++ class?) once you have that, access each element and apply your logic in it ,,(bunch of if--elses...) within that for! and...thats it!!
maila_baa · Oct 15, 2011 2:04 AM
@ Thanks Maila_Baa for the suggestion! Why wud I hide my gender, afterall sajha was referred to me by my frn who often visits sajha.. I got your concept, but I am looking for a solution.. :) well, if u cud do some coding for me?? I am still learning :)
priya_k · Oct 15, 2011 2:21 AM
As I said! ; complete solution ..copy-pasted from eclipse.....if COWBOYS beat patriots this sunday!!! ; lets enjoy the game priya !!: ;
Maila_Baa · Oct 15, 2011 2:57 AM
Simply amazing. I understand you are having hard time and Java is new to you but give an honest attempt to solve the problem. Show snippet of code that you have worked on so far. If you don't understand Java then what language do you understand? How about you write one in psedocode based on what maila_baa said? Writing the above code isn't hard at all. Stop begging for solution here. Seriously, I wonder why you are even taking this class? Is it a requirement that you need to fulfil? If I were you, I would change my major. You slacking right now will come back and haunt you in life. Incandescent.
incandescent · Oct 15, 2011 11:09 AM
This is not the solution, but just an implemention of LinkedList in Java. I tried to come up with the one that's enough to acheive the rest of the requirments of your homework. May be it will help you understand linked list a little bit. // LinkedList class // A linked list implementation in Java class LinkedList { private Node first; // to refer to first Node object in the list private Node last; // to refer to the last Node object in the list private Node nav; // to use to navigate the list: first through last // default constructor public LinkedList() { this.first = null; this.last = null; this.nav = null; } // to insert a number in the list public void insert(int number) { Node node = new Node(number); // construct a Node object with the number node.next = null; // this will be the last node so there should not be any node next to it if(this.first == null) { // if >> this is the first element being inserted into the list this.first = node; // first should refer to it this.nav = first; // nav should refere to it this.last = node; // since it's the first element it's the first and also last } else { // else >> since this is going to be the last node in the list last.next = node; // let the next of previous last node refer to this last = node; // and last should refer to currently the last node in the list } } // to check if the list is empty public boolean isEmpty() { if(this.first == null) { // if first is still null return true; // list its empty } return false; // else its not empty } // to check if there is next node while iterating through the list public boolean hasNext() { if(nav == null) { // nav goes from first to last and next to last is null nav = first; // reset nav to refer to the first node in the list return false; // so there is no more nodes } return true; } // to return the number stored in the current node and move nav to next node public int next() { int number = this.nav.number; // get the number in the current node this.nav = this.nav.next; // let the nav refer to the next node return number; // return the number } // Node class represents each node in the list // Since it does not have any meaning to the outside world // we can just make private with the LinkedList class private class Node { private int number; // this will hold number read from file private Node next; // this will work as the link between this node and the node next to it public Node(int number) { this.number = number; } } } // Testing the LinkedList class public class LinkedListTest { public static void main(String... args) { LinkedList ll = new LinkedList(); ll.insert(9); ll.insert(5); ll.insert(7); ll.insert(2); System.out.println(ll.isEmpty()); System.out.println("\n\n"); while(ll.hasNext()) { System.out.println(ll.next()); } System.out.println("\n\n"); while(ll.hasNext()) { System.out.println(ll.next()); } } } After that: > Read the numbers from the file using the some of the classes in "java.io" package. It's impossible to read files in Java without using library classes. > After you have read the numbers from file into the list, next steps will be just the loopings and conditions. > One thing: In the question, when it says set does it mean a real set, point is that sets do not allow duplicates and your solution might have to take care of that too. Last edited: 15-Oct-11 11:24 AM
fuckeetow · Oct 15, 2011 11:23 AM
It may not be as easy as it seems. To me it seems like an Undergraduate Algorithm and Data Structure Project. Hence the restraint on using java API. If it is, then your priority would be memory optimization and execution time. For a set of N integers, there are (2^N)-1 nonempty subsets. So it grows exponentially. And you need to process all the subsets. Hence, your attempt should be to reduce it to 2^(N/2)+2^(N/2) since it is way less than (2^N). The problem may fool you to think it can be solved in N^3 time. I seriously doubt it if N >4. I also doubt whether a polynomial time exists for this problem. For N > 10000, this program could take as long as one minute to execute in a powerful machine. Someone suggested to use nested for loop. You have to be very careful in optimizing this for loop. The subset {2,3,4,5,6,7,8,9} with eight integers can be written as: {3,4,.....9,2} = {4,5,.....9,2,3} = ..... whose average is the same. You may wish to factor these things. It's easy. For 2^10000 subsets, you will gain on some serious execution time. Though the project restricts sorting, just to test, you may wish to sort the input while you insert it. It's easier to process sorted list.e.g. For a sorted list the average of the first half would be lesser than the second half. So you can switch that mod function accordingly. Last edited: 15-Oct-11 02:48 PM
EastSidaz · Oct 15, 2011 2:39 PM
What is the input size of your project?
EastSidaz · Oct 15, 2011 2:45 PM
Thanks guys! The input size can be small. As I said earlier, it can be {2, 2} or { 9, 5, 7, 2}. But no more than 4 digit in the set. Thanks again!
priya_k · Oct 15, 2011 3:39 PM
If the input size is <5 then the program is trivial.
EastSidaz · Oct 15, 2011 3:57 PM
Last edited: 16-Oct-11 02:43 PM
default061 · Oct 16, 2011 4:56 AM
This conversation is preserved exactly as it was on the original Sajha.com and can't accept new replies.
Start a New Discussion