1
$\begingroup$

Let's have a set of digits $D = \{0, 1, \dots 9\}$ and n-tuples of digits.

Two tuples $(a_1, a_2, \dots a_n),(b_1, b_2, \dots b_n) $ are equivalent iff there exists a permutation of digits (bijection $P: D \rightarrow D$) , such that $\forall i: P(a_i) = b_i$.

For example, for 3-tuples: (1,2,3) is equivalent to (2,3,1), but not to (1,2,2). (1,2,2) is equivalent to (1,3,3), but not to (2,2,2), etc.

Equivalence relation partitions the set of tuples into equivalency classes. I have to find an algorithm, which loops through a large set of tuples and outputs just a single representative from each equivalency class. Do you have any ideas how to do that efficiently?

*** There is a large equivalency class of tuples, which have different digits only. Once I find one such tuple, I can ignore other such tuples. But what about other classes?


Can I have an extra question? What if I have some equivalence relation $\equiv$ on D, which splits D into equivalence classes. Two tuples are equivalent, when $\forall i : P(a_i) = b_i $ AND $a_i \equiv b_i$.

My idea was for each tuple $(a_1, a_2, \dots a_n)$ compute a "class-strip" $(c_1, c_2, \dots c_n)$, such that $c_i$ is the identifier of equivalency class of $a_i$ within D and $\equiv$. Then I can "group together" tuples with the same class-strip and use your method within each group. Does it make any sense? Do you have a better idea?

$\endgroup$
1
$\begingroup$

For every n-tuple, create a list (sorted by first number) of lists of indices. Exaple: 4-tuple (1,7,7,3), indices: ({},{1},{},{4},{},{},{},{2,3},{},{}). Sorted list of index lists (empty omitted) : ({1},{2,3},{4}) Quick to calculate, small to store, easy to compare.


Note: The n-tuples are ordered, right? otherwise (1,2,3) and (2,3,1) would be equivalent by identity. Therefore Derek's method does not work, since it would match (1,2,2) with (2,1,2).

EDIT

Extra question
My basic solution works for situation where all digits are in one congruence class. Therefore, to modify the result, do this for each class of digits separately. Example:
4-tuple: (1,7,7,4), and ≡ equivales odd numbers together and even numbers together.
indices: ({},{1},{},{},{4},{},{},{2,3},{},{}).
Now do the basic situation with partitions of space by the equivalence function.
evens: ({},{},{4},{},{}) //0,2,4,6,8
odds: ({1},{},{2,3},{},{}) //1,3,5,7,9
This is a complete representation of the 4-tuple, including the eq-func partition. Now omit empties, order intra-class and then order inter-class. Result:
[({1},{2,3}),({4})]
Where [] encapsulates entire solution, () encapsulates an equivalence class and {} is a list of indices of that digit in the n-tuple.
Now, this might be enough to represent the n-tuple, with the classes ordered by first index. However, it might be beneficial to comparison if the classes were ordered by size (ascending), that is a TODO.

$\endgroup$
  • $\begingroup$ You are right! I will delete my comment. $\endgroup$ – Derek Holt Oct 5 '16 at 13:42
  • $\begingroup$ That is smart! Thank you very much! $\endgroup$ – Ivan Kuckir Oct 5 '16 at 14:01
  • $\begingroup$ Extra question: but I will have to keep empty brackets () for empty equivalence classes, am I right? $\endgroup$ – Ivan Kuckir Oct 5 '16 at 16:45
  • $\begingroup$ @Ivan: Depends, for this the problem definition is incomplete - are the equivalence classes interchangeable? if no, then you will have to order the classes and keep empty lists for absent classes (with no element present in the n-tuple, logically including empty classes). $\endgroup$ – Honza Nav Oct 6 '16 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.