Сгенерировать декартово произведение списков в порядке убывания произведения записей (записи являются положительными числами, списки сортируются)

Question

Предположим, у меня есть несколько отсортированных списков положительных чисел, например, так:

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.60 до 0.15? Или 0.80 до 0.10? Второй должен быть [0.20, 0.80, 0.60] с продуктом 9.60e-02, индексами [1, 0, 0].

Вот программа на Java для их генерации / печати: https://repl.it/repls/FilthyGreatRotation (вся логика в методе printWholeCartesianProduct())
Эта программа генерирует их в лексикографическом порядке, а затем сортирует всеустанавливается по продукту.

Вопрос : Существует ли простой способ создать комбинации в правильном порядке?

Причина этого : IВо-первых, списки не имеют, только итераторы по некоторым отсортированным наборам чисел. Возможно, очень длинная, длина неизвестна заранее, но известно, что числа в каждом итераторе отсортированы.

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();
        }
    }
}

Answer 1

Я не знаком с Java, но поскольку в основном это всего лишь алгоритм, достаточно псевдокода:

Input:
Non-empty lists A, B, C: containing positive number(s).

Pseudo-code:
type-define tuple3 = (iterator, iterator, iterator);
function double value(tuple3 x) {
  return x.elm[0].value() * x.elm[1].value() * x.elm[2].value();
}
function boolean greater_than (tuple3 x, tuple3 y) {
  return (value(x) > value(y));
}
function void main() {
  iterator a = A.first();
  iterator b = B.first();
  iterator c = C.first();
  set<tuple3> Visit;
  PriorityQueue<tuple3, greater_than>  Q;
  Q.add((a,b,c));
  Visit.add((a,b,c));
  while (!Q.empty()) {
     tuple x = Q.pop_top();
     output(x);
     (a, b, c) = x;
     if (a.next() != null && !Visit.contains((a.next(), b, c))) {
         Q.add((a.next(), b, c));
         Visit.add((a.next(), b, c));
     }
     if (b.next() != null && !Visit.contains((a, b.next(), c))) {
         Q.add((a, b.next(), c));
         Visit.add((a, b.next(), c));
     }
     if (c.next() != null && !Visit.contains((a, b, c.next()))) {
         Q.add((a, b, c.next()));
         Visit.add((a, b, c.next()));
     }
  }
}

Обратите внимание, что функция output() выводит строку вывода. Я на самом деле не занимаюсь индексной печатью, но это должно быть довольно легко, верно? (Например, просто следите за индексами, увеличивая 3-tuple до 6-tuple, чтобы удерживать индексы дополнительными 3 элементами.) Должно быть легко распространить этот алгоритм на проблемы с числом списков больше 3.

ОБНОВЛЕНИЕ

Фактически, мы можем доказать, что в худшем случае O (N ^ 2) хранилище необходимо, если мы хотим оптимизировать скорость. Поскольку O (граница исследования) = O (N ^ 2), наше использование хранилища по крайней мере на некоторый постоянный фактор больше оптимального решения.

Не для того, чтобы предоставить официальное доказательство, но я хочу объяснить это в2D, то есть 2 списка умножения, а не 3. Тогда объяснение легко расширить.

Предположим, у нас есть список A, B с N положительными числами, отсортированными по убыванию. Эти результаты умножения NxN расположены в двумерном массиве. Например, когда N = 4, это выглядит так:

o > o > o > *
v   v   v   v
o > o > * > o
v   v   v   v
o > * > o > o
v   v   v   v
* > o > o > o

Каждый o или * представляет результат умножения. > означает «больше чем».

Верхний левый o представляет A[0] * B[0]. Каждый шаг вправо означает использование +1 индекса для A[], а каждый шаг вниз означает использование +1 индекса для B[]. Для того же столбца индекс A такой же. Для той же строки индекс B совпадает.

Рассмотрим *: мы знаем только, что A[] и B[] отсортированы по убыванию. Но мы не знаем, насколько «спускается» каждый шаг. Таким образом, эти * могут быть в любом порядке! Любой из тех 4! заказы. Если вы по крайней мере не сохраните их в какой-то предварительно упорядоченной структуре (куча, очередь с приоритетами и т. Д.), Нам придется читать и сравнивать ее снова и снова (т.е. сортировать эти 4 продукта), что побеждает скорость оптимизациидопущение.

Таким образом, мы уже объяснили, почему требуется хранилище N.

Теперь нам нужно доказать, что нашему алгоритму 2D-версии (то есть продукту из 2 списков) требуется не более 2N хранилища.

Я просто хочу дать подсказку. Полное доказательство будет слишком длинным. Например, если в середине нашего алгоритма приоритетная очередь хранит 4 *. Предполагая, что один из * посещен, и два из них вставляются в очередь следующим образом:

o > o > o > *
v   v   v   v
o > o > P > N
v   v   v   v
o > * > N > o
v   v   v   v
* > o > o > o

, где P означает предыдущий, то есть самое высокое значение, выбрасываемое из очереди,и N означает следующие два, сгенерированные +1 к каждому индексу, смежному с P. Понятно, что эти два N не могут быть выбраны в качестве наивысшего значения (поскольку один из * имеет большее произведение, чем каждый из них). Пока эти более высокие не появятся в очереди, эти N не смогут генерировать новые в очередь. Теперь, по крайней мере, два * направления "Прогресс" заблокированы! Это означает, что когда выбрано одно из двух значений (т. Е. Самое высокое значение для всплывающего окна), оно может создать только один новый продукт в очереди. Затем очередь поддерживается размером не более 2N.

Применяя это к 3D, мы знаем, что хранилище должно быть O (N ^ 2).

ОБНОВЛЕНИЕ хранилищеиспользование для "set" реализации

Кто-то может спросить, а как насчет "set"? Набор обычно реализуется в виде хеш-таблицы, пропорциональной количеству используемых записей. Наивной реализации может потребоваться хранить все продукты (т.е. O (N ^ 2) для 2D-версии и O (N ^ 3) для 3D-версии). Тщательная настройка для удаления записей, которые никогда не были нужны, уменьшит потребность в хранилище. Рассмотрим любой продукт в 2D-версии, может быть достигнуто только не более 2 других продуктов. то есть количество тестов Set.Contains () выполняется не более двух раз для каждого продукта. Если мы будем вести подсчет и удаляем эти неиспользуемые хеш-записи, они будут действительно очень близки к этим «нужным» записям к этим продуктам в нашей очереди. Это означает, что в 2D-версии в хэш-таблице также используется O (N) хранилище, а O (N ^ 2) для 3D-версии.