[x(i) + x(i+1) : x(i) + x(i+1) + x(i+2) : x(i) + x(i+1) + x(i+2) + x(i+3) : ...]
i = 0..length

M>[x(i) + x(i+1) : x(i) + x(i+1) + x(i+2) : x(i) + x(i+1) + x(i+2) + x(i+3) : ...]
M>i = 0..length
M>

M>У меня есть как бы пару идей. Как сортировать и выводить я знаю А вот ввод и нахождение сумм — . Вернее, как минимум сегодня, нет времени над этим подумать А решить хочется сегодня

M>Не швырнете в меня кодом? Или кусками кода

[1,2,15,20]

yourFunc :: [Int]->[Int]
yourFunc x = x

main = getLine >>= putStrLn.show.yourFunc.read

plus_elts :: (Num elt)
    => [elt] -- суммы с прошлого раза
    -> [elt] -- данные из исходного массива
    -> [elt] -- новые суммы

plus_elts [_] [] = 0 -- ниже дадим гарантию, что списки отличаются на 1 элемент
plus_elts (x:xs) (y:ys) = (x+y):(plus_elts xs ys)

list2sums :: (Num elt)
    => [elt] -- исходный массив
    -> [[elt]] -- массив сумм, начиная с суммы пар

list2sums []  = [] -- два дефолтных случая, когда просто нечего делать
list2sums [_] = [] -- впрочем, этот случай является завершением рекурсии ниже
list2sums d = list2sums' d (tail d) -- складываем со сдвигом: [1,2,3,...] + [2,3,4,...]
  where
    -- вход: список сумм с прошлого раза (s) и хвост массива исходных данных (d)
    -- выход: список списков сумм n-ок, начиная со следующей
    -- предусловие: (length s) == (length d)+1
    -- постусловие: голова результата (передаваемая дальше) s', (length s')==(length d)==(length s)-1
    list2sums' s [] = [] -- нечего больше складывать (кстати, можно проверить, что s содержит ровно один элемент)
    list2sums' s d =
      let s' = (plus_elts s d) -- length s' == length d
      in s' : (list2sums' s' (tail d)) 
  -- первый раз мы вызвали list2sums' где s - входные данные, т.е. суммы групп по одному :)

src = x1 : x2 : x3 : ...

s1 = x1+x2 : x1+x2+x3 : x1+x2+x3+x4 : ...

s2 =            x2+x3 :    x2+x3+x4 : ...
   =         s11-x1   : s12-x1      : ... = (tail s1) `decrement_by` (head x)

s3 =                          x3+x4 : ...
   =                    s21-x2      : ... = (tail s2) `decrement_by` (head (tail x))

причём
s1 = x1+x2 : (s1_1+x3) : (s1_2+x4) : ...

integrator f x0 []      = []
integrator f x0 (x1:xs) = x0' : integrator x0' xs
  where x0'= x0 `f` x1
-- как-то можно выразить через foldr. как именно? лень думать, однако.

-- первая серия - это список частичных сумм
partialsums (x1:xs) = integrator (+) x1 xs

-- все серии
allsums []   = [] -- нет данных
allsums [x1] = [] -- недостаточно данных
allsums xs   = s1 : integrator s1 iter xs
  where
    s1 = partialsums xs
    -- и собственно операция скрещивания
    sk `iter` xk = (tail sk) `decrement_by` xk
    s `decrement_by` x = map (\si -> si-x) s

ssum n l = (sum l1): ssum (n+1) l2 
  where (l1,l2)= splitAt n l

f = fromInt.sort.(ssum 2).toInt.words -- или .lines, если по строкам

main = interact f

f = (map fromInt).sort.(map ((ssum 2).toInt).words

M>[x(i) + x(i+1) : x(i) + x(i+1) + x(i+2) : x(i) + x(i+1) + x(i+2) + x(i+3) : ...]
M>i = 0..length
M>

sumn [] _ = []
sumn xs n = sum head : sumn tail n
    where (head, tail) = splitAt n xs

main = let num = 15
           xs = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
       in mapM_ (print . sumn xs) [2..num]

plus_elts :: (Num elt)
    => [elt] -- суммы с прошлого раза
    ->> [elt] -- данные из исходного массива
    ->> [elt] -- новые суммы

plus_elts [_] [] = 0 -- ниже дадим гарантию, что списки отличаются на 1 элемент
plus_elts (x:xs) (y:ys) = (x+y):(plus_elts xs ys)

GHC
— Could not deduce (Num [elt]) from the context (Num elt) Main.hs ArraySort/src line 9 04 December 2005 10:18:06 13
— Probable fix: — add (Num [elt]) to the type signature(s) for `plus_elts' — or add an instance declaration for (Num [elt]) — In the definition of `plus_elts': plus_elts [_] [] = 0 Main.hs ArraySort/src line 9 04 December 2005 10:18:06 14

Hugs
ERROR "D:\Mamut\EclipseWorkspace\ArraySort\src\Main.hs":9 — Cannot justify constraints in explicitly typed binding
*** Expression : plus_elts
*** Type : Num a => [a] -> [a] -> [a]
*** Given context : Num a
*** Constraints : Num [a]

К>>Если хочешь освоить Хаскелл — то вперёд, а если нужно по-быстрому за оставшийся день — то С++ в руки

M>Ну что ж. Буду думать, благо алгоритм уже разжеван и разве что в рот не положен Тем более, что время есть

-- тип "комбинация"...
type Combination = [Int] -- это упорядоченный список индексов комбинации
                         -- в принципе, мог быть и массив - но его порождать тяжелее

-- генератор комбинаций
combinations :: Int -> Int -> Int -> [Combination]
combinations n0 n1 k -- перебор k чисел из диапазона [n0..n1]
  | k==0      = [ [] ]                                       -- вырожденный случай
  | k==1      = [ [x] | x <- [n0..n1] ]                      -- банальный случай
  | otherwise = [ (x:xs) | x <- [n0..n1-(k-1)],              -- первое число
                           xs <- combinations (x+1) n1 (k-1) -- и перебор всех остальных
                ]

-- сумма данной комбинации элементов массива
sum :: (Num a) => Array a -> Combination -> a
sum arr inds = foldr fn ids
  where
    {- по смыслу:
       index `fn` total = (arr!index) + total
    что равно
       fn i t = (+) ((!) arr i) t
       fn i   = (+) ((!) arr i)
              = (+)(((!) arr)i)
              = (+)$((!) arr)i
       fn     = (+)$((!) arr)
    -}
    fn = (+)$((!)arr)

-- генератор сумм (до посинения)
gensums :: (Num a) => Array a -> Int -> [a]
gensums arr k = [ sum' comb | comb <- combinations n0 n1 k ] -- внёс поправку: combinations, а не permutations'
  where
    sum' = sum arr -- говорят, биндинг дешевле пассинга
    (n0,n1) = bounds arr

-- список сумм
listsums :: (Num a) => Array a -> [[a]]
listsums arr = [ gensums' k | k <- [1..n] ]
  where
    gensums' = gensums arr
    (n0,n1) = bounds arr
    k = n1-n0+1

-- и вот теперь, над этим списком будем надругиваться...
mergesums :: (Num a) => [[a]] -> [a]
-- (фантазия временно иссякла)

-- финальная функция
allsums :: (Num a) => Array a -> [a]
allsums {-arr-} = mergesums.listsums {-arr-}

main = do
  lst <- read <<= getStrLn -- через запятую, в квадратных скобках
  let arr = arrayList (1,length lst) lst
  print (allsums arr) -- тоже через запятую и в квадратных скобках
  return ()

mergesums :: (Cmp a) => [[a]] -> [a]

mergesums {-lsums-} = foldr merge2 [] {-lsums-}
  where
    merge2 :: [a] -> [a] -> [a]
    xs `merge2` [] = xs
    [] `merge2` ys = ys
    (x:xs) `merge2` (y:ys) | x<y       = x : (   xs  `merge2` (y:ys))
                           | otherwise = y : ((x:xs) `merge2`    ys )

             +--- gensums(1)
output <--merge2    +--- gensums(2)
             +---merge2     +--- gensums(3)
                    +--- merge2
                            .........  +--- gensums(n)
                               +--- merge2
                                       +--- [] (стартовое значение, переданное в foldr)

К>main = do
К>  lst <- read <<= getStrLn -- через запятую, в квадратных скобках
К>  let arr = arrayList (1,length lst) (sort lst)
                                    -- ~~~~~    ~
К>  print (allsums arr) -- тоже через запятую и в квадратных скобках
К>  return ()

M>Как оказалось, условие я и сам неправильно понял. Оказалось, что надо не просто суммы смежных двоек, троек и т.д., а все гораздо хуже Необходимо суммы всех возможных групп чисел вообще. Т.е. а1 + а2, а1 + а3, а1 + а4, ...., а1 + а2 + а3, а1 + а3 + а4, ..., а2 + а3, ..., а2 + а4 + а5, ...

M>И потом получившиеся суммы поставить в порядке возрастания. На вопрос "а нафига это надо", друг не ответил, сказал, что надо А я уже обещался помочь

perm :: [Int] -> [Int]
perm zs = perm' zs (tails zs)
    where perm' [] _ = []
          perm' _ [] = []
          perm' (x:xs) (y:ys) = map ((+) x . sum) ys ++ perm' xs ys

R>perm :: [Int] -> [Int]
R>perm zs = perm' zs (tails zs)
R>    where perm' [] _ = []
R>          perm' _ [] = []
R>          perm' (x:xs) (y:ys) = map ((+) x . sum) ys ++ perm' xs ys

listsums :: (Num elt) => [elt]{-входные данные-} -> [elt{-сумма комбинации-}]{-для разных комбинаций-}

-- суммы комбинаций как минимум двух элементов
listsums [] = []
listsums [x] = []
listsums x1:x2:xs =  (listsums2 (x1+x2) xs) -- взяли два первых элемента, находим суммы комбинаций длиной >= 0
                  ++ (listsums1 x1 xs) -- взяли первый элемент, пропустили второй, суммы комбинаций длиной >= 1
                  ++ (listsums  x2:xs) -- пропустили первый элемент, находим суммы комбинаций длиной >= 2
  where
    -- суммы комбинаций как минимум одного элемента, плюс константа
    listsums1 :: elt{-прибавка к сумме-} -> [elt]{-хвост-} -> [elt]{-суммы комбинаций-}
    listsums1 x0 [] = []
    listsums1 x0 [x] = [x0+x]
    listsums1 x0 x1:xs = (listsums2 (x0+x1) xs) ++ (listsums1 x0 xs)
    -- суммы комбинаций в том числе нуля элементов, плюс константа
    listsums2 :: elt{-прибавка к сумме-} -> [elt]{-хвост-} -> [elt]{-суммы комбинаций-}
    listsums2 x0 [] = [x0]
    listsums2 x0 x:xs = (x0+sum(x:xs)) : (listsums2 x0 xs)
    -- listsumsN, N означает, сколько элементов уже учтено

M>Как оказалось, условие я и сам неправильно понял. Оказалось, что надо не просто суммы смежных двоек, троек и т.д., а все гораздо хуже Необходимо суммы всех возможных групп чисел вообще. Т.е. а1 + а2, а1 + а3, а1 + а4, ...., а1 + а2 + а3, а1 + а3 + а4, ..., а2 + а3, ..., а2 + а4 + а5, ...

M>И потом получившиеся суммы поставить в порядке возрастания. На вопрос "а нафига это надо", друг не ответил, сказал, что надо А я уже обещался помочь

allsums ([])= []
allsums ([a])= []
allsums ([a,b])= [a+b]
allsums (a:as)=  (allsums as)++(map (a+) as)++(map (a+) (allsums as))

main = interact (unwords.(map show).sort.allsums.(map read).words)

Т>allsums ([])= []
Т>allsums ([a])= []
Т>allsums ([a,b])= [a+b]
Т>allsums (a:as)=  (allsums as)++(map (a+) as)++(map (a+) (allsums as))

Т>main = interact (unwords.(map show).sort.allsums.(map read).words)
Т>

allsums (a:as) = subs ++ map (a+) (as ++ subs)
    where subs = allsums as

-- это чтобы с консоли можно было играться
answer {-xs-} = (sort.allsums) {-xs-}

A> length$answer [1..14]
(секунду подумал)
16369

A> answer [1..14]
(секунду подумал)
(следует дамп из 16 тысяч чисел)

A> answer [1..15]
ERROR - Garbage collection fails to reclaim sufficient space

merge [] ys = ys 
merge xs [] = xs
merge (x:xs) (y:ys) = if x<=y then x:(merge xs (y:ys)) else y: (merge(x:xs)  ys)

allsums ([])= []
allsums ([a])= []
allsums ([a,b])= [a+b]
allsums (a:as) = merge subs (map (a+) (merge as  subs))
    where subs = allsums as

sort:{x[<x]}
allsum:{:[(#x)<2;();(#x)=2;+/x; t, (*x)+(1_ x),t:_f[1_ x] ]}

  #allsum[!22]
4194281
  \t sort[allsum[!22]]
250 - время в ms

M>Я уже решил это все дело написать на С++ Потому что сделал вид, что умею думать и начертил вот такое:

M>Лучше уж я буду сохранять промежуточные результаты

unique :: (Eq elt) => [elt] -> [elt]

unique []              = []
unique x:[]            = x
unique x:x':xs | x==x' = unique x:xs -- выбрасываем дубликат
unique x:xs            = x : unique xs

mergeunique {-xs-} {-ys-} = unique.merge

Т>sort:{x[<x]}
Т>allsum:{:[(#x)<2;();(#x)=2;+/x; t, (*x)+(1_ x),t:_f[1_ x] ]}

Т>  #allsum[!22]
Т>4194281
Т>  \t sort[allsum[!22]]
Т>250 - время в ms
Т>

m=:1 7 4 5 2 0 6 6       NB. пример списка
x=:(2:+i.@-&2@#)+/\]     NB. магия
/:~@-.&0,x m
2 6 7 7 8 8 9 11 11 11 12 12 12 13 14 16 17 17 18 18 19 19 19 23 24 25 30

LCR>Что то слишком многословно

LCR>m=:1 7 4 5 2 0 6 6       NB. пример списка
LCR>x=:(2:+i.@-&2@#)+/\]     NB. магия
LCR>/:~@-.&0,x m
LCR>2 6 7 7 8 8 9 11 11 11 12 12 12 13 14 16 17 17 18 18 19 19 19 23 24 25 30
LCR>

  sort[allsum[1 7 4 5 2 0 6 6]]
1 2 3 3 4 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9
 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 
 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 
 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 
 15 15 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 
 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 
 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 
 21 21 21 21 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 24 24 24 24 24 24 
 24 24 24 24 25 25 25 25 25 25 25 25 26 26 26 26 27 27 28 28 29 29 30 30 31 31

Т>Зато правильно

Т>  sort[allsum[1 7 4 5 2 0 6 6]]
Т> <247 чиселок>
Т>

   d=:[:#:[:i.2:^#
   x=:#~>&1@(+/"1)
   f=:/:~@(+/"1@#~[:x d)
   #f 1 7 4 5 2 0 6 6
247
   f 1 7 4 5 2 0 6 6 
1 2 3 3 4 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 1...

M>Как оказалось, условие я и сам неправильно понял. Оказалось, что надо не просто суммы смежных двоек, троек и т.д., а все гораздо хуже Необходимо суммы всех возможных групп чисел вообще. Т.е. а1 + а2, а1 + а3, а1 + а4, ...., а1 + а2 + а3, а1 + а3 + а4, ..., а2 + а3, ..., а2 + а4 + а5, ...

M>И потом получившиеся суммы поставить в порядке возрастания. На вопрос "а нафига это надо", друг не ответил, сказал, что надо А я уже обещался помочь

let rec powerset lst = match lst with
      [] -> [ []]
    | h::t ->          
          let pstail = powerset t in
          let diff = List.map (fun x -> h::x) pstail in
              pstail @ diff

let sum_list lst = List.fold_left (+) 0 lst

let all_sums lst =
    let ps = powerset lst in
    let sums = List.map sum_list ps in
        List.sort compare sums

# powerset [1;2;3;5];;
- : int list list =
[[]; [5]; [3]; [3; 5]; [2]; [2; 5]; [2; 3]; [2; 3; 5]; [1]; [1; 5]; [1; 3];
 [1; 3; 5]; [1; 2]; [1; 2; 5]; [1; 2; 3]; [1; 2; 3; 5]
# all_sums [1;2;3;4];;
- : int list = [0; 1; 2; 3; 3; 4; 4; 5; 5; 6; 6; 7; 7; 8; 9; 10]
#

LCR>>2 6 7 7 8 8 9 11 11 11 12 12 12 13 14 16 17 17 18 18 19 19 19 23 24 25 30
LCR>>

   x=:(2:+i.@-&1@#)+/\]
   /:~@-.&0,x 1 7 4 5 2 0 6 6
2 6 7 7 8 8 9 11 11 11 12 12 12 13 14 16 17 17 18 18 19 19 19 23 24 25 30 31

ГА>let sum_list lst = List.fold_left (+) 0 lst

let sum_list = List.fold_left (+) 0

ГА>let rec powerset lst = match lst with
ГА>      [] -> [ []]
ГА>    | h::t ->          
ГА>          let pstail = powerset t in
ГА>          let diff = List.map (fun x -> h::x) pstail in
ГА>              pstail @ diff

ГА>let sum_list lst = List.fold_left (+) 0 lst

ГА>let all_sums lst =
ГА>    let ps = powerset lst in
ГА>    let sums = List.map sum_list ps in
ГА>        List.sort compare sums
ГА>

let rec size l = match l with
    | [] -> []
    | h::t -> 1 + size t;;

let rec seive l = match l with
    | [] -> []
    | h::t ->
        if (size h) > 1 then
            h::seive t
          else
              seive t;;

let all_sums lst =
    let ps = seive powerset lst in
    let sums = List.map sum_list ps in
        List.sort compare sums;;

LCR>2. где ты умудрился скачать К? Ссылкой не поделишься

  f:{b@<b:+/'x@&:'a@&1<+/'a:+2_vs!_2^#x}
  #f 1 7 4 5 2 0 6 6
247

ГА>(*  А разве нету готовой функции List.length? *)
ГА>

LCR>>let rec size l = match l with
LCR>>    | [] -> [] (*  А здесь [] с ноликом не перепутали? *)

ГА>(*  А зачем такое решето, если 
ГА>        1) пустой список в результатах по определению только один 
ГА>        2) сумма пустого списка равна нулю
ГА>        3) в условии задачи никто не говорил выбрасывать пустое множество
ГА>        4) и если все-таки его писать, то чем не подошел List.filter, зачем вручную?*)

LCR>>let rec seive l = match l with
LCR>>    | [] -> [] (* а здесь пару лишних [] не забыли? *)

ГА>з.ы. После пары месяцев активного пребывания на РСДНе я всегда компилирую и разок запускаю код, который сюда выкладываю

  #allsum[!22]
4194281