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

Выводит все подмножества данного множества, включая пустое. Возможно, поможет.

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

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

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

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

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

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

Вот и я про то же самое. Если было бы просто не спросил бы у ЛОРа!

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

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

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

нужно получить все возможные варианты разбития одного множества на два подмножества, так? тогда берём битовую строку длиной равной длине начального множества и проходом от 0000…0 до 1111…1 помещаем i-e значение из начального множества или в первое подмножество, или во второе, в зависимости от значения i-го бита битовой строки. как-то так ;)

> значений из 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);
}

http://www.mathsisfun.com/sets/power-set.html

http://rosettacode.org/wiki/Power_Set#C.2B.2B

На вскидку кажется просто, но если реализовывать, то нифига не просто.

а если перед тем, как реализовывать,- подумать? :)

липский комбинаторика для программистов

кодировать с помощью битов это самое верное, на мой взгляд

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

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.

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

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

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

> v<-c("a","b","c") 
> vv<-c(outer(v,v,paste)) 
> vv [1] "a a" "b a" "c a" "a b" "b b" "c b" "a c" "b c" "c c" 
> vvv<-c(outer(vv,v,paste)) 
> vvv 
[1] "a a a" "b a a" "c a a" "a b a" "b b a" "c b a" "a c a" "b c a" "c c a" 
[10] "a a b" "b a b" "c a b" "a b b" "b b b" "c b b" "a c b" "b c b" "c c b" 
[19] "a a c" "b a c" "c a c" "a b c" "b b c" "c b c" "a c c" "b c c" "c c c"

The outer product of the arrays ‘X’ and ‘Y’ is the array ‘A’ with dimension ‘c(dim(X), dim(Y))’ where element ‘A[c(arrayindex.x, arrayindex.y)] = FUN(X[arrayindex.x], Y[arrayindex.y], ...)’.

outer(X, Y, FUN=«*», ...) X %o% Y

paste Concatenate vectors after converting to character

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

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

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

как вариант

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

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

Оказывается, этот пример стал классикой.

http://www.reddit.com/r/programming/comments/225f0/beautiful_haskell_implemen...

http://community.livejournal.com/evan_tech/220036.html

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

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

> combn(letters[1:7], 5)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,] "a"  "a"  "a"  "a"  "a"  "a"  "a"  "a"  "a"  "a"   "a"   "a"   "a"   "a"  
[2,] "b"  "b"  "b"  "b"  "b"  "b"  "b"  "b"  "b"  "b"   "c"   "c"   "c"   "c"  
[3,] "c"  "c"  "c"  "c"  "c"  "c"  "d"  "d"  "d"  "e"   "d"   "d"   "d"   "e"  
[4,] "d"  "d"  "d"  "e"  "e"  "f"  "e"  "e"  "f"  "f"   "e"   "e"   "f"   "f"  
[5,] "e"  "f"  "g"  "f"  "g"  "g"  "f"  "g"  "g"  "g"   "f"   "g"   "g"   "g"  
     [,15] [,16] [,17] [,18] [,19] [,20] [,21]
[1,] "a"   "b"   "b"   "b"   "b"   "b"   "c"  
[2,] "d"   "c"   "c"   "c"   "c"   "d"   "d"  
[3,] "e"   "d"   "d"   "d"   "e"   "e"   "e"  
[4,] "f"   "e"   "e"   "f"   "f"   "f"   "f"  
[5,] "g"   "f"   "g"   "g"   "g"   "g"   "g"  
> xxx <-rev(combn(letters[1:7], 2))
> dim(xxx)<-dim(combn(letters[1:7], 2))
> xxx
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,] "g"  "g"  "f"  "g"  "f"  "e"  "g"  "f"  "e"  "d"   "g"   "f"   "e"   "d"  
[2,] "f"  "e"  "e"  "d"  "d"  "d"  "c"  "c"  "c"  "c"   "b"   "b"   "b"   "b"  
     [,15] [,16] [,17] [,18] [,19] [,20] [,21]
[1,] "c"   "g"   "f"   "e"   "d"   "c"   "b"  
[2,] "b"   "a"   "a"   "a"   "a"   "a"   "a"  

незаметил что надо две подгруппы делать :(

Жуткий overhead же!

Тут сложность небось кубическая по N.

Хотя нет. Вопрос сложности снят.

Неясно другое - что за WTF is that и зачем это здесь?

Тут в общем на счет ВТФ такая штука. Задачка мне поставленная решается только перебором. Но есть возможность сократить количество переборов. Собственно Это только маленькая подзадача большой задачи. Задача касается троичных последовательностей. Спасибо за ответы тема пока не закрыта. Я еще посмотрю и поюзаю ваши предложения. Выложу готовое и закрою.