all permutations of list of characters

Given a list of unique characters, generate or print out all permutations of characters.
For example:
input: [a, b, c]
output:
[a, b, c]
[b, a, c]
[c, b, a]
[a, c, b]
[b, c, a]
[c, a, b]

One of the permutation algorithm is done by swapping,
We have a list of permutations, which initially contains the input characters only.
Then we have two loops, outer loop (i) goes through index 0 to len-2, inner loop (j) goes from index i+1 to len-1, and for each current permutation, we generate one new by swap characters at i and j.


public static void permuIteratively(char[] chars){
        assert chars!=null && chars.length>0;
       
        List<char[]> result = new ArrayList<char[]>();
        result.add(chars);
        int len = chars.length;
       
        /*
         * the algorithm is doing swapping with two loops
         * i: 0..len-2
         *   j: i+1..len-1
         *    for each string in the result list
         *     swap characters at i and j
         *     add swapping result string to the result
         *    
         * since we can't change the list which iterating through list
         * so we have to make a temp copy of the result and add swapping result
         * into temp list   
         *
         */
       
        for(int i=0; i<len-1; i++){
            //make a copy of result
            List<char[]> temp = new ArrayList<char[]>(result);
            for(int j=i+1;j<len;j++){   
                //loop through result and swap i and j
                for(char[] item : result){
                    char[] copy = Arrays.copyOf(item, item.length);
                    char tempC = copy[i];
                    copy[i] = copy[j];
                    copy[j] = tempC;
                    temp.add(copy);
                }           
            }
            result = temp;
        }
       
        for(char[] i : result){
            System.out.println(Arrays.toString(i));
        }
    }


Once we find a way do it in iteratively, it is not difficutlt to switch to recursive way .

public static void permu(char[] chars){
        List<char[]> l = new ArrayList<char[]>();
        l.add(chars);
        permuRec(chars, 0, l);
    }
    public static void permuRec(char[] chars, int index, List<char[]> current){
        /*
         * termination condition
         */
        if(index==chars.length-1){
            for(char[] i : current){
                System.out.println(Arrays.toString(i));
            }
            return;
        }
       
        //make a copy of result
        List<char[]> temp = new ArrayList<char[]>(current);
        //then we grow the result by swapping
        for(int j=index+1;j<chars.length;j++){
            for(char[] item : current){
                char[] copy = Arrays.copyOf(item, item.length);
                char tempC = copy[index];
                copy[index] = copy[j];
                copy[j] = tempC;
                temp.add(copy);
            }
        }
        //continue on next index
        permuRec(chars, index+1, temp);
    }
   

Another way to do it is to by reduction. Basically we divide and conquer,  find the permutations for substring start at i+1 first, then insert the character at i into all positions for each permutation from the subpromblem.

/**
     * we solve this by reduction, for string s,
     * first find the permutation of its substring from i+1
     * then for each permutation, insert the character at i
     * into all positions
     *
     * @param chars
     */
    public static void permutationByDP(char[] chars){
        System.out.println(permutationByReduRec(chars, 0));
    }
   
    public static List<List<Character>> permutationByReduRec(char[] chars, int index){
        /*
         * permutations are represented by list of characters
         */
        List<List<Character>> result = new ArrayList<List<Character>>();
        if(index == chars.length-1){
            /**
             * base case is the string only has one character
             */
            List<Character> list = new ArrayList<Character>();
            list.add(chars[index]);           
            result.add(list);
        }
        else{
            /*
             * we build the permutation by its substring index+1 first
             */
            List<List<Character>> list = permutationByReduRec(chars, index+1);
            char insert = chars[index];
            for(List<Character> item : list){
                /*
                 * then we insert char at index to all possible positions in the item
                 */
                for(int i=0; i<=item.size(); i++){
                    List<Character> copy = new ArrayList<Character>(item);
                    copy.add(i, insert);
                    result.add(copy);
                }

            }
        }
        return result;       
    }