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 ★★★★★ ()
Ответ на: комментарий от 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 ()

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

arsi ★★★★★ ()
Ответ на: комментарий от 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 ★★★★★ ()

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

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

dimon555 ★★★★★ ()
Ответ на: комментарий от 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 ()

> 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

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

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

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

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

как вариант

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

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

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

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

> 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"  


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

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

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

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