TransWikia.com

Writing a list of names, with a limited amount of "active" letters at a time. Algorithm to sort the names to reduce the amount of swapping letters?

Computer Science Asked by iouoneusername on October 31, 2020

While making name-tags for a dinner seating, I stumbled upon a problem which I can’t find any algorithm to solve, and I’m not sure where to begin.

The goal is to write the name of each dinner guest on a card, completing one name at a time.
The names are written with old-fashioned rubber stamps, so only 6 letters can be "active" at any given time. When a new letter is required, one of the active letters has to be swapped out for the new letter.

The problem is to sort the names in such an order, that I need to do the least amount of letter-swapping.

Example
I want to write the names:

  • Jack
  • Julie
  • Chuck

I can do this with 3 letter-swaps
Initial letters: J A C K H U
Write: Jack, Chuck

{swap A, C, K with L, I, E}

New active letters:
J L I E H U
Write: Julie

Now I want to find an algorithm that, given a list of names and a limit of active characters, provide the order of names and which letters to swap at each name, to reduce the total amount of letter-swaps.

Any ideas or pointers are welcome.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP