problem 3.7 bugs/suggestions...

[GoogleCodeExporter]

1, need to include <iterator> to use ostream_iterator
2, the test/explanation example provided in main() is problematic, since the 
integer range is 0-6, then F should be of size 7; Furthermore, the problem does 
not assume |A|=|B|=m=n=|S|, so it is better to use another parameter to let the 
function know "N-1";
3, from my personal viewpoint, the whole explanation is kind of confusing. 
Without working on an example, I do not quite understand what the problem wants 
and what the explanation means...I think, it is better to use input/output to 
clarify. For example, the inputs are simply S, A and B; the output should be an 
array F such that |F|=|S| and F[i] should be the smallest number that is 
equivalent to S[i]. You can also define this as the so-called "weakest" 
equivalence.

Original issue reported on code.google.com by fuban...@gmail.com on 9 Apr 2013 at 6:05

[GoogleCodeExporter]

Thanks for your report. We have fixed this problem and are ready to push the 
change very shortly. Right now, I will paste the update code in below:

int backtrace(const vector<int> &F, int idx) {
  while (F[idx] != idx) {
    idx = F[idx];
  }
  return idx;
}

/*
 * A and B encode pairwise equivalences on a cardinality N set whose elements
 * are indexed by 0, 1, 2, ..., N-1.
 *
 * For example A[i] = 6 and B[i] = 0 indicates that the 6 and 0 are to be
 * grouped into the same equivalence class.
 *
 * We return the weakest equivalence relation implied by A and B in an array
 * F of length N; F[i] holds the smallest index of all the elements that
 * i is equivalent to.
 */
vector<int> compute_equival_classes(const int &n, const vector<int> &A,
                                    const vector<int> &B) {
  // Each element maps to itself
  vector<int> F(n);
  iota(F.begin(), F.end(), 0);

  for (int i = 0; i < A.size(); ++i) {
    int a = backtrace(F, A[i]), b = backtrace(F, B[i]);
    a < b ? F[b] = a : F[a] = b;
  }

  // Generate the weakest equivalence relation
  for (int &f : F) {
    while (f != F[f]) {
      f = F[f];
    }
  }
  return F;
}

If you have any problem or comments, please feel free to contact us.
Tsung-Hsien

Original comment by TsungHsi...@gmail.com on 9 Apr 2013 at 6:14

[GoogleCodeExporter]

in the for loop you are still assuming that B.size() = A.size() aren't you?


for (int i = 0; i < A.size(); ++i) { // here why A.size() ?
    int a = backtrace(F, A[i]), b = backtrace(F, B[i]);
    a < b ? F[b] = a : F[a] = b;
  }

Original comment by tplee...@gmail.com on 21 Apr 2013 at 8:55

[GoogleCodeExporter]

we are assuming that B.size() = A.size() because these arrays encode pairs of 
elements that are taken to be equivalent. 

you can take a look at the new wording of the problem which may help (it's 
attached as a PNG)

thank you for your taking the trouble to write to us, we appreciate your 
feedback. please write to us (directly or via google code) whenever you need 
clarifications or have suggestions (like the one above)

cheers,
adnan

Original comment by adnan.a...@gmail.com on 22 Apr 2013 at 4:34

Attachments:

• [Screen Shot 2013-04-21 at 11.32.09 PM.png](https://storage.googleapis.com/google-code-attachments/elements-of-programming-interviews/issue-6/comment-3/Screen Shot 2013-04-21 at 11.32.09 PM.png)