Подсчитать все возможные варианты сочетаний рядов

Question

Есть массив со строками, в котором может быть 60-100 элементов(15-20 элементов, с качеством от 1 до 5), нужно из них собрать уникальные ряды из 10 элементов. Порядок элементов в ряде не важен. То есть:

1,2,3,4,5,6,7,8,9,10 = 10,9,8,6,7,5,4,3,2,1 = 8,9,10,7,6,4,5,3,1,2 - Одни и те же ряды.

Каждому элементу массива [1,2,3...] соответствуют массивы с названием элемента [Яблоко, Апельсин, Арбуз...], качество [1-5,1-5,1-5...] его цена [20,40,10...] и то, что может получиться из данного элемента [яблочный сок - 20$|салат из яблок - 30$, апельсиновый фрэш -50$, арбузный лимонад - 10$, арбузный десерт - 30$]. От среднего качества ряда качества зависит стоимость выходящего элемента. К примеру если качество ряда 1, то цена выходящего элемента, к примеру, будет 50$, 2 -60$, 3 - 75$, 4 - 130$, 5 - 250$. То есть у каждого выходящего элемента есть 5 качеств и 5 цен соответственно.

В результате нужно получить Среднее арифметическое качества ряда, среднюю цену элементов, шанс получения каждого продукта, и среднюю цена выходящего продукта.

К примеру, если на выходе 5 разных вариантов, то шанс салат из яблок - 20%. И нужно в зависимости от шанса получить среднюю выходящую стоимость.

Если все 10 элементов в ряде - яблоки, то шанс на салат и на яблочный сок - 50/50. Если 9 яблок и 1 апельсин, то 90% - салат и сок(45% салат и 45% сок), а 10% - апельсиновый фрэш. Если 8 яблок, 1 апельсин и 1 арбуз, то 80% - сок или салат, 10% - фрэш, 10% - арбузный лимонад или дессерт. Из каждого продукта, получается от 1 до 5-7 разных блюд

К примеру шанс получить яблочный сок и салат = 16.66%, а апельсиновый фрэш 33.33%. Выходящая стоимость будет 0.166x20 + 0.166x30 + 0.33x50 ... = n.

И потом отсортировать по выгодности, в зависимости от того, сколько было затрачено на продукты, и сколько в среднем может получиться на выходе. Таким образом найти оптимальные сочетания продуктов

Как лучше это реализовать, чтобы программа не выполнялась вечность?

Answer 1

Решил вот таким образом, но при увеличении массива больше 13-14 элементов уже очень сильно возрастает время выполнения. Как уменьшить время выполнения пока не решил

   static void combination(int[] a, int n) {
    int size = a.length;
    int[] selected = new int[n];
    new Object() {

        void print() {
            for (int i = 0; i < n; ++i){
                System.out.print(a[selected[i]] + " ");
                // будущие операции
            }
            System.out.println();
        }

        void combination(int index, int prev) {
            if (index >= n)
                print();
            else
                for (int i = prev; i < size; ++i)
                    combination(index + 1, selected[index] = i);
        }

    }.combination(0, 0);

    private void jLabel15MouseClicked(java.awt.event.MouseEvent evt) { 
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        combination(a, 10);
    }

БЛОГ НА HUSL

Подсчитать все возможные варианты сочетаний рядов

Ответы (1 шт):