package com.jiucaiyuan.net.question;



import java.util.ArrayList;

import java.util.Comparator;

import java.util.List;



/**

 * 【问题】打印一个字符串的全排列列（如果再加一个附加条件：要求不出现重复排列）

 * 【思路】第一个位置可以选择其中任意一个字符，第二个位置可以选择剩下的n-1个任何一个字符，第三个位置可以选择n-2个任何一个字符，依次类推

 *

 * @Author jiucaiyuan  2022/4/21 22:58

 * @mail services@jiucaiyuan.net

 */



public class PrintAllPermutations {

    /**

     * 字符串str的全排列，含有重复的

     *

     * @param str

     * @return

     */

    public static List<String> permutations(String str) {

        List<String> result = new ArrayList<>();

        if (str == null || str.length() == 0) {

            return result;

        }

        char[] chr = str.toCharArray();

        process(chr, 0, result);

        result.sort(new Comparator<String>() {

            @Override

            public int compare(String o1, String o2) {

                return o1.compareTo(o2);

            }

        });

        return result;

    }



    /**

     * 当前来到i这个位置，chs[i...]都可以尝试在i位置上，后续都可以去尝试，

     * chs[0-i-1]是之前的选择，把所有字符形成的全排列放到result中

     *

     * @param chs 之前的选择所形成的的结果

     * @param i   当前这个位置

     */

    private static void process(char[] chs, int i, List<String> result) {

        if (i == chs.length) {

            result.add(String.valueOf(chs));

            return;

        }

        for (int j = i; j < chs.length; j++) {

            swap(chs, i, j);

            process(chs, i + 1, result);

            swap(chs, i, j);

        }

    }





    /**

     * 字符串str的全排列，不重复全排列

     *

     * @param str

     * @return

     */

    public static List<String> permutationsNoDuplicate(String str) {

        List<String> result = new ArrayList<>();

        if (str == null || str.length() == 0) {

            return result;

        }

        char[] chr = str.toCharArray();

        processNoDuplicate(chr, 0, result);

        return result;

    }



    /**

     * 当前来到i这个位置，chs[i...]都可以尝试在i位置上，后续都可以去尝试，

     * chs[0-i-1]是之前的选择，把所有字符形成的全排列放到result中

     * 不重复全排列

     *

     * @param chs 之前的选择所形成的的结果

     * @param i   当前这个位置

     */

    private static void processNoDuplicate(char[] chs, int i, List<String> result) {

        if (i == chs.length) {

            result.add(String.valueOf(chs));

            return;

        }

        boolean[] visit = new boolean[26];

        for (int j = i; j < chs.length; j++) {

            if (!visit[chs[j] - 'a']) {

                visit[chs[j] - 'a'] = true;

                swap(chs, i, j);

                processNoDuplicate(chs, i + 1, result);

                swap(chs, i, j);

            }

        }

    }



    private static void swap(char[] chs, int i, int j) {

        char temp = chs[i];

        chs[i] = chs[j];

        chs[j] = temp;

    }





    private static void printList(List<String> res) {

        for (String str : res) {

            System.out.println(str);

        }

    }



    public static void main(String[] args) {

        String str = "acc";

        printList(permutations(str));

        System.out.println("-----------------");

        printList(permutationsNoDuplicate(str));

    }

}