Courses‎ > ‎AP Computer Science 2‎ > ‎Konstantinovich‎ > ‎

2017-03-09

posted Mar 8, 2017, 8:46 PM by Samuel Konstantinovich   [ updated Mar 9, 2017, 11:24 AM ]
Goal: Reparations! Complete this method on git under /06/Quiz2Redux.java

Announcements:
1. USACO will be graded Monday. You should try to finish the silver (even a slow version) ASAP, I will give some hints tomorrow for a better version.
2. Today's work will be due Tuesday so that you have at least 1 non-overlapping work day. It was meant to be a quiz, so it should be solveable.
3. A few of the presenters from Friday’s trip agreed to share their presentation slides with us. See the links below if interested:


Recursive backtracking is really good for generating all possibilities. All possible paths, sequence of moves, permutations/combinations/sets of elements.

Consider
boolean checkSum(n,data){
 //does any subset of elements in data add up to n?
}

checkSum( 40,[1,3,5,7,11,13,17]) -> True
How do we determine this on paper?
How do we make a program check this for us?

Consider
boolean checkSum(data1,data2){
 //does any NONZERO subset of elements in data1 add up to
 // any NONZERO subset of elements of data2?
}

checkSum( [1,3,5,7,11,13,17],[1,3,5,7,11,13,17]) -> True (same list)
checkSum( [1,3,5],[8,13,17]) -> True (8) 
checkSum( [1,3,6],[8,13,17]) -> False
checkSum( [1,3,5],[3,13,17]) -> True (3)
checkSum( [1,3,4,5],[19,13,17]) -> True (13)
checkSum( [9,14,18],[8,13,17]) -> False




Now consider:
[a,b,c,d]
How can we generate the powerset of this? (powerset is all subsets including the empty set and original set)
{ {}, {a}}  is the powerset of {a}
{ {}, {a}, {b}, {a,b}} is the powerset of {a,b}
{ {}, {a}, {b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}} is the powerset of {a,b,c}
{ {}, {a}, {b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}, 
  {d}, {a,d}, {b,d}, {a,b,d}, {c,d}, {a,c,d}, {b,c,d}, {a,b,c,d}}  is the powerset of {a,b,c,d}

This is a slightly modified version of the quiz to be completed and placed on github. 

Write an auxiliary method help( ArrayList<String> words,  /*more*/  )

It should create all possible subsets of letters from the String parameter of combinations, and add them to an ArrayListof Strings.
It is to be called inside the combinations method. 
Assume there are no duplicate letters in the string provided to combinations.
The order of the ArrayList is not important, only that all sequences are generated.
The letters that occur in each sequence should be in the same order as the original string.
The result is an ArrayList with:
  -The empty string, 
  -All 1 character strings, 
  -All 2 character strings, 
     ... 
   -Up to and including the string with all the characters.Since the ArrayList is sorted, the order is predictable

e.g.

- combinations("abcd") results in:
[, a, ab, abc, abcd, abd, ac, acd, ad, b, bc, bcd, bd, c, cd, d]

- combinations("kji") results in:
[, i, j, ji, k, ki, kj, kji]

(Note: In all cases: the first string is an empty string!)


import java.util.*;
public class Quiz2Redux{  
  /*Returns an ArrayList<String> that contains all subsets of the
   *characters of String s. Assume s has no duplicate characters.
   *the characters should appear in the same order that they occur 
   *in the original string.
   */
  public static ArrayList<String> combinations(String s){
      ArrayList<String>words = new ArrayList<String>();
      help( words , /*fill this in with more */);
      Collections.sort(words);
      return words;
  }
  
  private static void help( ArrayList<String> words, 
                             /*fill this in with more arguments*/ ){
   /*METHOD TO BE WRITTEN BY YOU.*/ 
  }
}




Comments