p234-heap.cpp

//
// Switching Channels
// Uses exhaustive search through all possible programs
// This version does not use next_permutation!
// Christopher Vo (cvo1 at cs.gmu.edu)
//
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

struct align {
  int p, t;
  bool operator<(const align & o) const { return p < o.p; }
};

int main(int argc, char * argv[])
{
  int i, j, k, num_p, num_a, fact, num_d = 1;
  int p[9], c[9], p_best[9], err_curr[9], err_best[9], tmp[9];
  align a[9];
  while (cin >> num_p && num_p != 0) {
    // get input
    for (i = 0; i < num_p; i++)
      cin >> p[i];
    cin >> num_a;
    for (i = 0; i < num_a; i++)
      cin >> a[i].p >> a[i].t;
    // sort alignment points by priority
    sort(a, a + num_a);
    // evaluate first schedule as best-so-far
    copy(p, p + num_p, p_best);
    for (i = 0, j = 0; i < num_p; i++)
      tmp[i] = j = j + p_best[i];
    for (i = 0; i < num_a; i++) {
      for (j = 0, err_best[i] = INT_MAX; j < num_p; j++) {
        int diff = abs(a[i].t - tmp[j]);
        if (diff < err_curr[i])
          err_curr[i] = diff;
      }
    }
    // go through n! permutations
    fill_n(c, 9, 0);
    i = 1;
    while (i < num_p) {
      if (c[i] < i) {
        int swap = i % 2 * c[i];
        int t = p[swap];
        p[swap] = p[i];
        p[i] = t;
        // compute error
        for (j = 0, k = 0; j < num_p; j++)
          tmp[j] = k = k + p[j];
        for (j = 0; j < num_a; j++) {
          for (k = 0, err_curr[j] = INT_MAX; k < num_p; k++) {
            int diff = abs(a[j].t - tmp[k]);
            if (diff < err_curr[j])
              err_curr[j] = diff;
          }
        }
        // compare error lexicographically to best
        if (lexicographical_compare(err_curr, err_curr + num_a,
            err_best, err_best + num_a)) {
          copy(p, p + num_p, p_best);
          copy(err_curr, err_curr + num_a, err_best);
        }
        c[i]++;
        i = 1;
      } else {
        c[i++] = 0;
      }
    }
    printf("Data set %d\n  Order: ", num_d++);
    for (i = 0; i < num_p; i++)
      printf("%d ", p_best[i]);
    for (i = 0, j = 0; i < num_a; i++)
      j += err_best[i];
    printf("\n  Error: %d\n", j);
  }
  return 0;
}

p234.cpp

//
// Switching Channels
// Uses exhaustive search through all possible programs
// Christopher Vo (cvo1 at cs.gmu.edu)
//
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

struct align {
  int p, t;
  bool operator<(const align & o) const { return p < o.p; }
};

int main(int argc, char * argv[])
{
  int i, j, k, num_p, num_a, fact, num_d = 1;
  int p[9], p_best[9], err_curr[9], err_best[9], tmp[9];
  align a[9];
  while (cin >> num_p && num_p != 0) {
    // get input
    for (i = 0; i < num_p; i++)
      cin >> p[i];
    cin >> num_a;
    for (i = 0; i < num_a; i++)
      cin >> a[i].p >> a[i].t;
    // sort alignment points by priority
    sort(a, a + num_a);
    // evaluate first schedule as best-so-far
    copy(p, p + num_p, p_best);
    for (i = 0, j = 0; i < num_p; i++)
      tmp[i] = j = j + p_best[i];
    for (i = 0; i < num_a; i++)
      for (j = 0, err_best[i] = INT_MAX; j < num_p; j++)
        err_best[i] = min(err_best[i], abs(a[i].t - tmp[j]));
    // go through n! permutations
    for (fact = 1, i = 2; i <= num_p; i++)
      fact *= i;
    for (i = 0; i < fact; i++) {
      next_permutation(p, p + num_p);
      // compute error
      for (j = 0, k = 0; j < num_p; j++)
        tmp[j] = k = k + p[j];
      for (j = 0; j < num_a; j++)
        for (k = 0, err_curr[j] = INT_MAX; k < num_p; k++)
          err_curr[j] = min(err_curr[j], abs(a[j].t - tmp[k]));
      // compare error lexicographically to best
      if (lexicographical_compare(err_curr, err_curr + num_a, err_best,
          err_best + num_a)) {
        copy(p, p + num_p, p_best);
        copy(err_curr, err_curr + num_a, err_best);
      }
    }
    printf("Data set %d\n  Order: ", num_d++);
    for (i = 0; i < num_p; i++)
      printf("%d ", p_best[i]);
    for (i = 0, j = 0; i < num_a; i++)
      j += err_best[i];
    printf("\n  Error: %d\n", j);
  }
  return 0;
}