Java中生成数值组合对应键集的笛卡尔积实现求助

我完全理解你的需求：当找到和为目标值的数值组合后，需要把每个数值对应的所有键进行笛卡尔积配对，比如2.45对应的键是[E-40, E-45]，2.65对应的是[E-56, E-34]，就要生成所有两两组合的结果。

下面是针对你的需求修改后的代码，主要优化点包括：

• 提前构建值到键列表的反向映射，避免重复创建哈希表
• 新增笛卡尔积计算逻辑，自动生成所有键组合
• 修复原代码中重复数值的处理逻辑，让结果更准确

修改后的完整代码 #

import java.util.*;

public class TestTheCombinations {
    // 定义数值到对应键列表的映射，建议从外部配置加载，这里为示例硬编码
    private static final Map<Double, List<String>> VALUE_TO_KEYS = new HashMap<>();
    static {
        VALUE_TO_KEYS.put(2.45, Arrays.asList("E-40", "E-45"));
        VALUE_TO_KEYS.put(2.65, Arrays.asList("E-56", "E-34"));
        VALUE_TO_KEYS.put(4.67, Arrays.asList("E-24"));
        VALUE_TO_KEYS.put(5.25, Arrays.asList("E-14"));
    }

    public static void main(String[] args) {
        ArrayList<Double> numbers = new ArrayList<>(Arrays.asList(2.45, 2.45, 2.65, 2.65, 4.67, 5.25));
        LinkedHashSet<Double> targets = new LinkedHashSet<>() {{ add(5.10); }};
        for (Double target : targets) {
            Combinations combinations = new Combinations(numbers, target, false, VALUE_TO_KEYS);
            combinations.calculateCombinations();
            for (String solution : combinations.getCombinations()) {
                System.out.println(solution);
            }
        }
    }

    public static class Combinations {
        private boolean allowRepetitions;
        private int[] repetitions;
        private ArrayList<Double> numbers;
        private Map<Double, List<String>> valueToKeys;
        private Double target;
        private Double sum;
        private boolean hasNext;
        private Set<String> combinations;

        /**
         * 带值键映射的构造方法
         */
        public Combinations(ArrayList<Double> numbers, Double target, boolean allowRepetitions, Map<Double, List<String>> valueToKeys) {
            this.allowRepetitions = allowRepetitions;
            // 根据是否允许重复处理数值列表
            if (this.allowRepetitions) {
                Set<Double> numbersSet = new HashSet<>(numbers);
                this.numbers = new ArrayList<>(numbersSet);
            } else {
                this.numbers = new ArrayList<>(numbers);
            }
            this.numbers.removeAll(Collections.singleton(0.0));
            Collections.sort(this.numbers);
            this.target = target;
            this.repetitions = new int[this.numbers.size()];
            this.combinations = new LinkedHashSet<>();
            this.sum = 0.0;
            this.valueToKeys = valueToKeys;
            this.hasNext = this.repetitions.length > 0;
        }

        private Double calculateSum() {
            this.sum = 0.0;
            for (int i = 0; i < repetitions.length; ++i) {
                this.sum += repetitions[i] * numbers.get(i);
            }
            return this.sum;
        }

        private void redistribute() {
            for (int i = 1; i < this.repetitions.length; ++i) {
                if (this.repetitions[i - 1] > 1) {
                    this.repetitions[i - 1] = 0;
                    this.repetitions[i] += 1;
                }
            }
            if (this.repetitions[this.repetitions.length - 1] > 1) {
                this.repetitions[this.repetitions.length - 1] = 0;
            }
        }

        private Double next() {
            if (this.hasNext && this.repetitions.length > 0) {
                this.repetitions[0] += 1;
                if (!this.allowRepetitions) {
                    this.redistribute();
                }
                this.calculateSum();
                for (int i = 0; i < this.repetitions.length && this.sum != 0; ++i) {
                    if (this.sum > this.target) {
                        this.repetitions[i] = 0;
                        if (i + 1 < this.repetitions.length) {
                            this.repetitions[i + 1] += 1;
                            if (!this.allowRepetitions) {
                                this.redistribute();
                            }
                        }
                        this.calculateSum();
                    }
                }
                if (this.sum.compareTo(0.0) == 0) {
                    this.hasNext = false;
                }
            }
            return this.sum;
        }

        public void calculateCombinations() {
            while (this.hasNext) {
                Double currentSum = this.next();
                if (currentSum.compareTo(target) == 0) {
                    // 收集当前组合中每个数值对应的键列表
                    List<List<String>> keyGroups = new ArrayList<>();
                    for (int i = 0; i < repetitions.length; ++i) {
                        Double num = numbers.get(i);
                        int count = repetitions[i];
                        // 按重复次数添加对应键列表
                        for (int j = 0; j < count; j++) {
                            keyGroups.add(valueToKeys.get(num));
                        }
                    }
                    // 计算笛卡尔积，生成所有键组合
                    List<List<String>> cartesianProduct = getCartesianProduct(keyGroups);
                    for (List<String> combo : cartesianProduct) {
                        combinations.add(String.join("-", combo));
                    }
                }
            }
        }

        /**
         * 递归计算多个列表的笛卡尔积
         */
        private List<List<String>> getCartesianProduct(List<List<String>> lists) {
            List<List<String>> result = new ArrayList<>();
            if (lists.isEmpty()) {
                result.add(new ArrayList<>());
                return result;
            }
            List<String> firstList = lists.get(0);
            List<List<String>> remainingProduct = getCartesianProduct(lists.subList(1, lists.size()));
            for (String item : firstList) {
                for (List<String> remaining : remainingProduct) {
                    List<String> newCombo = new ArrayList<>();
                    newCombo.add(item);
                    newCombo.addAll(remaining);
                    result.add(newCombo);
                }
            }
            return result;
        }

        public Set<String> getCombinations() {
            return this.combinations;
        }
    }
}

关键修改说明 #

1. 反向映射VALUE_TO_KEYS：
   • 把原代码中硬编码在toString里的哈希表改成全局映射，既提高复用性，也方便后续从外部配置加载数据。
2. 笛卡尔积生成逻辑：
   • 新增getCartesianProduct方法，递归计算多个键列表的笛卡尔积，这是生成所有键组合的核心，支持任意数量数值的组合场景。
3. 组合生成逻辑优化：
   • 在calculateCombinations中，找到符合条件的数值组合后，先收集每个数值对应的键列表，再通过笛卡尔积生成所有可能的键配对，最终转换成键1-键2的字符串格式存入结果集合。

运行结果 #

执行代码后会输出你需要的所有键组合：

E-40-E-56
E-40-E-34
E-45-E-56
E-45-E-34

这段代码也支持扩展到更多数值相加的场景（比如三个数之和的情况），会自动生成对应的多键组合，不需要额外修改核心逻辑。

内容的提问来源于stack exchange，提问作者arctu