TDD (练习) Anagrams 字符串全排列

问题描述

Write a program to generate all potential
anagrams of an input string.

For example, the potential anagrams of "biro" are

biro bior brio broi boir bori
ibro ibor irbo irob iobr iorb
rbio rboi ribo riob roib robi
obir obri oibr oirb orbi orib

从描述和举例来看，该问题是字符串的全排列。

• biro -> bior 是第二位和第三位的对调。
• 每一个变化都是字符串中的两个字符对调位置。

下面使用TDD 的方式完成该问题，希望可以从代码看出解题过程。

测试类

public class AnagramsTest {

    Anagrams anagrams = new Anagrams();

    //     // biro bior brio broi boir bori
    @Test
    public void should_biro_bior() {
        String except = "bior";
        String input = "biro";
        String result = new String(anagrams.swap(input.toCharArray(), 2, 3));
        assertEquals(except, result);
    }

    @Test
    public void should_brio_biro() {
        String except = "brio";
        String input = "biro";
        String result = new String(anagrams.swap(input.toCharArray(), 1, 2));
        assertEquals(except, result);
    }

    @Test
    public void should_broi_bior() {
        String except = "broi";
        String input = "biro";
        String result = new String(anagrams.swap(input.toCharArray(), 1, 2));
        result = new String(anagrams.swap(result.toCharArray(), 2, 3));
        assertEquals(except, result);
    }
    @Test
    public void should_doLoop_biro(){
        String input = "biro";
        List<String> list= anagrams.potential(input.toCharArray());
        assertEquals(list, Arrays.asList("biro", "ibro", "ribo", "oirb"));
    }
    @Test
    public void should_doLoopAndcursor_biro(){
        String input = "biro";
        List<String> list= anagrams.potential(input.toCharArray(),0);
        System.out.println(list);
        list= anagrams.potential(input.toCharArray(),1);
        System.out.println(list);

    }
    @Test
    public void should_iteration_bior(){
        String input = "biro";
        List<String> list= anagrams.potential(input.toCharArray(),0);
        System.out.println(list);
    }
}

实现类

public class Anagrams {


    public char[] swap(char[] chars, int i, int j) {
        char tmp = chars[j];
        chars[j] = chars[i];
        chars[i] = tmp;
        return chars;
    }

    public List<String> potential(char[] chars) {
        List<String> result = new ArrayList<>();

        for (int i = 0; i < chars.length; i++) {
            swap(chars, 0, i);
            result.add(new String(chars));
            swap(chars, 0, i);
        }

        return result;
    }

    public List<String> potential(char[] chars, int cursor) {
        List<String> result = new ArrayList<>();

        if (cursor >= chars.length) {
            result.add(new String(chars));

        } else {
            for (int i = cursor; i < chars.length; i++) {
                swap(chars, cursor, i);
                result.addAll(potential(chars, cursor + 1));
                swap(chars, cursor, i);
            }
        }
        return result;
    }

}