Mathematically determine if two strings are permutations of each other

Question

I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each string to char codes and perform mathematical operations on them to determine equivalence.

My idea was to sum up the char values of each and compare. Then multiply the values of each string and compare. If both the sum and product are the same for both strings then the strings are permutations of each other.

Note: this is assuming strings of equal length. instantly reject strings of different length.

example:
A = "abcd" = [1, 2, 3, 4] -> Sum: 10 -- Product: 24
B = "bcda" = [2, 3, 4, 1] -> Sum: 10 -- Product: 24

Sum A = Sum B and Product A = Product B therefore A is a permutation of B

Is there a case where this would not hold true? how would one go about proving this. I want it to be true because it would be more space efficient than https://stackoverflow.com/a/2145221/2001647 which also runs in O(n)

Answer 1

You need a function that uniquely maps multi-sets of symbols to numbers -- a bijection. Here is one example that is easy to understand.

Say your string is $w = w_1 \cdot \dots \cdot w_n$ over alphabet $\{1, \dots, k\}$. Denote with $m(w)$ the multi-set of its characters. Let $p_i$ the $i$-th prime number. Then,

$\qquad\displaystyle p(w) = \prod_{i=1}^n p_{w_i}$

has the required property, i.e.

$\qquad p(v) = p(w) \iff m(v) = m(w) \iff v$ is a permutation of $w$.

This follows directly from the uniqueness of prime factorizations and commutativity of integer multiplication.

This works fine and fast for small alphabets (say, Roman) but is horrible for large ones (say, Unicode).

---

In the unit-cost RAM model, of course, this has linear running-time and constant space cost, assuming a fixed and finite alphabet. But that's not a very useful model here.

For the logarithmic cost model, here's a start. The $k$-th prime is smaller than $k (\ln k + \ln \ln k)$, so the resulting number $p(w)$ has less than $n \cdot \log_2(k (\ln k + \ln \ln k))$ bits (worst-case bound from string $k^n$). Depending on the multiplication algorithm you use, you can derive the time to compute this.

---

More practical alternatives:

1. Define canonical forms; for instance, sort the strings w.r.t. some ordering on your alphabet. Strings are permutations of each other if they have the same canonical form. Time: $\Theta(n \log n)$ per string, then $O(n)$ comparison.
2. Explicitly create the multi-set of characters in the strings and compare, e.g. using a dictionary data structure. One possible advantage is that you can update this set according to string operations. Time: $O(n \log k)$ when using balanced BSTs, plus $O(k)$ comparison of the dictionaries.
3. Similar: compute the Parikh vectors of the strings.

Answer 2

Your algorith isn't correct.

Take $abbc = [1, 2, 2, 3]$ and $acd = [1, 3, 4]$. Their product is $12$ and their sum $8$, yet they aren't permutations of each other; they don't even have the same length.