Anonymization of dataset preserving unique identities
The point of k-anonymity is that you can't uniquely identify your patients. So I will rephrase your question:


  Given two anonymized tuples $x$ and $y$, can we tell if they are anonymizations of the same person?


Let's suppose for purposes of contradiction that we could. Then this means there is a "meta-tuple" which uniquely identifies a patient. But this violates anonymity (unless $k=1$). So it is impossible.