Challenge: Word Shuffles

Lab Java Intermediate 20 points

Print every arrangement of the letters of a word (all letters different), one per line, in alphabetical order, then count: k. Use backtracking – sort the letters first so the arrangements come out in order.

Input

One word of 1 to 6 different letters.

Output

Every arrangement, then count: k.

Example

Input

cab

Output

abc
acb
bac
bca
cab
cba
count: 6

Sample input available Sample output available

Editor

Java

Hints

Sort the letters, then try them in order at each position.

Use a boolean[] used to skip letters already placed, and undo after the recursive call.

Solution explanation

There are n! arrangements (6 for 3 letters, 720 for 6), so the work is O(n! · n). Because we try letters in sorted order, the output is alphabetical with no extra sorting.

Show solution

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static char[] letters;
    static boolean[] used;
    static StringBuilder out = new StringBuilder();
    static int count = 0;

    static void arrange(StringBuilder current) {
        if (current.length() == letters.length) {
            out.append(current).append('\n');
            count++;
            return;
        }
        for (int i = 0; i < letters.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.append(letters[i]);
            arrange(current);
            current.deleteCharAt(current.length() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        letters = sc.next().toCharArray();
        Arrays.sort(letters);
        used = new boolean[letters.length];
        arrange(new StringBuilder());
        out.append("count: ").append(count);
        System.out.println(out);
    }
}

Output

Answer