Brute force method / task assignment

Task assignment problem is a full permutation problem , First, complete the permutation , Then find the minimum cost task allocation method

package xcrj.kchalgorithm.bruteForce;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/** *  Task assignment problem  *  Yes n（n≥1） A task needs to be assigned to n Personal execution , One person performs a task  *  The first i The individual executes the j The cost of a task is c[i][j]（1≤i,j≤n）. Find the allocation scheme with the lowest total cost . * <p> * <p> *  Task assignment to people is a full permutation problem , People fixed , Task assignment has a relative order , So it's a full permutation problem  * <p> *  Incremental brute force method  * 1 * 12 | 21 * 123 312 132 | 321 231 213 * <p> *  recursive ： *  Recursive export ： The number to be added i> The maximum number n *  Recursive body ： Give the original arrangement each time   Index based j increase i  produce 1 New permutations  * <p> *  step ： * 1.  Full Permutation , Each task assignment method  * 2.  Traverse the full permutation result , Find the minimum cost task allocation method  */
public class DutyDistribution {
    
    //  Number of people = Number of tasks =4
    private static int n = 4;
    private static int[][] rdCosts = {
    {
    9, 2, 7, 8}, {
    6, 4, 3, 7}, {
    5, 8, 1, 8}, {
    7, 6, 9, 4}};
    //  Store in full line ,24 Is the total number of all permutations ,4!
    static Set<List<Integer>> fullPerm = new HashSet<>(24);

    static {
    
        List<Integer> list = new ArrayList<>(1);
        fullPerm.add(list);
    }

    public static void insertI(int i) {
    
        Set<List<Integer>> fullPermTemp = new HashSet<>(6);
        //  Put all permutations in the original permutation set into the temporary set 
        for (List<Integer> list : fullPerm) {
    
            // ！ Copy the permutations in the original permutation set , By index j increase i
            for (int j = 0; j < i; j++) {
    
                List<Integer> listTemp = new ArrayList<>(3);
                for (Integer v : list) {
    
                    listTemp.add(v);
                }
                listTemp.add(j, i);
                fullPermTemp.add(listTemp);
            }
        }
        //  Clear the original permutation set 
        fullPerm.clear();
        //  Copy all permutations of the temporary permutation set to the original permutation set 
        for (List<Integer> list : fullPermTemp) {
    
            List<Integer> l = new ArrayList<>(3);
            for (Integer v : list) {
    
                l.add(v);
            }
            fullPerm.add(l);
        }
        //  Clear temporary spread collection 
        fullPermTemp.clear();
    }

    public static void fullPermutation2(int i, int n) {
    
        if (i > n) System.out.println(" Full Permutation ：" + fullPerm);
        else {
    
            insertI(i);
            fullPermutation2(i + 1, n);
        }
    }

    /* Task assignment */
    public static void dutyDistribution() {
    
        fullPermutation2(1, 4);
        //  Minimum task allocation cost 
        int minCost = Integer.MAX_VALUE;
        //  Minimum cost task allocation 
        List<Integer> minCostDuties = null;
        //  Traverse each task assignment method , That is, traverse the full permutation ; The first i Task allocation method in ,List<Integer> The index represents , Value represents task 
        for (List<Integer> duties : fullPerm) {
    
            //  The total cost of a task assignment 
            int sumCost = 0;
            // j The number of the representative 
            for (int j = 0; j < duties.size(); j++) {
    
                // -1 reason , Because the task number of the full permutation is from 1 Start 
                sumCost += rdCosts[j][duties.get(j) - 1];
            }
            //  Compare costs 
            if (sumCost < minCost) {
    
                minCost = sumCost;
                minCostDuties = duties;
            }
        }
        //  Output the minimum cost task allocation method 
        System.out.println(minCostDuties);
        //  Output task assignment minimum cost 
        System.out.println(minCost);
    }

    public static void main(String[] args) {
    
        dutyDistribution();
    }
}