Страницы

Поиск по вопросам

воскресенье, 24 ноября 2019 г.

Код-гольф - Реализация алгоритма выборки комбинаций


Приём ответов завершён, всем спасибо за участие!
Можете оставлять свои решения, но победители уже выбраны и пересчёта не будет.



Приветствую.  

Задача: Напишите функцию, которая из произвольного входящего массива выберет вс
комбинации чисел, сумма которых будет равняться 10.  

Подробнее:
Диапазон чисел: 0 - 1000 включительно.
Количество чисел во входящем массиве: 1 - 10 включительно.
Уже выбранные числа могут использоваться неоднократно, но комбинации должны быт
уникальны.
--- Смена позиций не делает комбинацию уникальной, т. е. [1,9] и [9,1] не позволяются).
--- При входных данных [5,5,2,3] можно сделать [5,5], [5,2,3].
Продолжительность конкурса: 14 дней.
Обязательный формат метки ответа (для автоматического парсера в таблицу):

Язык, КоличествоСимволов

Определение победителя: Определяется по градации: Реализация, состоящая из наименьшего количества символов. Реализация, получившая больше всего плюсов (общий рейтинг минус голоса против). Реализация, время первой редакции которой раньше. Необходимо так же давать ссылку на один из онлайн-компиляторов с Вашим рабочим кодом. Тесты приветствуются. Настоятельно рекомендуется давать как конкурсную версию кода (минифицированную и/ил с колдунствами), так и наглядное описание этого же кода. Всем интересно не только увидеть языковую магию, но и что-то почерпнуть для себя. От одного участника допустимо несколько ответов, если они реализованы на разных языках. Но не более одного на язык Все вопросы по деталям и/или разногласиям и/или трактовке условий, прошу обсуждать в комментариях к этому сообщению или в комнате чата по код-гольфу. Итоги: Стандартные 3 места + 1 за самое большое количество плюсов (общий рейтинг минус голоса против). 1 место: @PavelMayorov - Haskell, 42 символа. 2 место: @ArtemKonovalov - Scala, 69 символов. 3 место: @Mike - Perl, 78 символов. Зрительские симпатии: @D-side (Ruby, 84) - 19 баллов. Поздравления всем участникам, вы хорошо сражались. Особенно страсти накалились в самом конце, когда неожиданно было опубликовано решение обгоняющее лидера на 1 символ. Но судьба вернула всё обратно. Хотелось бы отметить необычное для данного соревнования решение от пользователя @AlexanderGavrikov - 1437 символов! Это своеобразный рекорд, стоит отметить. Таблица лидеров: execute(581668); .cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23p 84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:cente 49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fol 11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1an 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50 0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3an 11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100 50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin: 50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0 rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}} .cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23p 84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:cente 49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fol 11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1an 11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50 0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3an 11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100 50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin: 50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0 rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}} /* TODO: Fix it */ body { font-size: 1rem; line-height: 1.5rem; font-family: 'Open Sans', sans-serif; background: #fff; padding: 0 2rem; } h1 { font-weight: 600; margin-bottom: 3rem; text-align: center; color: #212121; } #leadership { width: 100%; margin: 1rem auto; border-collapse: collapse; box-shadow: 0 2px 7px rgba(0,0,0,0.2); background: #fafafa; } #leadership td { padding: 1rem .5rem !important; text-align: left; font-weight: 500; transition: all .3s ease-in-out; } #leadership tr:hover td{ background: #03a9f4; color: #fefefe; } #leadership tr:hover td a { color: #fff; } #leadership th { padding: 1.5rem .5rem !important; color: #727272; text-align: left !important; font-weight: 500; border-bottom: 1px solid #dcdcdc; } #leadership a { text-decoration: none; color: #212121; } #leadership a:hover { color: #03a9f4; } #leadership td:nth-of-type(1){ text-align: center; color: #727272; font-size: .75rem; } #leadership td:nth-of-type(2){ } #leadership td:nth-of-type(2) img { width: 34px; border-radius: 50%; } /* #leadership th:nth-of-type(1), #leadership th:nth-of-type(2){ border-bottom: none; } */ #leadership th:nth-of-type(5), #leadership th:nth-of-type(6), #leadership th:nth-of-type(7), #leadership td:nth-of-type(5), #leadership td:nth-of-type(6), #leadership td:nth-of-type(7) { text-align: center !important; }
Удачи всем!


Ответы

Ответ 1



Haskell, 42 70 символа g=nub.filter((10==).sum).subsequences.sort Требует импорта функций nub, sort и subsequences из Data.List Запуск: main = print $ g [5,5,2,3] http://ideone.com/5jUIsy Как работает: входной список сортируется (иначе функция nub, см. далее, не поймет); функция subsequences находит все сочетания (без ограничения длины), их 2m, где - длина входного списка; при помощи filter выбираются те сочетания, которые дают нужную сумму; при помощи nub выбираются различные сочетания. PS спасибо участнику Artem Konovalov за то, что опосредованно подсказал мне не писать велосипед, а заглянуть в стандартную библиотеку языка :)

Ответ 2



Ruby, 84 91 ->a{(1..a.size).flat_map{|n|a.sort.combination(n).select{|c|c.reduce(:+)==10}.uniq}} Первое решение, которое таки умещается в одну строку при просмотре с сайта! Это литерал лямбды, который надо вызвать с массивом входных данных. Результатом будет массив из найденных комбинаций. Ideone В Ruby функция получения комбинаций элементов массива реализована прямо в класс Array, в стандартной библиотеке. Ой. В остальном, решение максимально прямое и неплохо переводится на естественный язык: (1..a.size) # Для диапазона от 1 до длины массива А .flat_map{ |n| # ...сконкатенировать для каждого N в нём следующее: a.sort # Из отсортированного массива А... .combination(n) # ...взять все комбинации длиной N элементов .select{ |c| # ...выбрав только те С из них, в которых: c.reduce(:+)==10} # Cвёртка С сложением равна 10. .uniq} # ...убрав повторения. Поскольку порядок в комбинациях неважен, чтобы не получить дубликатов, массив можн отсортировать. Можно отсортировать и комбинации постфактум, но это медленнее и требует больше символов.

Ответ 3



SQL SQLite Oracle 11.2, 104 114 124 147 176 обнаружен баг (см.комментарии) Реализация алгоритма выборки комбинации слагаемых для получения заданной суммы из заданного набора значений, с помощью рекурсивных SQL-запросов Решение на конкурс WITH t(p,w,s)AS(SELECT'',0,0 UNION SELECT p||i||';',r,i+s FROM t,a WHERE r>w)SELECT p FROM t WHERE s=10; Подготовка -- создаём таблицу с данными CREATE TABLE a (r INTEGER, i INTEGER); -- заполняем INSERT INTO a VALUES (1,5); INSERT INTO a VALUES (2,5); INSERT INTO a VALUES (3,2); INSERT INTO a VALUES (4,3); Читаемый вариант решения в конкурсном убраны алиасы. вместо t.r - w, a.r - r, a.i - i WITH t (p, r, s) AS (SELECT '', 0, 0 -- инициализация кортежа для рекурсии UNION SELECT p || a.i || ';' , -- сбор строки для вывода a.r, -- запоминаем номер строки, чтоб не взять дважды a.i+s -- накопительная сумма FROM t, a WHERE a.r > t.r -- ограничение - не использовать уже учтенные строки ) SELECT p -- вывод комбинаций FROM t WHERE s = 10; --наше конкурсное условие - сумма=10 Выдача P 5;5; 5;2;3; Тест (Home - читабельный код, Tab 2 - конкурсный)

Ответ 4



R, 111 s<-function(a)unique(Filter(function(x)sum(x)==10,unlist(Map(function(n)combn(a,n,sort,F),c(1:length(a))),F))) Код на IDE ONE Человекопонятный код: solve <- function(a) { # собираем вектор с допустимыми длинами комбинаций sizes <- c(1:length(a)) # сопоставляем каждой длине комбинации, получаем список списков комбинаций, каждая комбинация пропускается через sort combinations <- Map(function(size) combn(a, size, FUN = sort, simplify = FALSE), sizes) # делаем список с комбинациями плоским combinations <- unlist(combinations, recursive = FALSE) # оставляем только комбинации дающие в сумме 10 combinations <- Filter(function(x) sum(x) == 10, combinations) # выкидываем дубликаты combinations <- unique(combinations) #возвращаем результат combinations } Вызывется на интересующем векторе s(c(2,3,5,5))

Ответ 5



perl, 78    81 95 98 109 112 118 121 123 178 use List::Util 'sum'; # В размере не учитывается - библиотека "из коробки" sub X{for$c(sort@_){@r=map{$_,[@$_,$c]}@r,[]}grep{!$f{"@$_"}++&&10==sum@$_}@r} Тест на ideone.com Не сжатый вариант: sub X{ for $c(sort@_) { # Перебираем отсортированный входной массив @r=map {$_,[@$_,$c]} @r, # Для каждого элемента в массиве вариантов добавляем # такой же но с добавленным текущим числом [] # Затравка первого цикла - пустой массив } grep { # Выбираем те элементы массива !$f{"@$_"}++ && # Которые еще не встречались ранее 10==sum@$_ # И сумма элементов которых равна 10 } @r } Старый вариант с рекурсией (95 символов): sub X { # Основная функция my$n=pop; # $n=первый параметр (текущий остаток) @_=sort@_; # Сортируем входной массив my %r; # Объявляем хеш результатов map { # перебираем массив my$a=$n-(my$c=pop); # вытаскиваем очередной элемент массива (в $c) # и вычисляем текущий остаток минус данный элемент массива $r{"$c,$_"}++ for X(@_,$a) # Кладем в хеш результатов каждый элемент массива, # который вернет функция перед которым текущий элемент с запятой $r{$c}++ if!$a # Если разность 0 - то кладем в результаты само число } @_; keys%r # возвращаем массив результатов } # Вызов @A=(1,3,4,5,3,3,7,2,7,10); # Тестовый массив $,="\n"; print X(@A,10);

Ответ 6



JavaScript, 163 148 141 129 124 118 109 92 байткод для конкурса :) Совместное творчество с @Mike . f=(n,s,c,r=[],i=0)=>{for(s?0:c[r.join()]=r;i{ /*запуск рекурсии, которая обойдёт все комбинации чисел в массиве , комбинация на каждом шаге в аргументе r , (желаемая_сумма - сумма_комбинации) : в аргументе s*/ for( s?0:c[r.join()]=r;/*если сумма == 0 - записываем слагаемые в выходные данные*/ i{for(s?0:c[r.join()]=r;i

Ответ 7



PHP, 114   120 127 130 131 132 143 151 140 142 145 149 163 171 172 По количеству так-же, но выдает меньше предупреждений и работает быстрее. function($a,&$o){for(;2e3-$c++;$d&=$t=[])foreach($a as$k=>$e)1<<$k&$c?:($d+=$t[]=$e)-sort($t)-9?:$o[join($t)]=$t;} sandbox function($a, &$o){ for(; 2e3 - $c++; $d &= $t = []) // Перебор битовых масок массива 0..1023(2000) foreach($a as $k => $e) 1<<$k&$c // Попадает ли элемент в маску? ?: ($d += $t[] = $e) - sort($t) - 9 // sort() == 1, ($d += $t[] = $e) == $d ?: $o[ join($t) ] = $t; // join совместно с sort обеспечивают уникальность }

Ответ 8



Javascript ES6, 165 161 150 147 145 134 133 125 123 (неверно) 124 118 a=>[...Array(2e3)].map((x,q)=>a.filter((x,i)=>q&1<x+""!=a[i-1]&eval(x.join`+`)==10) Примечания: Длина массива ограничена 10 числами, поэтому можно использовать перебор по маске. Лямбда-функция не рекурсивная, поэтому её сохранение в переменную не учитываетс в числе символов. Подробнее на codegolf'е. Текущая версия функции не создаёт глобальных переменных Проверка: f=a=>[...Array(2e3)].map((x,q)=>a.filter((x,i)=>q&1<x+""!=a[i-1]&eval(x.join`+`)==10) console.log(f([5,5,2,3]).join(" ")) console.log(f([5,2,3]).join(" ")) console.log(f([0,10,10,5,0]).join(" ")) console.log(f([0,10,10,5,0,5]).join(" ")) console.log(f([9]).join(" "))

Ответ 9



Python3, 130         131 136 144 147 168 182 216 226 Минифицированный вариант: def r(a,c=[],z=[]): a.sort() for i,v in enumerate(a):z+=[c+[v]]if v+sum(c)==10*0**(c+[v]in z)else r(a[i+1:],c+[v],z)*0 return z Пример использования: res = r( [1,4,5,5,2,3,1,4] ) print( res ) Минифицированная версия исключительно для гольфа. Не минифицированная версия: def recur( arr, curArr, maxSumm ): arr.sort() curSumm = sum( curArr ) # текущая набранная сумма, не забываем, что sum([]) == 0 result = [] for i in range( len( arr ) ): if arr[i] + curSumm == maxSumm: # если в сумме набрали нужное число, то добавляем к результату result+=[ curArr + [ arr[i] ] ] elif arr[i] + curSumm < maxSumm: # если сумма меньше, то добавляем результат рекурсивного вызова result+= recur( arr[i+1:], curArr + [ arr[i] ], maxSumm ) return result def unique( arr ): # уникальные значения массива unique = [] [ unique.append(i) for i in arr if i not in unique ] return unique Живой пример: http://ideone.com/ggl9lO

Ответ 10



Scala, 69 73, 80 Нечитабельный вариант: def f(a:Seq[Int])=a.indices.flatMap(a.combinations).filter(_.sum==10) пример использования val a = List(1,2,3,4,5,6,7,8,9,10) println(f(a)) Читабельный вариант: def getSeq(list: List[Int]) = list //берем индексы т.е. получаем последовательность от 0 до size .indices //берем всевозможные комбинации длиной index из элементов списка .flatMap(index => list.combinations(index)) //фильтруем списки по сумме элементов == 10 .filter(s => s.sum == 10) Демка

Ответ 11



C++, 174 152 using m=multiset;setf(auto a){setr;for(int q=2e3,s;--q;){m c;s=10;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s-=x;if(!s)r.insert(c);}return r;} Примечания: В качестве аргумента следует передавать контейнер, в котором элементы лежат последовательно. http://ideone.com/4AAo0T http://ideone.com/o1nsmz #include #include #include using namespace std; //set>f(vectora){set>r;for(int q=2e3,s;--q;){multisetc;s=0;for(auto&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} //174 //using m=multiset;setf(vectora){setr;for(int q=2e3,s;--q;){m c;s=0;for(auto&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} //161 //using m=multiset;setf(auto a){setr;for(int q=2e3,s;--q;){m c;s=0;for(auto&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} // 155 //using m=multiset;setf(auto a){setr;for(int q=2e3,s;--q;){m c;s=0;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s+=x;if(s==10)r.insert(c);}return r;} // 154 //using m=multiset;setf(auto a){setr;for(int q=2e3,s,i;--q;){m c;s=i=0;for(int&x:a)if(q&1<;setf(auto a){setr;for(int q=2e3,s,i;--q;){m c;s=10,i=0;for(int&x:a)if(q&1<;setf(auto a){setr;for(int q=2e3,s;--q;){m c;s=10;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s-=x;if(!s)r.insert(c);}return r;} // 152 //using m=multiset;setf(auto a){setr;m c;for(int q=2e3,s;--q;!s?r.insert(c),0:0){c.clear();s=10;for(int&x:a)if(q&1<<&x-&a[0])c.insert(x),s-=x;}return r;} int main() { for (auto &r : f((vector){5,5,2,3})) { for (auto &x : r) cout << x << ' '; cout << '\n'; } return 0; }

Ответ 12



Java, 1437 Всем добрый день. Не уверен, есть ли однозначность в условии, но насколько я понимаю если входной массив {2, 3, 5, 5, 0}, то в результате должно быть 4 строки: {2, 3, 5} {0, 2, 3, 5}, {5, 5}, {0, 5, 5}. Так как массивы {2, 3, 5} и {0, 2, 3, 5} отличаются один {0}, но массивы разные и их сумма равна 10. В некоторых решениях выше при вводе данных {2, 3, 5, 5, 0} ответ будет только из двух массивов {2, 3, 5} и {5, 5}. Написано, Что во входном файле числа от 0 до 1000 включительно, значит нули могут быть. Написал свое решение на Java. Оно по сравнению с другими очень громоздкое, однак не хранит список массивов в памяти, чтобы удалять дубликаты, а выводит их "на лету", что называется. Плюс учитывает тот случай, который рассмотрел выше. Большой объем кода еще объясняется написание без использования каких-то стандартны коллекций. Идея в том, чтобы подсчитать количество единиц, двоек, троек и т. д. десяток во входном файле. Зная эту информацию, а также количество нулей, построить ответ. Рабочий код тут: http://ideone.com/mwV9Uh Листинг решения: import java.util.Scanner; public class Main { int c[] = new int[11]; void f(int n, int s, int[] cc) { for (int i = 1; i <= c[n]; ++i) { cc[n] += i; s += i * n; if (s == 10) { for (int z = 0; z <= c[0]; ++z) { for (int j = 0; j < z; ++j) { System.out.print("0 "); } for (int j = 1; j <= 10; ++j) { for (int k = 0; k < cc[j]; ++k) { System.out.print(j + " "); } } System.out.println(""); } } if (s >= 10) { cc[n] -= i; return; } for (int m = n + 1; m <= 10; ++m) { f(m, s, cc); } s -= i * n; cc[n] -= i; } } void g() { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int x = scanner.nextInt(); if (x >= 0 && x <= 10) { c[x]++; } if (x == -1) { break; } } int[] cc = new int[11]; for (int i = 1; i <= 10; ++i) { f(i, 0, cc); } } public static void main(String[] args) { Main x = new Main(); x.g(); } } Вот пример читаемого кода: import java.util.Scanner; public class Main { //количество каждого числа от 0 до 10 во входном файле int cnt[] = new int[11]; //вывод массива на экран private void printArray(int[] curCnt) { for (int i = 1; i <= 10; ++i) { for (int j = 0; j < curCnt[i]; ++j) { System.out.print(i + " "); } } System.out.println(); } //перебор для вывода вариантов private void brute(int number, int curSum, int[] curCnt, int tab) { for (int i = 1; i <= cnt[number]; ++i) { curCnt[number] += i; curSum += i * number; if (curSum == 10) { for (int cntZero = 0; cntZero <= cnt[0]; ++cntZero) { for (int i_ = 0; i_ < cntZero; ++i_) { System.out.print("0 "); } printArray(curCnt); } } if (curSum >= 10) { curCnt[number] -= i; return; } for (int newNumber = number + 1; newNumber <= 10; ++newNumber) { brute(newNumber, curSum, curCnt, tab + 1); } curSum -= i * number; curCnt[number] -= i; } } private void run() { //считывание данных из консоля Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int x = scanner.nextInt(); if (x >= 0 && x <= 10) { cnt[x]++; } if (x == -1) { break; } } int[] cntCur = new int[11]; for (int i = 1; i <= 10; ++i) { brute(i, 0, cntCur, 0); } } public static void main(String[] args) { Main solution = new Main(); solution.run(); } }

Ответ 13



D, 110 import std.stdio; import std.array; import std.range; import std.algorithm; alias f=e=>e.permutations.map!"a.length.iota.map!(b=>a[0..b+1].array.sort)".join.sort.filter!"a.sum==10".uniq; void main() { [5, 5, 2, 3].f.writeln; [5, 5, 2, 3, 2, 4, 7, 3].f.writeln; }

Ответ 14



Python3, 120 def f(a,o,i=0,p=[]):s=sum(p);exec(('o+=([p],[])[p in o];'*(s>9)+'f(a,o,i+1,sorted(p+[a[i]]));i+=1;'*(len(a)-i))*(s<11)) Примечание Результат записывается в параметр функции, т.е. вызываем функцию в виде f(input_list_of_numbers, output_list_of_combinations) Тест на Ideone Расшифровка кода def f(a, o, i=0, p=[]): s = sum(p); if s < 11: if s > 9: if p not in o: o += [p] while i < len(a): f(a, o, i + 1, sorted(p + [a[i]])) i += 1

Комментариев нет:

Отправить комментарий