Write a program called TwoSets in Java that reads a text file, in.txt, that cont
ID: 3835617 • Letter: W
Question
Write a program called TwoSets in Java that reads a text file, in.txt, that contains a list of positive integers (duplicates are possible) separated by spaces and/or line breaks. After reading the integers, the program saves them in a singly linked list in the same order in which they appear in the input file. Then, without changing the linked list, the program prints out Yes if the set of integers includes two subsets with equal averages (the averages might not always be integers). Otherwise (if every two subsets have different averages), the program prints out No. Assume that in.txt contains at least two integers.
Examples:
If in.txt contains 5 5, the program must print out Yes. In this case, the first subset is {5} with an average of 5; and the second subset is {5} with an average of 5.
If in.txt contains 3 2 7 1, the program must print out Yes. The first subset is {1, 3} with an average of 2; and the second sunset is {2} with an average of 2.
If in.txt contains 3 8 1 4, the program must print out Yes. The first subset is {1, 3, 8} with an average of 4; the second subset is {4} with an average of 4.
If in.txt contains 5 1 4, the program prints out No. All possible collections of two subsets are: {1} and {4}; {1} and {5}; {4} and {5}; {1} and {4, 5}; {1, 5} and 4; {1, 4} and {5}. In each collection, the two subsets have different averages.
If in.txt contains 9 2 8 4, the program must print out No. All possible collections of two subsets are: {2} and {4}; {2} and {8}; {2} and {9}; {4} and {8}; {4} and {9}; {8} and {9}; {4, 8} and {9}; {4} and {8, 9}; {4, 9} and {8}; {2} and {8, 9}; {2, 8} and {9}; {8} and {2, 9}; {2, 4} and {9}; {2} and {4, 9}; {4} and {2, 9}; {2, 4} and {8}; {2} and {4, 8}; {4} and {2, 8}; {2} and {4, 8, 9}; {4} and {2, 8, 9}; {8} and {2, 4, 9}; {9} and {2, 4, 8}; {2, 4} and {8, 9}; {2, 8} and {4, 9}; {2, 9} and {4, 8}. In each collection, the two subsets have different averages.
If in.txt contains 10 3 8 5 4, the program must print out Yes. The first subset is {3, 10} with an average of 6.5; and the second subset is {5, 8} with an average of 6.5. Another solution is {3, 5} and {4}. The program does not need to find all solutions. It stops after finding the first solution and prints out Yes.
Your program has to:
(a) Implement a linked list from scratch.
(b) Read the integers from the file in.txt and store them into the linked list. The integers should be stored in the same order as they appear in the input file in.txt.
(c) Work on the linked list in order to find out whether the list has two sublists with equal averages. No additional data structures are allowed. All computations must be done in place on the original data structure. In other words, your program can use only one data structure (and only one instance of it),
the linked list, and some auxiliary scalar variables. No additional data structures are allowed, such as a second linked list, an array, string, etc.
d) Print Yes or No.
e) Your program should not modify the linked list, i.e., it should remain in its original form as it was read from the input file in.txt.
You are supposed to implement the linked list from scratch without using language libraries. For example, you are not allowed to use any built-in dynamic data structures, such as ArrayList or LinkedList. If you have any doubts whether you can use a particular construct, please feel free to email me.
Try to write short and simple programs. The efficiency of your program is not important. The purpose of this assignment is to check your ability to:
- Program in Java
- Design and implement a linked list
- Design, implement and analyze algorithms
Explanation / Answer
/*
* Java Program to Implement Singly Linked List
*/
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class SinglyLinkedList
{
protected Node start;
protected Node end ;
public int size ;
/* Constructor */
public SinglyLinkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
/* Function to insert an element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* Function to insert an element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
/* Function to display elements */
public void display()
{
System.out.print(" Singly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ " ");
}
}
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
public class AllSubsets
{
private ArrayList<Integer> cloneSet(ArrayList<Integer> input)
{
ArrayList<Integer> clone = new ArrayList();
for (int i = 0; i < input.size(); i++)
{
clone.add(input.get(i));
}
return clone;
}
public void findAllSubsets(ArrayList<ArrayList<Integer>> allSubsets, SinglyLinkedList set, int currIndex)
{
if (currIndex == set.getSize())
{
return;
}
int allSubSetsSize = allSubsets.size();
ArrayList<Integer> newSet;
for (int i = 0; i < allSubSetsSize; i++)
{
newSet = cloneSet(allSubsets.get(i));
newSet.add(set.start.getData());
if(null!=set.start.getLink()){
set.start = set.start.getLink();
}
allSubsets.add(newSet);
}
findAllSubsets(allSubsets, set, currIndex+1);
}
public ArrayList<ArrayList<Integer>> findAllSubsets(SinglyLinkedList set)
{
ArrayList<ArrayList<Integer>> allSubsets = new ArrayList();
allSubsets.add(new ArrayList<Integer>());
findAllSubsets(allSubsets, set, 0);
return allSubsets;
}
public static void readFromFile(String fileName,SinglyLinkedList set){
BufferedReader br = null;
FileReader fr = null;
try {
fr = new FileReader(fileName);
br = new BufferedReader(fr);
String sCurrentLine;
while ((sCurrentLine = br.readLine()) != null) {
set.insertAtEnd(Integer.valueOf(sCurrentLine));
}
} catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args)
{
AllSubsets solution = new AllSubsets();
ArrayList avrgeArr = new ArrayList();
SinglyLinkedList set = new SinglyLinkedList();
readFromFile("inputnumbers.txt",set);
ArrayList<ArrayList<Integer>> allSubsets = solution.findAllSubsets(set);
System.out.println("Subsets are: ");
double sum =0;
int elemCount =1;
boolean flag =false;
for (int i = 0; i < allSubsets.size(); i++)
{
sum =0;
ArrayList<Integer> tempSet = allSubsets.get(i);
for (int j = 0; j < tempSet.size(); j++)
{
System.out.print(tempSet.get(j) + ", " );
sum = sum +tempSet.get(j);
elemCount = j+1;
}
double avg = sum /elemCount;
if (!avrgeArr.contains(avg)){
avrgeArr.add(avg);
}
else{
flag = true;
}
System.out.println();
}
if(flag){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.