Generate combinations ordered by an attribute

Обновить

December 2018

Просмотры

1.6k раз

4

Я ищу способ создания комбинации объектов упорядоченных по одному атрибуту. Я не думаю, что лексикографический порядок то, что я ищу ... Я постараюсь дать пример. Скажем, у меня есть список объектов A, B, C, D со значениями атрибутов, которые я хочу заказать, будучи 3,3,2,1. Это дает объекты A3, B3, C2, D1. Теперь я хочу, чтобы генерировать комбинации 2-х объектов, но они должны быть упорядочены в нисходящем образом:

  • A3 B3
  • А3 С2
  • В3 С2
  • A3 D1
  • B3 D1
  • C2-D1

Генерация всех сочетаний и их сортировки не является приемлемым, поскольку в реальном мире сценарий предполагает большие наборы и миллионы комбинаций. (Набор 40, порядок 8), и мне нужно только комбинации выше определенного порога.

На самом деле мне нужно подсчитать комбинации выше порога, сгруппированных суммой данного атрибута, но я думаю, что это гораздо сложнее сделать - так что я бы согласиться на разработку всех комбинаций выше порогового значения и их подсчета. Если это вообще возможно.

EDIT - Мой первоначальный вопрос был не очень точным ... Я на самом деле не нужны эти комбинации упорядоченные, просто думал, что это поможет выделить комбинации выше порогового значения. Чтобы быть более точным, в приведенном выше примере, давая порог 5, я искал информацию о том, что данный набор производит 1 комбинацию с суммой 6 (A3 B3) и 2 с суммой 5 (A3 C2, В3 С2). Я на самом деле не нужны сами комбинации.

Я смотрел на проблему подмножества суммы, но если я правильно понял учитывая динамичное решение будет только дать вам информацию есть данная сумма или нет, не в счете сумм.

Спасибо

6 ответы

2

На самом деле, я думаю , что вы действительно хотите , лексикографический порядок, но по убыванию , а не по возрастанию. К тому же:

  • Это мне не ясно из вашего описания, что A, B, ... D играть какую-либо роль в своем ответе (за исключением, возможно, в качестве контейнера для значений).
  • Я думаю, ваш пример вопроса просто «Для каждого целого, по крайней мере 5, вплоть до максимально возможной суммы двух значений, сколько различных пары из множества {3, 3, 2, 1} есть суммы этого целого?»
  • Интересная часть раннего катапультирование, когда не возможно решение не может быть достигнуто (остальное достижимые суммы слишком малы).

Я отправлю пример кода позже.

Вот пример кода, я обещал, несколько замечаний следующие:

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

Предисловие замечания:

При этом используется небольшой вспомогательный класс под названием Tally, что только изолирует суммирование (в том числе инициализации для никогда ранее не видели ключей). Я положу его в конце.

Чтобы сохранить эту краткий, я взял некоторые ярлыки, которые не являются хорошей практикой для «реальной» коды:

  • Это не проверяет массив значений NULL, и т.д.
  • Я предполагаю, что массив значения уже отсортированы в порядке убывания, требуется для-антикризисной ранней техники. (Хороший производственный код будет включать в себя сортировку.)
  • Я положил переходные данные в переменный экземпляре вместо передачи их в качестве аргументов среди частных методов , которые поддерживают count. Это делает этот класс не-потокобезопасным.

Объяснение:

Экземпляр Combosсоздается с ( по убыванию) заказанного массива целых чисел для комбинирования. valueМассив устанавливается один раз в случай, но несколько вызовов countмогут быть сделаны с различными размерами населения и пределами.

countМетод вызывает ( в основном) стандартный рекурсивный обход уникальных комбинаций nцелых чисел от values. limitАргумент дает нижнюю границу сумм процентов.

countAtМетод рассматривает комбинацию целых чисел от values. leftАргумент , сколько целые остаются составляют nцелые числа в сумме, startявляется положение , в valuesкоторой требуется выполнить поиск, и sumявляется частичной суммой.

Раннее катапультирование механизма основано на вычислениях best, двумерный массив , который определяет «наилучшую» сумму достижимости из данного состояния. Значение best[n][p]является наибольшей суммой nзначений , начиная с позицией pоригинала values.

Рекурсия countAtднищ, когда правильное население было накоплено; это добавляет ток sum(от nзначений) к tally. Если countAtне достигли нижнего предела, она подметает valuesот start-ный положения , чтобы увеличить ток частичного sum, до тех пор , как:

  • достаточно позиций остаются в valuesдля достижения указанной популяции, и
  • best(наибольший) субтотальная оставаясь достаточно большой , чтобы сделать limit.

Образец выполнения с данными вашего вопроса в:

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

производит результаты вы указали:

found 2 sums of 5
found 1 sums of 6

Вот код Tally:

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}
0

Проверьте этот вопрос в StackOverflow: Алгоритм вернуть все комбинации S

Я также использовал только код Java-ниже, чтобы генерировать все перестановки, но он может быть легко использован для создания уникальной комбинации дала индекс.

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}
0

Вот рекурсивный подход к подсчитать количество этих подмножеств: Определим функцию , count(minIndex,numElements,minSum)которая возвращает число подмножеств размера numElements, сумма которых , по крайней мере minSum, содержащие элементы с индексами minIndexили больше.

Как и в постановке задачи, мы сортируем наши элементы в порядке убывания, например , [3,3,2,1], и вызовите первый нулевой индекс, а общее число элементов N. Мы предполагаем , что все элементы неотрицательны. Для того, чтобы найти все 2-подмножества, сумма которых составляет по меньшей мере 5, мы называем count(0,2,5).

Пример кода (Java):

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

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

0

Если вы используете C # есть довольно хорошая библиотека дженерики здесь . Заметим , однако , что генерация некоторых перестановок не в лексикографическом порядке

1

Я написал класс для обработки общих функций для работы с биномиальным коэффициентом, который является типом проблемы, что ваша проблема подпадает под. Он выполняет следующие задачи:

  1. Выходы всех K-индексы в хорошем формате для любого N выбирать K в файл. K-индексы могут быть замещены более описательных строк или букв. Этот метод позволяет решать такого рода проблемы весьма тривиальным.

  2. Преобразование K-индексы для правильного индекса записи в отсортированном биномиальноге таблицы коэффициентов. Этот метод гораздо быстрее, чем старые опубликованных методы, которые полагаются на итерации. Он делает это, используя математическое свойство, присущее треугольника Паскаля. Моя статья говорит об этом. Я считаю, что я первый, чтобы обнаружить и опубликовать эту технику, но я могу ошибаться.

  3. Преобразование индекса в отсортированном биномиальноге таблицы коэффициентов для соответствующих K-индексов.

  4. Использование Mark Dominus метод для вычисления биномиального коэффициента, который гораздо менее вероятно, переполнение и работает с большими числами.

  5. Класс написан на .NET C # и обеспечивает способ управления объектами, связанные с проблемой (если таковые имеются) с помощью общего списка. Конструктор этого класса принимает булево значение с именем InitTable, что, когда правда будет создать общий список для хранения объектов, которые будут управлять. Если это значение неверно, то это не будет создавать таблицу. Таблица не должна быть создана для того, чтобы выполнить 4 выше методов. Методы Accessor предоставляются для доступа к таблице.

  6. Существует связанный с ним тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован с 2-х случаях и нет никаких известных ошибок.

Чтобы прочитать этот класс и скачать код, см Tablizing биномиального Coeffieicent .

0

Я очень извиняюсь (после всех этих уточнений в комментариях), чтобы сказать, что я не мог найти эффективное решение этой проблемы. Я пытался в течение последнего часа без каких-либо результатов.

Причина (я думаю), что эта проблема очень похожа на такие проблемы, как задача коммивояжера. До тех пор, пока вы не попробуете все комбинации, нет никакого способа узнать, какие атрибуты добавят ДО порога.

Там, кажется, нет умного трюка, который может решить этот класс задач.

Тем не менее существует множество оптимизаций, которые вы можете сделать, чтобы фактический код.

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