# Rearranging strings to minimise storage in a trie

I'm currently thinking about the following problem.

## Problem

Input: a set $W$ of strings over an alphabet $\Sigma$.

Goal: permute the characters in each string so that the trie that will contain the rearranged strings has as few edges as possible.

(by "permuting" and "rearranging", I mean that any permutation of the characters is valid).

## Example

Given strings $S=$"ABRACADABRA" and $T=$"BARRACUDA", storing them without rearrangement would require a trie of size 20, since they share no common prefix; however, if we are allowed to rearrange them, we can obtain the following optimal solution of size 12:

0-A-B-R-A-C-A-D-R-A-B-A (S')
\
U     (T')


(where 0 denotes the root, and $S'$ (resp. $T'$) is the rearranged $S$ (resp. $T$)).

## Question(s)

Has this problem been studied before, and can you give me references? What is its complexity (for $|W|\geq 3$; the problem is easy otherwise)?

• What kinds of rearrangements do you permit? Arbitrary permutations? – Dave Clarke Oct 5 '11 at 14:12
• I had the same question as Dave. Can you edit the question so that people do not have to read the comments to understand what you are asking? – Tsuyoshi Ito Oct 5 '11 at 15:31
• Do you have an application in mind? – Raphael Oct 5 '11 at 17:45
• In the graph example, you are storing sets of edges, while your question seems to suggest that you are storing multisets (i.e., your strings may contain the same character more than once). The case of sets sounds easier to me... – Jukka Suomela Oct 5 '11 at 21:56
• Is alphabet Σ fixed or specified as part of the input? (Your comment suggests that it is part of the input.) – Tsuyoshi Ito Oct 6 '11 at 23:39