0
$\begingroup$

I have a problem domain that has several kinds of symmetries. I will try to keep this as general as possible. Given an array of strings:

["4533", "1234", ...]

The two symmetries that I have in the problem is that you can permute any two "columns", for example "123" is equivalent to "213" (all strings are the same length, and the column permutations are shared between them all). But also, the digits themselves can be permuted (like a cryptoquote) so "111233444" is equivalent to "222344555" (all strings share an alphabet and alphabet permutations are shared by them all). I would like an efficient algorithm to find the lexicographic minimum version of the array of strings.

E.g. ["4533", "1234", ...] after swapping the 3/4 columns for the 1/2 columns becomes ["3345", "3412", ...] and after mapping the digits 3->1, 4->2, 5->3, 1->4, 2->5 you get ["1123", "1245", ...] which is the lexicographic minimum (using an alphabet of these 5 characters).

My current implementation does this: psuedocode

column map (1, 2, 3...)
digit map ()

smallest_v <- original_v

loop through all permutations of column map
  clear digit map
  v <- permute original array based on column map
  s <- loop through strings of v
    c <- loop through characters of s
      if c is new character append c to digit map
  v <- permute original array on column map and digit map
  if v < smallest_v
    smallest_v <- v
return smallest_v

more or less. I'm curious if this is a known symmetry or if others can think of a more efficient way of finding the unique representation of this equivalence class.

Edit

Perhaps a better way to explain the problem is using a 2D array. with R rows (between 0-10) and C columns (between 0-10). The elements of each cell is a number (between 0-31).

The symmetries of the problem is that you can permute the columns, permute all of the characters, (cryptoquote style).. e.g.

4 5 3 3 ->  column   -> 3 3 4 5 -> character -> 1 1 2 3
1 2 3 4 ->permutation-> 3 4 1 2 ->permutation-> 1 2 4 5
$\endgroup$
6
  • $\begingroup$ I don't understand what you mean by "columns" if you have a list of strings. I don't understand what 'permute any two "columns"' means - what role is the 'two' playing? I don't understand what are the allowed operations. You describe operations acting on a single string, but I don't understand how they act on the list. Can I "permute" just one string, or must I permute them all in the same way? Can you edit your post to make the problem statement clearer? $\endgroup$
    – D.W.
    Jul 20, 2023 at 7:29
  • $\begingroup$ Can you tell us about the problem size you have to do with? Typically how many strings are in a list, how many characters in a string, how many characters in the alphabet? $\endgroup$
    – D.W.
    Jul 20, 2023 at 7:31
  • $\begingroup$ I will edit as soon as I can. But I will try to answer your questions here too. By nth column I mean the nth letter in the string. All of the strings are the same length, so If you permute the columns you are uniformly changing the order of the characters in all of the strings. So you have two permutation symmetries one for the order of the characters in the strings, and one for the choice of characters in the alphabet. Typically the problem domain will have between 0 and 10 words all the same length with length between 0 and 8 $\endgroup$ Jul 20, 2023 at 11:16
  • $\begingroup$ Thank you for the clear problem statement. Don't use "Edit:". Instead, revise the question so it is self-contained and reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755 $\endgroup$
    – D.W.
    Jul 21, 2023 at 17:34
  • $\begingroup$ What is your objective? What exactly you want to compute? $\endgroup$
    – Michael
    Jul 21, 2023 at 22:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.