Computer Science 15-100 (Sections T & U), Spring 2008
Class Notes:  Solving Combinatorial Problems Using Arrays and Combinatorial Iterators

Logistics

  1. Schedule
    1. today:  quiz 6, hw8a due, bonus 2 due
    2. hw8b due Friday
  2. Reading:
    1. Wikipedia pages referenced below

Topic Outline:

  1. Miscellany
    1. Inline static array allocations:
           a = { 1, 2, 3}; // will not work!
           a = new int[] { 1, 2, 3 }; // works!
       
    2. The super-handy java.util.Arrays class
           int[] x = { 1, 2, 3}, y = { 1, 2, 3};
           if (x == y) ...  // nope!
           if (x.equals(y)) ...  // nope again!
           if (Arrays.equals(x,y)) ...  // this works!
      Also has:  binarySearch, equals, fill, sort, and toString!
           int[] a = { 4, 3, 1, 2}
           System.out.println(Arrays.toString(a));
           Arrays.sort(a);
           System.out.println(Arrays.toString(a));
       
    3. The First Semi-Annual Hemi-Casual Demi-Factual Midi Play-Off
       
  2. Some Combinatorial Iterators
     
    File   Permutations.java   Combinations.java   BaseNCounting.java   PowerSet.java
    Meaning A permutation is an arrangement where order matters. A combination is an arrangement where order does not matter. This is a counter, or an odometer, where the digits are in baseN (0,1,...,n-1). A"power set" of a set is the set of all the possible subsets of that set.
    Sample
    Code    		 Permutation p = new Permutation(4,2);
    while (p.hasNext()) {
       int[] a = p.next();
       System.out.println(Arrays.toString(a));
    }    		 Combination c = new Combination(4,2);
    while (c.hasNext()) {
      int[] a = c.next();
      System.out.println (Arrays.toString(a));
    }    		 BaseNCounter bnc = new BaseNCounter(4,2);
    while (bnc.hasNext()) {
       int[] a = bnc.next();
       System.out.println(Arrays.toString(a));
    }    		 PowerSet ps = new PowerSet(4);
    while (ps.hasNext()) {
       int[] a = ps.next();
       System.out.println(Arrays.toString(a));
    }
    Sample
    Output    		 [0, 1]
    [0, 2]
    [0, 3]
    [1, 0]
    [1, 2]
    [1, 3]
    [2, 0]
    [2, 1]
    [2, 3]
    [3, 0]
    [3, 1]
    [3, 2]



         		 [0, 1]
    [0, 2]
    [0, 3]
    [1, 2]
    [1, 3]
    [2, 3]









         		 [0, 0]
    [0, 1]
    [0, 2]
    [0, 3]
    [1, 0]
    [1, 1]
    [1, 2]
    [1, 3]
    [2, 0]
    [2, 1]
    [2, 2]
    [2, 3]
    [3, 0]
    [3, 1]
    [3, 2]
    [3, 3]    		 []
    [0]
    [1]
    [0, 1]
    [2]
    [0, 2]
    [1, 2]
    [0, 1, 2]
    [3]
    [0, 3]
    [1, 3]
    [0, 1, 3]
    [2, 3]
    [0, 2, 3]
    [1, 2, 3]
    [0, 1, 2, 3]

     

  3. Some Combinatorial Problems (of a great, great many...)
    1. Permutations
      1. Travelling Saleman Problem
      2. Cryptarithm
      3. Krypto (w/counting in base 4 for the arithmetic operators)
      4. 7 Bridges of Konigsberg
         
    2. Combinations
      1. Poker Odds
         
    3. Base-N Counting
      1. Bin Packing
      2. Yahtzee Odds
         
    4. Power Sets
      1. Partition
      2. Subset Sum
      3. SAT:  The Boolean Satisfiability Problem

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem