本文提供了求夏普利值的代码,需要算法的地方只有分割子集。
import java.util.*;public class Shapley {/*** 得到包含这个元素的全部子集* @param set* @param target* @return*/public static Set<Set<String>> findSubsets(List<String> set, String target) {Set<Set<String>> subsets = new HashSet<>();findSubsets(set, target, 0, new HashSet<>(), subsets);return subsets;}private static void findSubsets(List<String> set, String target, int index, Set<String> currentSubset, Set<Set<String>> subsets) {if (index == set.size()) {if (currentSubset.contains(target)) {subsets.add(new HashSet<>(currentSubset));}return;}// Include the current elementcurrentSubset.add(set.get(index));findSubsets(set, target, index + 1, currentSubset, subsets);// Exclude the current elementcurrentSubset.remove(set.get(index));findSubsets(set, target, index + 1, currentSubset, subsets);}/**** @param map 集合和钱之间的映射* @param target 需要求夏普利值的函数* @param set 包含全部元素的集合* @return 夏普利值*/public static double getShapley(HashMap<Set<String>,Integer> map,String target,List<String> set){Set<Set<String>> subSetI = findSubsets(set,target);double sum = 0;for (Set<String> subSet:subSetI ) {double w = calW(new HashSet<>(set),subSet);double value1 = getValue(map,subSet);Set<String> removeSet = new HashSet<>(subSet);removeSet.remove(target);double value2 = getValue(map,removeSet);double add = w*(value1-value2);sum += add;}return sum;}public static void main(String[] args) {HashMap<Set<String>,Integer> map = new HashMap(){};map.put(new HashSet<>(Arrays.asList(new String[]{"老板"})),1);map.put(new HashSet<>(Arrays.asList(new String[]{"工程师"})),1);map.put(new HashSet<>(Arrays.asList(new String[]{"打工仔"})),0);map.put(new HashSet<>(Arrays.asList(new String[]{"老板","工程师"})),3);map.put(new HashSet<>(Arrays.asList(new String[]{"老板","打工仔"})),2);map.put(new HashSet<>(Arrays.asList(new String[]{"老板","工程师","打工仔"})),5);map.put(new HashSet<>(Arrays.asList(new String[]{"工程师","打工仔"})),2);String boss = "老板";String engineer = "工程师";String worker = "打工仔";String target = boss;List<String> set = new ArrayList<>(3);set.add(boss);set.add(engineer);set.add(worker);System.out.println("老板的夏普利值:"+getShapley(map,boss,set));System.out.println("工程师的夏普利值:"+getShapley(map,engineer,set));System.out.println("打工仔的夏普利值:"+getShapley(map,worker,set));}/**** @param map 集合和其赚到的钱的映射* @param s 需要求赚的钱的集合* @return 赚到的钱*/public static double getValue(HashMap<Set<String>,Integer> map,Set<String> s){if(s.size()==0)return 0;for (Set<String> iterSet:map.keySet()) {if(iterSet.equals(s)){return map.get(iterSet);}}throw new RuntimeException("this set does not contain the element");}/**** @param originSet 原始的集合,里面保管所有的元素* @param s 需要求权重的集合* @return 权重值*/public static double calW(Set<String> originSet,Set<String> s){int sSize = s.size();int oSize = originSet.size();return (double) factorial(sSize-1)*factorial(oSize-sSize)/factorial(oSize);}/*** 求阶乘* @param n* @return*/static int factorial(int n) {if (n == 0)return 1;elsereturn (n * factorial(n - 1));}
}