Генерировать комбинации, упорядоченные по атрибуту

https://stackoverflow.com/questions/523800

22-08-2019
|

Вопрос

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

А3 Б3
А3 С2
Б3 С2
А3 Д1
Б3 Д1
С2 Д1

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

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

РЕДАКТИРОВАТЬ. Мой первоначальный вопрос был не очень точным...На самом деле мне не нужен упорядоченный порядок этих комбинаций, просто я подумал, что это поможет изолировать комбинации, превышающие пороговое значение.Точнее, в приведенном выше примере, задав порог 5, я ищу информацию о том, что данный набор дает 1 комбинацию с суммой 6 (A3 B3) и 2 с суммой 5 (A3 C2, Б3 С2).На самом деле мне не нужны сами комбинации.

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

Спасибо

Решение

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

Из вашего описания мне непонятно, что А, Б,...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, который просто изолирует табуляцию (включая инициализацию ранее не встречавшихся ключей).Я поставлю это в конец.

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

Это не проверяет массив нулевых значений и т.д.
Я предполагаю, что массив значений уже отсортирован в порядке убывания, что необходимо для метода досрочного спасения.(Хороший производственный код должен включать сортировку.)
Я помещаю временные данные в переменные экземпляра вместо того, чтобы передавать их в качестве аргументов частным методам, поддерживающим 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-ing позиция для увеличения текущего частичного 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();
    }
}

Другие советы

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

Выводит все K-индексы в удобном формате для любого N, выбирающего K в файл.K-индексы можно заменить более описательными строками или буквами.Этот метод делает решение такого типа задач довольно тривиальным.
Преобразует K-индексы в правильный индекс записи в таблице отсортированных биномиальных коэффициентов.Этот метод намного быстрее, чем старые опубликованные методы, основанные на итерациях.Это достигается за счет использования математического свойства, присущего треугольнику Паскаля.Моя газета говорит об этом.Я считаю, что я первый, кто открыл и опубликовал эту технику, но могу ошибаться.
Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы.
Использование Марк Доминус метод расчета биномиального коэффициента, который с гораздо меньшей вероятностью переполнится и работает с большими числами.
Класс написан на .NET C# и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), с помощью универсального списка.Конструктор этого класса принимает логическое значение InitTable, которое, если оно истинно, создает общий список для хранения управляемых объектов.Если это значение ложно, таблица не будет создана.Таблицу не обязательно создавать для выполнения 4 вышеуказанных методов.Для доступа к таблице предусмотрены методы доступа.
Существует связанный тестовый класс, который показывает, как использовать этот класс и его методы.Он был тщательно протестирован в двух случаях, и никаких известных ошибок не обнаружено.

Чтобы прочитать об этом классе и загрузить код, см. Таблизация биномиального коэффициента.

Проверьте этот вопрос в stackoverflow: Алгоритм возврата всей комбинациис

Я также просто использовал приведенный ниже 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;
}

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

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

Кажется, не существует хитрого трюка, который мог бы решить этот класс проблем.

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

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

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

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

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

Образец кода (Джава):

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 и постоянно получал результаты менее чем за секунду.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow