Hasilkan elemen dasar dari aljabar Steenrod

16

Aljabar Steenrod adalah aljabar penting yang muncul dalam topologi aljabar. Aljabar Steenrod dihasilkan oleh operator yang disebut "kotak Steenrod," yang ada untuk setiap bilangan bulat positif i. Ada dasar untuk aljabar Steenrod yang terdiri dari "monomial yang dapat diterima" dalam operasi kuadrat. Adalah tujuan kami untuk menghasilkan basis ini.

Urutan bilangan bulat positif disebut dapat diterima jika setiap bilangan bulat setidaknya dua kali lipat dari yang berikutnya. Jadi misalnya [7,2,1]dapat diterima karena 722 dan . Di sisi lain, tidak dapat diterima karena . (Dalam topologi kita akan menulis untuk urutannya ).221[3,2]3<22Sq7Sq2Sq1[7,2,1]

The gelar berurutan adalah total dari entri itu. Jadi misalnya, derajatnya [7,2,1]adalah . The kelebihan dari urutan diterima adalah elemen pertama dikurangi total dari unsur-unsur yang tersisa, sehingga memiliki kelebihan .7+2+1=10[7,2,1]7-2-1=4

Tugas

Tulislah sebuah program yang mengambil sepasang bilangan bulat positif (d,e)dan mengeluarkan serangkaian semua deret derajat yang dapat diterima ddan kelebihan kurang dari atau sama dengan e. Outputnya adalah himpunan sehingga urutan urutan yang diterima tidak masalah.

Contoh:

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

Di sini kami sedang mencari urutan diterima dengan total 3. Ada dua opsi, [3]dan [2,1]. ( [1,1,1]dan [1,2]memiliki jumlah 3 tetapi tidak dapat diterima). Kelebihannya [3]adalah 3 dan selisihnya [2,1]adalah . Dengan demikian, satu-satunya urutan dengan kelebihan adalah .2-1=11[2,1]

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

Karena kelebihan selalu kurang dari atau sama dengan derajat, kami tidak memiliki kondisi berlebih. Jadi, kami hanya mencoba untuk menemukan semua urutan diterima dari tingkat 6. Pilihannya adalah [6], [5, 1], dan [4, 2]. (Ini memiliki kelebihan , , dan 4 - 2 = 2. )65-1=44-2=2

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

Urutan derajat 10 yang dapat diterima adalah:

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

Ini memiliki kelebihan 10 , 9-1=8 , 8-2=6 , 7-3=4 , 7-2-1=4 , dan 6-3-1=2 masing-masing, jadi tiga yang terakhir semuanya bekerja.

Mencetak gol

Ini adalah kode golf: Solusi terpendek dalam byte yang menang.

Kasus uji:

Setiap pemesanan ulang output sama baiknya, jadi untuk input (3, 3), output [[3],[2,1]]atau [[2,1],[3]]sama-sama dapat diterima (namun [[1,2],[3]]tidak).

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]]
jilbab
sumber
1
Oke, saya akan berikan penjelasan singkat.
Hood

Jawaban:

6

05AB1E , 16 12 byte

Disimpan 4 byte berkat Grimy

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

Cobalah online!

Penjelasan

Ŝ              # 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
Emigna
sumber
ćsO-adalah built-in Æ.
Grimmy
Juga À@¨bisa ¦@.
Grimmy
1
@ Grimy: Oh wow, bagaimana saya melewatkan itu :) Terima kasih!
Emigna
5

Bahasa Wolfram (Mathematica) , 67 62 byte

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

Cobalah online!

-4 bytes oleh @attinat

  • IntegerPartitions@d : Dapatkan semua daftar penjumlahan bilangan bulat ke d
  • Cases[,...]: Saring dengan ketentuan berikut:
    • 2#& @@# - d <= e &&: Dua kali elemen pertama dikurangi jumlahnya kurang dari e, dan ...
    • Max@Ratios@#<=.5: Rasio elemen yang berurutan dari daftar semuanya kurang dari 1/2.

Karena ekurang dari 0,5, kita bisa mengubahnya menjadi ketimpangan yang dirantai.

Untuk beberapa byte tambahan, ini jauh lebih cepat: Coba online!

lirtosiast
sumber
1
63 bytes
attinat
5

Jelly ,  16  15 byte

-1 berkat Erik the Outgolfer (penyesuaian cerdas untuk pemeriksaan yang memungkinkan filter tunggal)

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

Sebuah tautan diad yang menerima bilangan bulat positif d,, di sebelah kiri dan bilangan bulat positif e,, di sebelah kanan yang menghasilkan daftar daftar bilangan bulat positif.

Cobalah online! (footer memformat hasil untuk menghindari daftar pemformatan daftar implisit yang dilakukan Jelly sebagai program lengkap)

Bagaimana?

:Ɲ;_/>¥’Ạ - 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)
Jonathan Allan
sumber
Anda dapat menyimpan byte dengan trik pintar . Mungkin perlu sedikit waktu untuk memahami mengapa itu berhasil. : P
Erik the Outgolfer
@EriktheOutgolfer luar biasa, saya telah mencoba beberapa cara serupa untuk menyejajarkan kedua filter (termasuk penggabungan), tetapi semuanya keluar sebagai 16 karena saya tidak berpikir untuk menggunakan trik pengurangan pada saat yang sama.
Jonathan Allan
4

Haskell , 59 58 54 byte

1 byte disimpan berkat nimi

4 byte disimpan berkat xnor

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

Cobalah online!

Posting Rock Garf Hunter
sumber
1
Anda dapat menyimpan beberapa byte dengan mendefinisikan #secara langsung: Coba online!
xnor
3

JavaScript (V8) ,  88 87  81 byte

Mengambil input sebagai (e)(d). Mencetak urutan ke 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)

Cobalah online!

Berkomentar

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
Arnauld
sumber
3

Pyth , 23 byte

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

Cobalah online!

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
Sok
sumber
3

Python 3 , 213 byte

Pemahaman daftar raksasa. Kemungkinan besar bukan cara terbaik untuk melakukan ini, tapi saya tidak tahu bagaimana cara melewatkan pernyataan 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 byte

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)])

Cobalah online!

Sesuai dengan hasil edit oleh @Jonas Ausevicius

OrangeCherries
sumber
2
Selamat datang di situs ini. Beberapa tips: Saya sepertinya Anda tidak terlalu terbiasa dengan di mana spasi diperlukan dalam python. Anda memiliki beberapa tempat yang bisa dihapus ruang dengan baik, jadi saya akan melihatnya. Juga berfungsi seperti alldapat mengambil generator sehingga Anda hanya dapat melakukan all(...)bukan all([...]). Terakhir karena kiriman Anda adalah fungsi yang sepenuhnya anonim, Anda tidak dikenakan sanksi atas penugasan ( f=) dan karenanya dapat menguranginya dari skor Anda (-2 byte).
Post Rock Garf Hunter
Oh dan juga di python3 Anda dapat melakukan cast to list dengan [*(...)]bukannya list(...)yang biasanya menghemat satu byte tetapi dalam case Anda menghemat 2 karena juga memungkinkan Anda untuk menghapus spasi.
Post Rock Garf Hunter
2
189 byte jika tidak masalah untuk mengembalikan objek filter, jika tidak 192 dengan [*filter(...)]. Juga selamat datang :)
Reinstate Monica
2
172 byte
Jonas Ausevicius
2

Arang , 42 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

Fθ⊞υ⟦⊕ι⟧

Pertama buat daftar daftar dari [1]..[d].

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

Untuk setiap daftar, buat daftar baru dengan mengawali semua angka dari angka pertama yang digandakan hingga d dan menambahkan daftar itu ke daftar daftar yang akan diproses. Ini memastikan bahwa semua urutan yang diizinkan yang berisi angka tidak lebih besar dari dyang dibuat.

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

Keluarkan hanya daftar yang derajat ddan kelebihannya tidak lebih besar dari e. (Jumlah derajat dan kelebihannya sama dengan dua kali angka pertama dari daftar.)

Neil
sumber
2

Python 3 , 156 byte

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*

mengambil d,esebagai input; daftar keluaran tupel

Mirip dengan @OrangeCherries, jawab dan bantuan dari komentar; tetapi lebih banyak byte yang disimpan

Cobalah online!

Jonas Ausevicius
sumber
1

Jelly , 18 byte

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

Cobalah online!

Nick Kennedy
sumber
1

Ruby , 78 byte

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]])}

Cobalah online!

MegaTom
sumber