排列组合算法

给出一个字串，列出所有可能的排列组合

如果用for循环的话根本不知道需要多少层，所以这里的算法都是通过递归来完成。

排列

排列的思想就是从所有的可能选择数组里拿一个出来，放到目标数组，目标数组放满了则输出。

一个实现

    private static void arrangementSelect(String[] dataList, String[] resultList, int resultIndex) {
        int resultLen = resultList.length;
        if (resultIndex >= resultLen) { // 全部选择完时，输出排列结果
            System.out.println(Arrays.asList(resultList));
            return;
        }

        // 递归选择下一个
        for (int i = 0; i < dataList.length; i++) {
            // 判断待选项是否存在于排列结果中
            boolean exists = false;
            for (int j = 0; j < resultIndex; j++) {
                if (dataList[i].equals(resultList[j])) {
                    exists = true;
                    break;
                }
            }
            if (!exists) { // 排列结果不存在该项，才可选择
                resultList[resultIndex] = dataList[i];
                arrangementSelect(dataList, resultList, resultIndex + 1);
            }
        }
    }

这里的几个点：

• 每次递归都去所有的选择里拿，然后看目标数组里是不是已经存在了，不存在则放入。
• 每一次递归代往表目标数组放入一个数字。比如遍历A、B、C、D第一个递归放入A，第二个递归放入B，第三个递归放入C，第四个递归放入D，然后目标数组满了，然后第四个递归返回，返回到第三个递归，第三个递归上次放入的是C，这次放入D，然后又到第四个递归，第四个递归只剩下C可以放了，所以输出的顺序是ABCD，ABDC等等。

组合

    private static void combinationSelect(String[] dataList, int dataIndex, String[] resultList, int resultIndex) {
        int resultLen = resultList.length;
        int resultCount = resultIndex + 1;
        if (resultCount > resultLen) { // 全部选择完时，输出组合结果
            System.out.println(Arrays.asList(resultList));
            return;
        }

        // 递归选择下一个
        for (int i = dataIndex; i < dataList.length; i++) {
            resultList[resultIndex] = dataList[i];
            combinationSelect(dataList, i + 1, resultList, resultIndex + 1);
        }
    }

//useage
combinationSelect(new String[]{"A", "B", "C", "D"}, 0, new String[3], 0);

这里的不同点在于同一个位置选择过的数据不再选择。

参考文章：

• https://cgs1999.iteye.com/blog/2327664