CSCI 1101 – Winter 2012
Laboratory Report 6
SOLUTIONS
Exercise 2: Write a program that reads words into two ArrayLists list1 and list2 and then creates a third ArrayList that contains words which are common to both list1 and list2. You may assume that the strings are entered as words separated by a space on a single line and the end is signaled by “-1” (String -1). You can use keyboard.next() to read each word.
A sample dialog is shown below:
Enter words on one line, end with -1
java c pascal ada java c++ -1
Enter words on one line, end with -1
c pascal java lisp lisp -1
[java, c, pascal, ada, java, c++]
[c, pascal, java, lisp, lisp]
Array List with common strings:
[c, pascal, java]
SOLUTION: (Core part only)
int i,j;
ArrayList<String> result = new ArrayList<String>();
if (list1.size() >= list2.size())
{
for(i=0;i<list2.size();i++)
{
boolean match = false;
for(j=0;j<list1.size()&!match; j++)
if ((list2.get(i)).equals(list1.get(j)))
{
result.add(list2.get(i));
match = true;
}
}
}
else if (list2.size() > list1.size())
{
for(i=0;i<list1.size();i++)
{
boolean match = false;
for(j=0;j<list2.size()&!match; j++)
if ((list1.get(i)).equals(list2.get(j)))
{
result.add(list1.get(i));
match = true;
}
}
}
Exercise 3: Write a program that reads words into an ArrayList list1 and creates another ArrayList list2 that has the same words in list1 but no duplicates.
A sample dialog is shown below:
Enter words on one line, end with -1
java c pascal ada java java ada c++ -1
Array List with no duplicates:
[java, c, pascal, ada, c++]
Solution:
int i,j;
ArrayList<String> result = new ArrayList<String>();
for(i=0;i<a.size();i++)
{
String item = a.get(i);
boolean repeat = false;
j=0;
while (!repeat & j<result.size())
{
if (item == result.get(j))
repeat=true;
j++;
}
if (!repeat)
result.add(item);
}
Exercise 4: The objective of this exercise is to write a program that reads a number of Strings and sorts them by inserting each string into the appropriate place in an arraylist. For example, if the strings are:
Shai
Ralph
Hillary
Tom
Barbara
Fred
Then the arraylist should grow as follows:
[Empty]
[Shai]
[Ralph, Shai]
[Hillary, Ralph, Shai]
[Hillary, Ralph, Shai, Tom]
[Barbara, Hillary, Ralph, Shai, Tom]
[Barbara, Fred, Hillary, Ralph, Shai, Tom]
The algorithm to sort is simple. As you read each name (say name1), compare it with each name (say name2) stored in the arraylist starting from the index 0. As soon (name1.compareTo(name2) >0), that is the right index to put name1. Be sure that you do not cross the arraylist boundary.
Solution:
import java.util.ArrayList;
import java.util.Scanner;
public class ArrayListSort
{
public static void main(String[] args)
{
Scanner keyboard = new Scanner(System.in);
ArrayList<String> namesList = new ArrayList<String>();
System.out.println("Enter names, end with -1:");
String newWord = keyboard.nextLine();
while (!newWord.equals("-1"))
{
boolean found = false;
int i;
for(i=0; i<namesList.size()&!found; i++)
{
if (newWord.compareTo(namesList.get(i))<0)
found = true;
}
if (found)
namesList.add(i-1, newWord);
else
namesList.add(newWord);
System.out.println(namesList);
newWord = keyboard.nextLine();
}
}
}
Exercise 5: Write a program that produces random permutations of the numbers 1 to 10. (Note: “Permutation” is a mathematical name for an arrangement.) For example, there are six permutations of the numbers 1,2,3: 123, 132, 231, 213, 312, and 321.
To generate a random permutation, you need to fill an ArrayList with the numbers 1 to 10 so that no two entries of the array have the same contents. You could do it by brute force, by calling Random.nextInt() until it produces a value that is not yet in the array. Instead, you should implement a smarter method. Make a second ArrayList and fill it with the numbers 1 to 10. Then pick one of those at random, remove it, and append it to the permutation ArrayList. Repeat ten times. This will give the first list, List 1.
Repeat it to generate 10 lists. It doesn’t matter if two of the 10 lists are identical – the probability of this happening is small.
Example output is shown below:
List 1: 4 6 8 1 9 7 10 5 3 2
List 2: 6 8 1 7 3 4 9 10 5 2
List 3: 2 4 9 6 8 1 10 5 7 3
List 4: 8 5 4 3 2 9 6 7 1 10
List 5: 10 3 2 6 8 9 5 7 4 1
List 6: 9 10 3 2 1 5 6 8 4 7
List 7: 3 8 5 9 4 2 10 1 6 7
List 8: 3 2 4 5 7 6 9 8 10 1
List 9: 4 1 5 10 8 3 6 2 7 9
List 10: 3 5 2 4 1 7 9 6 8 10
import java.util.ArrayList;
public class ArrayListRandom
{
public static void main(String[] args)
{
for(int i=1; i<=10; i++)
{
ArrayList<Integer> numbers = new ArrayList<Integer>();
ArrayList<Integer> myList = new ArrayList<Integer>();
for(int j=0; j<10;j++)
numbers.add(j+1);
for(int k=1; k<=10;k++)
{
int rand = (int)(Math.random()*numbers.size());
int num = numbers.remove(rand);
myList.add(num);
}
System.out.println("List " + i +":" + myList);
}
}
}