(Заказано) Установить разделы в блоках фиксированного размера - PullRequest
Новая
       58

(Заказано) Установить разделы в блоках фиксированного размера

0 голосов
/ 01 января 2011

Вот функция, которую я хотел бы написать, но не могу это сделать. Даже если ты не / не могу дать решение, я был бы признателен за советы. Например, Я знаю, что есть корреляция между упорядоченными представлениями сумма целого и упорядоченного набора разделов, но это само по себе не помогает мне в найти решение. Итак, вот описание функции, которая мне нужна:


Задача

Создание эффективной * функции 

List<int[]> createOrderedPartitions(int n_1, int n_2,..., int n_k)

, который возвращает список массивов всех установленных частей набора {0,...,n_1+n_2+...+n_k-1} в number of arguments блоки размера (в этом заказ) n_1,n_2,...,n_k (например, n_1=2, n_2=1, n_3=1 -> ({0,1},{3},{2}),...).

Вот пример использования: 

int[] partition = createOrderedPartitions(2,1,1).get(0);
partition[0]; // -> 0
partition[1]; // -> 1
partition[2]; // -> 3
partition[3]; // -> 2

Обратите внимание, что количество элементов в списке (n_1+n_2+...+n_n choose n_1) * (n_2+n_3+...+n_n choose n_2) * ... * (n_k choose n_k). Кроме того, createOrderedPartitions(1,1,1) создаст перестановки {0,1,2} и, таким образом, будет 3! = 6 элементов в список.

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

Дополнительные требования

Если аргумент равен 0, обрабатывайте его так, как если бы его не было, например createOrderedPartitions(2,0,1,1) должен дать тот же результат, что и createOrderedPartitions(2,1,1). Но хотя бы один аргумент не должен быть 0. Конечно, все аргументы должны быть> = 0.

Примечания

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

На самом деле, еще лучше будет тип возврата List<Tuple<Set>> (например, когда создание такой функции в Python). Тем не менее, аргументы, которые имеют значение 0 не должно игнорироваться. createOrderedPartitions(2,0,2) тогда создать 

[({0,1},{},{2,3}),({0,2},{},{1,3}),({0,3},{},{1,2}),({1,2},{},{0,3}),...]


Фон

Мне нужна эта функция, чтобы сделать моего бота-мастера более эффективным и больше всего код более "красивый". Взгляните на filterCandidates функция в мой исходный код . Есть ненужные / дубликаты запросов, потому что я просто использую перестановки вместо специально заказанные перегородки. Кроме того, мне просто интересно, как писать эта функция.


Мои идеи (некрасивых) "решений"

Создайте блок питания из {0,...,n_1+...+n_k}, отфильтруйте подмножества размера n_1, n_2 и т. Д. И создайте декартово произведение n подмножеств. тем не мение на самом деле это не сработает, потому что будут дубликаты, например ({1,2},{1})...

Сначала выберите n_1 из x = {0,...,n_1+n_2+...+n_n-1} и поместите их в Первый сет. Затем выберите n_2 из x without the n_1 chosen elements beforehand и так далее. Затем вы получите, например, ({0,2},{},{1,3},{4}). из Конечно, каждая возможная комбинация должна быть создана так ({0,4},{},{1,3},{2}), тоже и тд. Кажется довольно сложным для реализации, но может быть возможным.


Исследования

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

http://rosettacode.org/wiki/Combinations

1 Ответ

1 голос
/ 02 января 2011

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

from itertools import combinations

def partitions(*args):
    def helper(s, *args):
        if not args: return [[]]
        res = []
        for c in combinations(s, args[0]):
            s0 = [x for x in s if x not in c]
            for r in helper(s0, *args[1:]):
                res.append([c] + r)
        return res
    s = range(sum(args))
    return helper(s, *args)

print partitions(2, 0, 2)

Вывод: 

[[(0, 1), (), (2, 3)], [(0, 2), (), (1, 3)], [(0, 3), (), (1, 2)], [(1, 2), (), (0, 3)], [(1, 3), (), (0, 2)], [(2, 3), (), (0, 1)]]

Это достаточно для перевода алгоритма в Lua / Java.Это в основном вторая идея, которая у меня была.


Алгоритм

Как я уже упоминал в конце вопроса, основная идея заключается в следующем:

Сначала выберите n_1 элементы набора s := {0,...,n_1+n_2+...+n_n-1} и поместите их в первый набор первого кортежа в результирующем списке (например, [({0,1,2},..., если выбранные элементы 0,1,2).Затем выберите n_2 элементы набора s_0 := s without the n_1 chosen elements beforehand и так далее.Одним из таких кортежей может быть ({0,2},{},{1,3},{4}).Конечно, каждая возможная комбинация создается, поэтому ({0,4},{},{1,3},{2}) является еще одним таким кортежем и т. Д.

Реализация

Сначала создается набор для работы (s = range(sum(args))).Затем этот набор и аргументы передаются рекурсивной вспомогательной функции helper.

helper выполняет одно из следующих действий: Если все аргументы обработаны, верните «какое-то пустое значение», чтобы остановить рекурсию.В противном случае переберите все комбинации переданного набора s длины args[0] (первый аргумент после s в helper).В каждой итерации создайте набор s0 := s without the elements in c (элементы в c являются выбранными элементами из s), который затем используется для рекурсивного вызова helper.

Так что же происходит сАргументы в helper заключаются в том, что они обрабатываются один за другим.helper может сначала начинаться с helper([0,1,2,3], 2, 1, 1), а в следующем вызове это, например, helper([2,3], 1, 1), а затем helper([3], 1) и, наконец, helper([]).Конечно, другой «путь дерева» будет helper([0,1,2,3], 2, 1, 1), helper([1,2], 1, 1), helper([2], 1), helper([]).Все эти «древовидные пути» созданы и, таким образом, генерируется необходимое решение.

...