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

Последовательность натуральных чисел называется допустимой, если каждое целое число как минимум вдвое больше следующего. Так, например [7,2,1], допустимо, потому что $7 \geq 2*2$ и $2 \geq 2*1$ . С другой стороны, [3,2]не допустимо, потому что $3 < 2*2$ . (В топологии мы бы написали $\mathrm{Sq}^7 \mathrm{Sq}^2\mathrm{Sq}^1$ для последовательности [7,2,1]).

Степень последовательности является суммой её записей. Так, например, степень [7,2,1]составляет $7 + 2 + 1 = 10$ . Превышение допустимой последовательности является первым элементом минус сумма остальных элементов, так что [7,2,1]имеет избыток $7 - 2 - 1 = 4$ .

задача

Напишите программу, которая берет пару натуральных чисел (d,e)и выводит множество всех допустимых последовательностей степениd и превышения, меньшего или равного e. Выходными данными является набор, поэтому порядок допустимых последовательностей не имеет значения.

Примеры:

 Input: 3,1
 Output: [[2,1]]

Здесь мы ищем допустимые последовательности с общим количеством 3. Есть два варианта, [3]и [2,1]. ( [1,1,1]и [1,2]имеют сумму 3, но не допустимы). Превышение [3]составляет 3, а превышение [2,1]составляет $2-1 = 1$ . Таким образом, единственная последовательность с избытком $\leq1$ - это [2,1].

Input: 6, 6
Output: [[6], [5, 1], [4, 2]] (or any reordering, e.g., [[5,1],[4,2],[6]])

Поскольку избыток всегда меньше или равен степени, у нас нет условия превышения. Таким образом, мы просто пытаемся найти все допустимые последовательности степени 6. Параметры являются [6], [5, 1]и [4, 2]. (Они имеют избыток $6$ , $5-1 = 4$ и $4-2=2$ )

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

Допустимые последовательности степени 10:

[[10], [9,1], [8,2], [7,3], [7,2,1], [6,3,1]]

Они имеют избыток $10$ , $9-1 = 8$ , $8-2 = 6$ , $7-3 = 4$ , $7-2-1 = 4$ и $6-3-1=2$ соответственно, поэтому последние три все работают.

счет

Это код гольф: выигрывает самое короткое решение в байтах.

Тестовые случаи:

Любое изменение порядка вывода одинаково хорошо, поэтому для ввода (3, 3), вывода [[3],[2,1]]или [[2,1],[3]]одинаково приемлемо (однако [[1,2],[3]]это не так).

Input: 1, 1
Output: [[1]]

Input: 3, 3
Output: [[2,1], [3]]

Input: 3, 1
Output: [[2,1]]

Input: 6, 6
Output: [[6], [5, 1], [4, 2]]

Input: 6, 4
Output: [[5,1], [4,2]]

Input: 6, 1
Output: []

Input: 7, 7
Output: [[7], [6,1], [4,2,1], [5,2]]

Input: 7,1
Output: [[4,2,1]]

Input: 10, 10
Output: [[10], [9,1], [7,2,1], [6,3,1], [8,2], [7,3]]

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

Input: 26, 4
Output: [15, 7, 3, 1]

Input: 26, 6
Output: [[16, 7, 2, 1], [16, 6, 3, 1], [15, 7, 3, 1], [16, 8, 2], [16, 7, 3]]

05AB1E , 16 12 байт

Сохранено 4 байта благодаря Grimy

Åœíʒx¦@P}ʒÆ@

Попробуйте онлайн!

объяснение

Ŝ              # integer partitions
  í             # reverse each
   ʒ    }       # filter, keep only elements true under:
    x           # each element doubled
     ¦          # remove the first element in the doubled list
      @         # compare with greater than or equal with the non-doubled
       P        # product
         ʒ      # filter, keep only elements true under:
          Æ     # reduce by subtraction
           @    # compare with greater than or equal to second input

Wolfram Language (Mathematica) , 67 62 байта

Cases[IntegerPartitions@#,a_/;2a[[1]]-#<=#2>Max@Ratios@a<=.5]&

Попробуйте онлайн!

-4 байта @attinat

• IntegerPartitions@d : Получить все списки целых чисел в d
• Cases[,...]: Фильтровать по следующему условию:
  • 2#& @@# - d <= e &&: Дважды первый элемент минус сумма меньше e , и ...
  • Max@Ratios@#<=.5: Соотношения последовательных элементов списка меньше 1/2.

Поскольку eменьше чем .5, мы можем превратить это в цепное неравенство.

Для нескольких дополнительных байтов это значительно быстрее: попробуйте онлайн!

Желе ,  16  15 байт

-1 благодаря Эрику Outgolfer (умная настройка для проверки с использованием одного фильтра)

:Ɲ;_/>¥’Ạ
ŒṗUçƇ

Диадическая ссылка, принимающая положительное целое число dслева и положительное целое число eсправа, которое приводит к списку целых положительных чисел.

Попробуйте онлайн! (нижний колонтитул форматирует результаты, чтобы избежать неявного форматирования списка, который Jelly делает в виде полной программы)

Как?

:Ɲ;_/>¥’Ạ - Link 1: admissible and within excess limit? descending list, L; excess limit, e
 Ɲ        - neighbour-wise:
:         -   integer division  -- admissible if all these are >1
      ¥   - last two links as a dyad - i.e. f(L,e):
    /     -   reduce (L) by:
   _      -     subtraction
     >    -   greater than (e)? (vectorises)  -- within excess if all these are ==0
  ;       - concatenate
       ’  - decrement (vectorises)
        Ạ - all (non-zero)?

ŒṗUçƇ - Main link: integer, d; integer, e
Œṗ    - partitions (of d)
  U   - reverse each
    Ƈ - filter keep those (v in that) for which:
   ç  -   call last Link (1) as a dyad - i.e. f(v, e)

Хаскелл , 59 58 54 байта

1 байт сохранен благодаря nimi

4 байта сохранены благодаря xnor

0#_=[[]]
d#m=do i<-[1..div(m+d)2];(i:)<$>(d-i)#(2*i-d)

Попробуйте онлайн!

JavaScript (V8) ,  88 87  81 байт

Принимает вход как (e)(d). Печатает последовательности в STDOUT.

e=>g=(d,s=x=d,a=[])=>s>0?d&&g(d-1,s,a,g(d>>1,s-d,[...a,d])):a[s]*2-x<=e&&print(a)

Попробуйте онлайн!

комментарии

e =>                  // e = maximum excess
  g = (               // g is a recursive function taking:
    d,                //   d   = expected degree; actually used as the next candidate
                      //         term of the sequence in the code below
    s =               //   s   = current sum, initialized to d; we want it to be equal
                      //         to 0 when a sequence is complete
    x = d,            //   x   = copy of the expected degree
    a = []            //   a[] = current sequence
  ) =>                //
    s > 0 ?           // if s is positive:
      d &&            //   if d is not equal to 0:
        g(            //     outer recursive call:
          d - 1,      //       decrement d
          s,          //       leave s unchanged
          a,          //       leave a[] unchanged
          g(          //       inner recursive call:
            d >> 1,   //         update d to floor(d / 2)
            s - d,    //         subtract d from s
            [...a, d] //         append d to a[]
          )           //       end of inner recursive call
        )             //     end of outer recursive call
    :                 //   else:
      a[s] * 2 - x    //     s if either 0 (success) or negative (failure)
                      //     if s is negative, a[s] is undefined and this expression
                      //     evaluates to NaN, forcing the test to fail
      <= e            //     otherwise, we test whether the excess is valid
      && print(a)     //     and we print a[] if it is

Pyth , 23 байта

f!>-FTvzf!<#2/MCtBT_M./

Попробуйте онлайн!

f!>-FTvzf!<#2/MCtBT_M./Q   Implicit: Q=input 1, vz=input 2
                           Trailing Q inferred
                     ./Q   Generate partitions of Q (ordered lists of integers which sum to Q)
                   _M      Reverse each
        f                  Filter keep elements of the above, as T, where:
               CtBT          Pair the set with itself without the first element and transpose
                             This yields all adjacent pairs of values
             /M              Integer divide each pair
           #                 Filter keep elements...
          < 2                ... less than 2
                             For admissible sequences this will be empty
         !                   Logical NOT - maps [] to true, populated lists to false
                           Result of filter are all admissible sequences
f                          Filter keep the above, as T, where:
   -FT                       Reduce T by subtraction to get degree
 !>   vz                     Is the above not greater than vz?
                           Implicit print

Python 3 , 213 байт

Огромное понимание списка. Скорее всего, не самый лучший способ сделать это, но я не могу понять, как пропустить оператор if

import itertools as z
f=lambda d,e:[c for c in [[b for b in list(z.permutations(range(1,d+1),i)) if sum(b)==d and b[0]-sum(b[1:i])<=e and all([b[i]>=b[i+1]*2 for i in range(len(b)-1)])] for i in range(1,5)] if c]

Python 3 , 172 байта

from itertools import*
r=range
f=lambda d,e:filter(len,[[b for b in permutations(r(1,d+1),i)if d==sum(b)and~e<d-2*b[0]and all(i>=j*2for i,j in zip(b,b[1:]))]for i in r(5)])

Попробуйте онлайн!

Согласно редакции @Jonas Ausevicius

Древесный уголь , 42 байта

Ｆθ⊞υ⟦⊕ι⟧ＦυＦ…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ιＩΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Ｆθ⊞υ⟦⊕ι⟧

Сначала создайте список списков из [1]..[d].

ＦυＦ…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ι

Для каждого списка создайте новые списки, добавив перед ними все числа от удвоенного первого числа до dи добавьте эти списки в список списков для обработки. Это гарантирует, что все допустимые последовательности, содержащие числа не больше, чем dсозданы.

ＩΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Выведите только те списки, чья степень dи избыток не больше чем e. (Сумма степени и превышения равна двойному первому числу в списке.)

Python 3 , 156 байт

lambda d,e:[x for y in range(5)for x in permutations(range(1,d+1),y)if all(i>=j*2for i,j in zip(x,x[1:]))and d==sum(x)and~e<d-2*x[0]]
from itertools import*

принимает в d,eкачестве входных данных; выводит список кортежей

Подобно @OrangeCherries ответ и помощь от комментариев; но больше байтов сохранено

Попробуйте онлайн!

Желе , 18 байт

ŒṗU:Ɲ’ẠƊƇUṪ_SƊ’<ʋƇ

Попробуйте онлайн!

Рубин , 78 байт

g=->(d,e,m=1){d<m ?[]:g[d-m,e+m,m*2].map{|q|q+[m]}+g[d,e,m+1]|(d>e ?[]:[[d]])}

Попробуйте онлайн!