LINUX.ORG.RU

Разбиение множества


1

0

Народ подскажите пожалуйста есть ли у кого готовая функция разбиения множества на подмножества. Те допустим {0,1,2,3} {0){1,2,3} {1}{0,2,3} {2}{0,1,3} {3}{0,1,2} {0,1}{2,3} ... И тд На вскидку кажется просто, но если реализовывать, то нифига не просто.


#!/usr/bin/guile -s 
!# 
 
(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
           (append rest (map (lambda(lst) (cons (car s) lst)) rest)))))

(display (subsets (list 1 2 3 4)))
(newline)
annoynimous ★★★★★
()
Ответ на: комментарий от annoynimous

а мне бы на с++ на функциональном оно конечно хорошо но мне бы на с++ или си как удобнее.

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

Ну и причем на входе должен быть массив допустим vector<int> mas; а на выходе допустим массив структур

struct mes {
vector<int> x1;
vector<int> x2;
}
vector <mes> result;

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

Какой ужас.
Этот append, похоже, делает сложность по времени сразу квадратичной, а то и более.
А по памяти вообще экспоненциальная сложность.
Вполне возможно, и переполнение стека кажется скоро случится.

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

P.S. Где искать - не знаю.

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

То есть тебе для больших множеств нужен этот алгоритм?
Но зачем? o_0 - там же количество результатов экспоненту места занимает

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

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

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

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

> значений из 10 не больше но и это уже приличный перебор получается.

ха :) 1024 варианта — не такой уж и большой перебор ;)

for (int m = 0; m < (1 << set.size()) - 1; ++m) {
    a.clear();
    b.clear();
    for (int i = 0; i < set.size(); ++i) {
        if (m & (1 << i))
            a.push(set[i]);
        else
            b.push(set[i]);
    }
    my_func(a, b);
}
arsi ★★★★★
()
Ответ на: комментарий от annoynimous

Хех, на Прологе такое записывается вообще в три строчки.

substr(X,Y,Z):-suffix(Y,X),head(Z,X).
subset([],_).
subset([X|Y],Z):-member(X,Z),substr(M,Z,X),tail(L,M),subset(Y,L).

Запрос к базе:

subset(X,[1,2,3,4]),write(X),nl,fail.

Хотя допускаю что можно и проще.

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

Хотя конечно решение на процедурном языке намного нагляднее и его вычислительную ёмкость намного легче оценить.

Думаю что в этом — основная причина непопулярности подобной эзотерики.

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

Хотя допускаю что можно и проще.

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

Думаю что в этом — основная причина непопулярности подобной эзотерики.

как вариант

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

Как и предполагалось, вынесло мозг ;)

мне в своё время тоже

jtootf ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.