LINUX.ORG.RU
Форум — Development  

Set

 


0

3

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



Последнее исправление: cetjs2 (всего исправлений: 2)
← QWebView::createWindow
Посоветуйте литературу →

при дополнении одного из них другим получалось исходное

При объединении, ты хотел сказать?

Генеришь подмножество, вычитаешь из исходного, получаешь другое подмножество. Твоё сгенерённое с этим найденным при объединении дадут исходное. Какие проблемы?

yoghurt ★★★★★
()
Ответ на: комментарий от yoghurt

Да, не очень корректно объяснил! Суть в том, что из всех подмножеств мне нужно выбрать только те суммы элементов которых равны, и они вместе организуют исходное.

Ashley
() автор топика
Ответ на: комментарий от Ashley

Нахрена, если уже есть исходное, из которого можно вычесть любое подмножество и получить его «дополнение»?

anonymous
()

В общем, это, судя по всему, какая-то Real World проблема, попробуй лучше Scala.

anonymous
()
Ответ на: комментарий от Ashley

ну так нагенери все возможные подмножества X_0...X_N исходного множества Y, для каждого X_i вычисли Z_i = Y - X_i, из всех пар (X_i, Z_i) выбери те, у которых суммы элементов равны.

Решается в лоб.

На более умный и быстрый вариант меня сейчас уже не хватит.

yoghurt ★★★★★
()
Ответ на: комментарий от Ashley 
import Data.List ((\\), nubBy)

solve :: (Num a, Eq a) => [a] -> [([a], [a])]
solve s = nubBy similar $ filter sameSums $ pairs s $ subsets s
  where
    similar (a, b) (c, d) = (a == c && b == d) || (a == d && b == c)
    subsets [] = [[]]                 
    subsets (x:xs) = let ss = subsets xs in ss ++ map (x:) ss
    pairs i = let m x = (x, i \\ x) in map m
    sameSums (a, b) = sum a == sum b

Самое топорное, что я мог придумать.

> solve [2..13]
[([9,11,12,13],[2,3,4,5,6,7,8,10]),([7,8,9,10,11],[2,3,4,5,6,12,13]),([6,8,9,10,12],[2,3,4,5,7,11,13]),([6,7,9,11,12],[2,3,4,5,8,10,13]),([6,7,9,10,13],[2,3,4,5,8,11,12]),([6,7,8,11,13],[2,3,4,5,9,10,12]),([5,8,9,11,12],[2,3,4,6,7,10,13]),([5,8,9,10,13],[2,3,4,6,7,11,12]),([5,7,10,11,12],[2,3,4,6,8,9,13]),([5,7,9,11,13],[2,3,4,6,8,10,12]),([5,7,8,12,13],[2,3,4,6,9,10,11]),([5,6,10,11,13],[2,3,4,7,8,9,12]),([5,6,9,12,13],[2,3,4,7,8,10,11]),([5,6,7,8,9,10],[2,3,4,11,12,13]),([4,8,10,11,12],[2,3,5,6,7,9,13]),([4,8,9,11,13],[2,3,5,6,7,10,12]),([4,7,10,11,13],[2,3,5,6,8,9,12]),([4,7,9,12,13],[2,3,5,6,8,10,11]),([4,6,10,12,13],[2,3,5,7,8,9,11]),([4,6,7,8,9,11],[2,3,5,10,12,13]),([4,5,11,12,13],[2,3,6,7,8,9,10]),([4,5,7,8,10,11],[2,3,6,9,12,13]),([4,5,7,8,9,12],[2,3,6,10,11,13]),([4,5,6,9,10,11],[2,3,7,8,12,13]),([4,5,6,8,10,12],[2,3,7,9,11,13]),([4,5,6,8,9,13],[2,3,7,10,11,12]),([4,5,6,7,11,12],[2,3,8,9,10,13]),([4,5,6,7,10,13],[2,3,8,9,11,12]),([3,9,10,11,12],[2,4,5,6,7,8,13]),([3,8,10,11,13],[2,4,5,6,7,9,12]),([3,8,9,12,13],[2,4,5,6,7,10,11]),([3,7,10,12,13],[2,4,5,6,8,9,11]),([3,6,11,12,13],[2,4,5,7,8,9,10]),([3,6,7,8,10,11],[2,4,5,9,12,13]),([3,6,7,8,9,12],[2,4,5,10,11,13]),([3,5,7,9,10,11],[2,4,6,8,12,13]),([3,5,7,8,10,12],[2,4,6,9,11,13]),([3,5,7,8,9,13],[2,4,6,10,11,12]),([3,5,6,9,10,12],[2,4,7,8,11,13]),([3,5,6,8,11,12],[2,4,7,9,10,13]),([3,5,6,8,10,13],[2,4,7,9,11,12]),([3,5,6,7,11,13],[2,4,8,9,10,12]),([3,4,8,9,10,11],[2,5,6,7,12,13]),([3,4,7,9,10,12],[2,5,6,8,11,13]),([3,4,7,8,11,12],[2,5,6,9,10,13]),([3,4,7,8,10,13],[2,5,6,9,11,12]),([3,4,6,9,11,12],[2,5,7,8,10,13]),([3,4,6,9,10,13],[2,5,7,8,11,12]),([3,4,6,8,11,13],[2,5,7,9,10,12]),([3,4,6,7,12,13],[2,5,8,9,10,11]),([3,4,5,10,11,12],[2,6,7,8,9,13]),([3,4,5,9,11,13],[2,6,7,8,10,12]),([3,4,5,8,12,13],[2,6,7,9,10,11]),([3,4,5,6,8,9,10],[2,7,11,12,13]),([3,4,5,6,7,9,11],[2,8,10,12,13]),([3,4,5,6,7,8,12],[2,9,10,11,13])]

Вроде похоже на правду

yoghurt ★★★★★
()
Ответ на: комментарий от yoghurt

Более игрушечные примеры

> solve [1,1]
[([1],[1])]
> solve [2,2]
[([2],[2])]
> solve [3,3]
[([3],[3])]
> solve [1,1]
[([1],[1])]
> solve [1,1,2,2]
[([1,2],[1,2])]
> solve [1,1,2,2,3,3]
[([3,3],[1,1,2,2]),([1,2,3],[1,2,3])]
yoghurt ★★★★★
()
Ответ на: комментарий от Ashley

Ну вот, а говорил, что умеешь генерить возможные подмножества :)

yoghurt ★★★★★
()
Ответ на: комментарий от yoghurt

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

unC0Rr ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← QWebView::createWindow
Development
Посоветуйте литературу →