Print every way of arranging the letters of a word.
What to build
A recursive function that builds each arrangement one letter at a time.
Requirements
- Read a word whose letters are all different.
- Print every arrangement, one per line, in alphabetical order.
Input
One word.
Output
One line per arrangement.
Constraints
The word has from 1 to 6 different lowercase letters.
Example
Input:
ab
Output:
ab
ba
Why it works
Choosing each possible first letter and then arranging the rest covers everything exactly once. Because the letters are tried in sorted order, the results come out in alphabetical order.
Examples
Example 1 · Input
ab
Expected output
ab ba
Example 2 · Input
cba
Expected output
abc acb bac bca cab cba
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sort the letters first, so that the results come out in order.
Hint 2
For each letter, put it first and arrange the remaining letters.
Hint 3
A word with no letters left has exactly one arrangement.
Solution
Show one correct solution (try it yourself first)
def arrange(prefix, letters):
if not letters:
print(prefix)
return
for i in range(len(letters)):
arrange(prefix + letters[i], letters[:i] + letters[i + 1:])
arrange("", "".join(sorted(input())))