Slightly improved version (deals with multiple characters together
instead of one at a time):
# Pack.py
def Pack(Words):
if not Words:
return ''
# The method is to build up the result by adding letters at the
beginning
# and working forward, and by adding letters at the end, working
backwards,
# meanwhile shrinking the words in the list.
Words = list(Words) # Don't mutate the original
Initial = ''
Final = ''
while True:
# It is safe to add an initial letter (of one or more of the
words) if
# EITHER There is no word that contains it as
# a non-initial letter but not as an initial letter.
# OR All words start with it.
while True:
FirstLetters = set(w[0] for w in Words)
FirstLettersSafe = sorted(ch for ch in FirstLetters if
all(w[0]==ch for w in Words)
or not any(ch in w[1:] and w[0]!=ch for w in Words))
# sorted() to make the answer deterministic
# (not dependent on set ordering)
if not FirstLettersSafe:
break
AnyProgress = True
Initial += ''.join(FirstLettersSafe) # Build up the
answer from the beginning
Words = [ (w[1:] if w[0] in FirstLettersSafe else w) for w
in Words ]
Words = [ w for w in Words if w != '']
if not Words:
return Initial + Final
# It is safe to add a final letter (of one or more of the words) of
# EITHER There is no word that contains it as
# a non-final letter but not as a final letter.
# OR All words end with it.
while True:
LastLetters = set(w[-1] for w in Words)
LastLettersSafe = sorted(ch for ch in LastLetters if
all(w[-1]==ch for w in Words)
or not any(ch in w[:-1] and w[-1]!=ch for w in Words))
# sorted() to make the answer deterministic
# (not dependent on set ordering)
if not LastLettersSafe:
break
Final = ''.join(LastLettersSafe) + Final # Build up the
answer from the end
Words = [ (w[:-1] if w[-1] in LastLettersSafe else w) for w
in Words ]
Words = [ w for w in Words if w != '']
if not Words:
return Initial + Final
if not (FirstLettersSafe or LastLettersSafe):
break # stuck
# Try all the possibilities for the next letter to add at the
beginning,
# with recursive calls, and pick one that gives a shortest answer:
BestResult = None
for ch in FirstLetters:
Words2 = list( (w[1:] if w[0] == ch else w) for w in Words )
Words2 = [ w for w in Words2 if w != '' ]
res = ch + Pack(Words2)
if BestResult is None or len(res) < len(BestResult):
BestResult = res
return Initial + BestResult + Final
print(Pack(['APPLE', 'PIE', 'APRICOT', 'BANANA', 'CANDY']))
Rob Cliffe
--
https://mail.python.org/mailman/listinfo/python-list
