编号的排序列表的迭代笛卡尔积(叉积),以条目的乘积递减顺序(包括桩的MVCE)

问题描述 投票:0回答:1

假设我有几个数字排序列表,例如:

double[] a1 = new double[]{0.70, 0.20, 0.10};
double[] a2 = new double[]{0.80, 0.10, 0.05, 0.05};
double[] a3 = new double[]{0.60, 0.15, 0.14, 0.10, 0.01};

我想按条目的递减乘积顺序迭代这些数组的笛卡尔积,就像这样:

0000: Combo[product=3.36e-01, vals=[0.70, 0.80, 0.60], indexes=[0, 0, 0]]
0001: Combo[product=9.60e-02, vals=[0.20, 0.80, 0.60], indexes=[1, 0, 0]]
0002: Combo[product=8.40e-02, vals=[0.70, 0.80, 0.15], indexes=[0, 0, 1]]
0003: Combo[product=7.84e-02, vals=[0.70, 0.80, 0.14], indexes=[0, 0, 2]]
0004: Combo[product=5.60e-02, vals=[0.70, 0.80, 0.10], indexes=[0, 0, 3]]
0005: Combo[product=4.80e-02, vals=[0.10, 0.80, 0.60], indexes=[2, 0, 0]]
...

例如在上面的示例中,第一个条目是显而易见的(对数组进行排序),它是第一个值的组合:[0.70, 0.80, 0.60]与乘积0.70*0.80*0.60 = 3.36e-01以及数组a1, a2, a3中的对应值索引为[0, 0, 0]。现在第二个条目不太明显了,我们应该将0.70更改为0.20吗?还是0.600.15?还是0.800.10?第二个应为[0.20, 0.80, 0.60],乘积为9.60e-02,索引为[1, 0, 0]

这里是Java中用于生成/打印它们的程序:https://repl.it/repls/FilthyGreatRotation(所有逻辑都在printWholeCartesianProduct()方法中)该程序按字典顺序生成它们,然后按产品对整个集合进行排序。

问题:首先是否有一种简单的方法可以以正确的顺序实际生成连击?

这样做的原因:首先,我没有列表,只是迭代了一些排序的数字集合。可能是veerery的长度,提前不知道长度,但是已知每个迭代器中的数字都已排序。

要玩的MVCE(与上面的https://repl.it链接中的相同:]

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringJoiner;
import java.util.function.Consumer;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        List<List<Double>> data = createData();
        printWholeCartesianProduct(data);
    }

    public static List<List<Double>> createData() {
        double[] a1 = new double[]{0.70, 0.20, 0.10};
        double[] a2 = new double[]{0.80, 0.10, 0.05, 0.05};
        double[] a3 = new double[]{0.60, 0.15, 0.14, 0.10, 0.01};
        return createData(a1, a2, a3);
    }

    public static void  printWholeCartesianProduct(List<List<Double>> data) {
        final DecimalFormat df = new DecimalFormat("0.00");

        // print input data
        String matrix = data.stream()
            .map(l -> l.stream().map(df::format).collect(Collectors.joining(", ")))
            .map(row -> "[" + row + "]")
            .collect(Collectors.joining("\n"));
        System.out.println("Input data:\n" + matrix);

        // collect combos as they are generated
        final List<Combo> combos = new ArrayList<>();
        Consumer<int[]> callback = indexes -> {
            double[] v = new double[indexes.length];
            double prod = 1;
            for (int i = 0; i < indexes.length; i++) {
                List<Double> col = data.get(i);
                int index = indexes[i];
                v[i] = col.get(index);
                prod *= v[i];
            }
            combos.add(new Combo(prod, v, indexes.clone()));
        };

        // generate combos
        int[] c = new int[data.size()];
        int ptr = c.length - 1;
        while (ptr >= 0) {
            callback.accept(c);
            c[ptr]++; // increment
            if (c[ptr] == data.get(ptr).size()) { // carry
                do {
                    ptr--;
                } while(ptr >= 0 && c[ptr] == data.get(ptr).size() - 1);
                if (ptr < 0) {
                    break;
                }
                c[ptr]++;
                // zero out
                while (++ptr <= c.length - 1) {
                    c[ptr] = 0;
                }
                ptr = c.length - 1;
            }
        }

        // cheating - sort after generation and print result
        combos.sort((o1, o2) -> Double.compare(o2.product, o1.product));
        StringBuilder sb = new StringBuilder();
        double totalP = 0;
        for (int i = 0; i < combos.size(); i++) {
            sb.append(String.format("%04d: ", i)).append(combos.get(i)).append("\n");
            totalP += combos.get(i).product;
        }
        System.out.printf("Cartesian product in descending product (total p=%.3e):\n%s", totalP, sb.toString());
    }

    public static List<Double> asList(double[] a) {
        return Arrays.stream(a).boxed().collect(Collectors.toList());
    }

    public static List<List<Double>> createData(double[]... arrays) {
        final List<List<Double>> vals = new ArrayList<>();
        Arrays.stream(arrays).forEachOrdered(a -> vals.add(asList(a)));
        return vals;
    }

    static class Combo {
        final double product;
        final double[] vals;
        final int[] indexes;

        Combo(double product, double[] vals, int[] indexes) {
            this.product = product;
            this.vals = vals;
            this.indexes = indexes;
        }

        @Override
        public String toString() {
            return new StringJoiner(", ", Combo.class.getSimpleName() + "[", "]")
                .add("product=" + String.format("%.2e", product))
                .add("vals=[" + Arrays.stream(vals).boxed().map(v -> String.format("%.2f", v)).collect(
                    Collectors.joining(", ")) + "]")
                .add("indexes=" + Arrays.toString(indexes))
                .toString();
        }
    }
}
java algorithm iteration cartesian-product
1个回答
© www.soinside.com 2019 - 2024. All rights reserved.