// -----------------
// Permutations.java
// -----------------

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

final class Permutations {
    /**
     * O(n!) in space
     * O(n!) in time
     */
    public static List<String> eval (String s) {
        final List<String> x = new ArrayList<String>();
        if (s.length() == 0) {
            return x;}
        if (s.length() == 1) {
            x.add(s);
            return x;}
        for (int i = 0; i != s.length(); ++i) {
            final char         c = s.charAt(i);
            final List<String> y = eval(s.substring(0, i) + s.substring(i + 1, s.length()));
            for (String t : y)
                x.add(c + t);}
        return x;}}

final class PermutationsTest {
    public static void main (String[] args) {
        System.out.println("Permutations.java");

        {
        List<String> x = Permutations.eval("");
        assert x.equals(new ArrayList<String>());
        }

        {
        List<String> x = Permutations.eval("a");
        assert x.equals(Arrays.asList("a"));
        }

        {
        List<String> x = Permutations.eval("ab");
        assert x.equals(Arrays.asList("ab", "ba"));
        }

        {
        List<String> x = Permutations.eval("abc");
        assert x.equals(Arrays.asList("abc", "acb", "bac", "bca", "cab", "cba"));
        }

        {
        List<String> x = Permutations.eval("aaa");
        assert x.equals(Arrays.asList("aaa", "aaa", "aaa", "aaa", "aaa", "aaa"));
        }

        System.out.println("Done.");}}