Every arrangement of the letters, each one once

Given a word, list every arrangement of its letters. If a letter appears more than once, each distinct arrangement must appear only once.

Sort the letters first and print the arrangements in the order the walk produces, which comes out alphabetical.

Worked example#

For abc there are six:

abc acb bac bca cab cba

For aab there are only three, not six:

aab aba baa

Swapping the two as changes nothing you can see, so those arrangements are the same one.

The idea#

Backtracking again, with one difference from subsets: each position can use any letter not already used, not just the ones after it. So instead of a start index you need a record of which letters are taken.

walk(built):
    if built is full: record it, return
    for each letter:
        if it is already used: skip
        mark used, append it            # choose
        walk(built)                     # explore
        remove it, unmark               # un-choose

The duplicate problem, and the one-line fix#

For aab the plain walk produces six arrangements, and three of them are repeats. Collecting into a set would remove them after the fact, having done twice the work to build them.

The fix is to stop the repeat being made at all. Sort the letters first, so equal letters are neighbours, then at each position:

Skip a letter if it equals the one before it and that one is not currently used.

Read that condition carefully, because the "not used" half is the part that is easy to get wrong.

If the previous equal letter is not used, it is available at this very position, so the branch starting with it has already been walked, or is about to be. Taking this one instead produces the identical arrangement, so skip.

If the previous equal letter is used, it was taken at a shallower position. This one is a genuinely different second a, so it must be allowed.

That single line turns an n-factorial walk with duplicates into one that generates each distinct arrangement exactly once.

Constraints#

• 1 <= length <= 8
• Lowercase letters only