C++ (Qt)bool Linked( const Point & p0, const Point & p1 );
C++ (Qt)Linked(p0, p1) = true;Linked(p1, p2) = true;Linked(p0, p2) = false;
Haskellimport Data.List as DL -- cohesion принимает функцию группировки (Linked) и список элементов, возвращает список групп элементовcohesion :: (a -> a -> Bool) ->[a] -> [[a]]-- тривиальные случаиcohesion _ [] = []cohesion _ [x] = [[x]]cohesion test [x, y] | test x y == True = [[x, y]] | otherwise = [[x], [y]]-- общий алгоритм - выделяем очередную группу по первому элементу и остаток, над остатком проделываем то же самое. cohesion test (x:xs) = (x:as_x) : cohesion test not_as_x where (asx, other) = DL.partition (test x) xs (as_x, not_as_x) = collect asx other collect [] not_as_x' = ([], not_as_x') collect asx' [] = (asx', []) collect (y:ys) zs = (y:as_y, not_as_y) where (asy, ozs) = DL.partition (test y) zs (as_y, not_as_y) = collect (ys++asy) ozs -- Ну и протестируем на нескольких списках и функцияхmain :: IO ()main = do -- всегда False, групп столько же, сколько элементов putStrLn $ show $ cohesion (\_ _ -> False) [1..5] -- всегда True одна группа со всеми элементами putStrLn $ show $ cohesion (\_ _ -> True) [1..5] -- выделяем группу элементов <= 3 и группу > 7 putStrLn $ show $ cohesion (\a b -> (a <= 3 && b <= 3) || (a > 7 && b > 7)) [1..10]
$ ghc Cohesion.hs[1 of 1] Compiling Main ( Cohesion.hs, Cohesion.o )Linking Cohesion ...$ ./Cohesion[[1],[2],[3],[4],[5]][[1,2,3,4,5]][[1,2,3],[4],[5],[6],[7],[8,9,10]]
C++ (Qt)bool CanAdd( const Point & pt, const vector <CPoint> & c ){ for (size_t i = 0; i < c.size(); ++i) if (Linked(pt, c[i]) return true; return false;} ...vector <vector<CPoint> > data; // вектор новых контейнеров for (size_t i = 0; i < src.size(); ++i) { // scr - исходный контейнер size_t index; const Point & pt = src[i]; for (index = 0; i < data.size(); ++i) // ищем контейнер куда можно добавить if (CanAdd(pt, data[i])) break; if (index >= data.size()) { // не нашли, создаем новый контейнер data.push_back(vector <CPoint> ()); data.back().push_back(pt); } // нашли подходящий else { vector <CPoint> & dst = data[index]; dst.push_back(pt); // добавили в него // теперь все равно надо проверить оставшиеся size_t index2 = index + 1; while (index2 < data.size()) { vector <CPoint> & sec = data[index2]; if (!CanAdd(pt, sec)) ++index2; else { // сливаем dst.insert(dst.end(), src.begin(), sec.end()); data.erase(data.begin() + index2); } } }}
Haskell-- cohesion принимает функцию группировки принимающую 2 элемента и возвращающую Bool (Linked) и список элементов-- возвращает список групп элементовcohesion :: (a -> a -> Bool) ->[a] -> [[a]] -- Запись x:xs обозначает список из головы x и хвоста xs. Хвост может быть пустой -- Запись test x обозначает что мы зафиксировали первый параметр функции. Теперь при вызове ей нужен только второй параметр.-- Запись xs++ys для списков, обозначает конкатенацию списков - список ys добавляется в конец списка xs -- для входного списка с головой x и хвостом xs возвращаем список из cohesion test (x:xs) = (x:as_x) : cohesion test not_as_x where -- делим хвост списка на тех, кто "как x" (asx) и остальных (other), вызывая для каждого test с x-ом в первом параметре (asx, other) = DL.partition (test x) xs -- из остальных выбираем тех которые походят на какой-нибудь элемент из "как x" и остаток (as_x, not_as_x) = collect asx other -- тривиальные случаи collect [] not_as_x' = ([], not_as_x') -- список "как x" пустой - collect asx' [] = (asx', []) -- список остальных пустой collect (y:ys) zs = (y:as_y, not_as_y) where -- делим остальных на таких как голова тестируемого списка и не таких (ozs) (asy, ozs) = DL.partition (test y) zs -- для остатка списка и вновь прибывших проводим разделение (as_y, not_as_y) = collect (ys++asy) ozs
