New answers tagged combinatorics
6
Python 2 with numpy, 330 bytes
import numpy as N,itertools as I
L=list
D=N.dot
n=input()
def G((a,b,c)):
A=a
while 1:
u=b-a;v=c-b;d=D(v,v)
if D(u,u)-d:return 0
p=2*D(u,v)*v
a,b,c=b,c,c+a-b+p/d
if(p%d).any()or((c<0)|(c>n)).any()or L(a)<L(A):return 0
if L(a)==L(A):return 1
print sum(map(G,I.permutations(map(N.array,I.product(...
3
APL (Dyalog Unicode), 35 34 bytes
Thanks to Bubbler for -1 byte!
Another port of my Python answer.
0∘{⍵≤⍺:⍵=⍺⋄(⊢+.∇⊢+⍵-×⍨)(⌊⍺*÷2)↓⍳⍵}
Try it online!
The main function is the dfn { ... } which takes \$k\$ as the left argument and \$n+k\$ as the right argument. 0∘ supplies the initial \$k=0\$.
⍵≤⍺:⍵=⍺ is the stopping condition, if \$n+k \le k \Leftrightarrow ...
4
Retina, 65 bytes
.+
*_;
+%L$w`^((^_|\2__)*)(;|(?=(_+);(?!\1)))
$#4*$#2*_$4;$#2*_
;
Try it online! Link includes test suite that tests all n up to and including the input. Explanation:
.+
*_;
Convert the input to unary and append a working area for the previous square root.
+`
Repeat until no new solutions can be found.
%`
Check all lines separately for ...
4
CP-1610 machine code, 31 DECLEs1 ≈ 39 bytes2
1. A CP-1610 opcode is encoded with a 10-bit value (0x000 to 0x3FF), known as a 'DECLE'.
2. As per the exception described in this meta answer, the exact score is 38.75 bytes (310 bits)
This is an implementation with only integer additions, subtractions and comparisons.
A routine taking the input in R1 and ...
2
Perl 5 (-MList::Utils+sum), 64 bytes
sub f{my($n,$k)=@_;sum!$n,map f($n+$k-$_*$_,$_),$k**.5+1..$n+$k}
Try it online!
Using @ovs formula
3
Haskell, 53 bytes
A port of my Python answer.
(#0)
n#k|n==0=1|w<-n+k=sum[(w-d*d)#d|d<-[1..w],d*d>k]
Try it online!
4
05AB1E, 20 19 bytes
Åœ€œ€`ÙʒÅ«t+}н§Å²}g
Brute-force approach, so very slow. Times out for \$\geq10\$.
Try it online or verify the first 9 test cases.
Explanation:
Ŝ # Get all combinations of positive integers that sum to the (implicit)
# input-integer
€ # Map over each inner list:
œ # And get all ...
5
Wolfram Language (Mathematica), 56 50 bytes
If[a=##-i i;0<a<#,a~#0~i,1-Sign@a]~Sum~{i,√+##}&
Try it online!
10
Python 3, 67 bytes
This builds all sequences that sum to \$n\$ and slightly higher and counts those that exactly sum to \$n\$.
f=lambda n,k=0:(n==0)+sum(f(n-d*d+k,d)for d in range(n-~k)if d*d>k)
Try it online!
This approach is based on the observation that \$\sqrt x\$ can only be an integer if \$x\$ is an integer. This means, when building a sequence ...
22
APL (Dyalog Unicode), 39 bytes
+/⊢{∨/⍺⍵<⍵0:0⋄⍺=0:1⋄+/∊∇¨/⍺(⍵*2)-⊂⍳⍺}¨⍳
Try it online!
A tacit function containing an inner dfn to use recursion. Does not use floating point numbers at all.
How it works
First of all, observe that
$$
\displaystyle
\sqrt{a_1+\sqrt{a_2 + \cdots + \stackrel{\vdots}{\sqrt{a_t}}}} \le \cdots \le \sqrt{a_1+a_2 + \cdots + a_t} \...
1
Husk, 9 bytes
↑#≤²∫O¹ηÖ
Try it online! Outputs an empty list if no solution is possible.
0
Java 8, 75 bytes
n->k->{int r=0,a=n*k;for(;a-->0;)if(a%n*(n-a%n)==a/n*(k-a/n))r++;return r;}
Port of @ovs' Python 2 answer, so make sure to upvote him!
Try it online.
1
Perl 5, (-p -Minteger) 54 bytes
/ /;$_=grep$_%$'*($'-$_%$')==$_/$'*($`-$_/$'),1..$`*$'
Try it online!
Using the same formula, and range product as ovs except the range starts from 1
2
Jelly, 8 bytes
r1×ḶċⱮ/S
A monadic Link accepting a pair of integers which yields the count.
Try it online! Or see the test-suite.
How?
r1×ḶċⱮ/S - Link [n,k]
r1 - ([n,k]) inclusive range to 1 = [[n,n-1,...,1],[k,k-1,...,1]]
Ḷ - lowered range ([n,k]) = [[0,1,...,n-1],[0,1,...,k-1]]
× - multiply = [[n×0,(n-1)×1,...,1×(n-1)],[k×0,(k-1)×1,...,...
4
Scala, 65 64 60 51 bytes
n=>k=>0 to n*k-1 count(a=>a%n*(n-a%n)==a/n*(k-a/n))
Try it online!
-1 thanks to user!
-4 thanks to ovs!
-9 thanks to Kjetil!
1
Haskell,53 47 bytes
a#b=sum[1|x<-[1..a],y<-[1..b],x*(a-x)==y*(b-y)]
Try it online!
Saved 6 thanks to @ovs
We use the expression x/(b-y)==y/(a-x) which is converted to x*(a-x)==y*(b-y) to avoid modulo checks.
The expression computes the ratio between sides(the second inverted) which has to be the same to be a valid rectangle.
2
Retina, 45 bytes
\d+
*
L$w`(_+) (_+)
$.`*$1=$.2*$'
m`^(.*)=\1$
Try it online! Link includes test suite. Takes space-separated inputs. Explanation:
\d+
*
Convert the inputs to unary.
L$w`(_+) (_+)
Match all substrings that contain _ _. This corresponds to all pairs of \$ 0 \le x < n \$ and \$ 0 \le y < k \$ which are represented by the unmatched ...
4
C (gcc), 63 61 bytes
Saved 2 thanks to ceilingcat!!!
s;a;f(n,k){for(s=a=n*k;a--;)s-=a%n*(n-a%n)!=a/n*(k-a/n);a=s;}
Try it online!
Port of ovs's Python answer.
6
05AB1E, 10 8 bytes
LDI-*`¢O
Try it online!
Commented:
# implicit input: [n, k]
L # for both values take the [1..x] range
# [[1,...,n], [1,...,k]]
D # duplicate this list
I # push the input [n,k]
- # subtract this from the ranges
# [[1-n,...,n-n], [1-k,...,k-k]]
# =[[-n+1,...,0], [-...
3
Charcoal, 21 bytes
ＮθＮηＩΣＥθ№Ｅη×λ⁻ηλ×ι⁻θι
Try it online! Link is to verbose version of code. Explanation: Calculates \$ x(n-x) \$ for \$ 0 \le x < n \$ and \$ y(n-y) \$ for \$ 0 \le y < k \$ and counts the number of times an integer appears in both lists, which corresponds to the parallelogram with coordinates \$ (x, 0), (0, y), (n - x, 0), (0, k - y) \...
13
Python 2, 66 59 bytes
lambda n,k:sum(a%n*(n-a%n)==a/n*(k-a/n)for a in range(n*k))
Try it online!
Each possible rectangle inside the \$n \times k\$-rectangle can be specified by two integers, \$0 \le a \lt n\$ and \$0 \le b \lt k\$:
To verify a rectangle given \$a\$ and \$b\$, it suffices to check if one angle is a right angle. To do this I take the dot ...
3
JavaScript (ES6), 63 58 56 bytes
Saved 2 bytes thanks to @ovs
(n,y=x=0)=>g=k=>(x=x||++y*k--&&n)&&(y*k==--x*(n-x))+g(k)
Try it online!
2
Jelly, 7 bytes
ŒRṗ²§ċ⁸
Try it online!
Very inefficient; fails to finish within a minute for the last 4 test cases.
How it works
ŒRṗ²§ċ⁸ - Main link. Takes n on the left, d on the right
ŒR - Yield [-n, -n+1, ..., 0, ..., n-1, n]
ṗ - Yield all sublists of this range of length d
² - Square each number
§ - Take the sum of each list
ċ ...
1
Japt, 12 bytes
õ à cá føU ñ
Try it
õ à cá føU ñ :Implicit input of integer U
õ :Range [1,U]
à :Combinations
c :Flat map
á : Permutations
f :Filter
øU : Contains U?
ñ :Sort
2
Scala, 109 bytes
n=>1.to(n).toSet.subsets.flatMap(_.toSeq.permutations).filter(_ toSet n).toSeq.sortBy(_ map(""+)mkString " ")
Try it online!
The interesting part is the _ toSet n in the middle. Removing a little bit of syntactic sugar, it becomes list=>list.toSet().apply(n). This uses the apply method of Set, which is an alias for ...
3
Haskell, 60 bytes
n!b=[[]|all(<n)b]++[k:c|k<-b,c<-n!filter(/=k)b]
f n=n![1..n]
Try it online!
Very much like xnor's Python approach, but my b is the complement of their l.
Explanation
Definition: an n-SDPI is a sequence of distinct positive integers 1 ≤ i ≤ n, among which is n.
We can think about "using up" numbers as we write such a ...
1
Gaia, 9 bytes
┅zf¦e¦Ė⁇ȯ
Try it online!
Generate all permutations of subsets of [1..n], filter out those not containing n, and sort.
1
Perl 5, 52 bytes
$n=$_;map/(.).*\1|[^1-$n]/|!/$n/||say,sort 1..$n x$n
Try it online!
Can run like this for n=3:
echo 3 | perl -nlE'$n=$_;map/(.).*\1|[^1-$n]/|!/$n/||say,sort 1..$n x$n'
But doesn't work for n > 9. For n=7 it used twelve seconds on my humble laptop and then about ten minutes for n=8.
3
JavaScript (ES6), 89 82 bytes
This started as a port of @xnor's method and then was golfed the JS way from there.
f=(n,s=[],i)=>i>n?[]:[...!i^s.includes(i||n)?[]:i?f(n,[...s,i]):[s],...f(n,s,-~i)]
Try it online!
Commented
f = ( // f is a recursive function taking:
n, // n = input
s = [], ...
1
APL (Dyalog Extended), 36 bytes
{∧∪{⍵/⍨w∊¨⍵}⊃,/⊃¨(⊢,,¨)/¨↓⌂pmat⊢w←⍵}
Try it online!
Uses Bubbler's APL tip for generating subsequences of a vector.
Explanation
{∧∪{⍵/⍨w∊¨⍵}⊃,/⊃¨(⊢,,¨)/¨↓⌂pmat⊢w←⍵}
w←⍵ assign input to w for later
⌂pmat⊢ generate matrix of all permutations of 1..input
...
3
K (ngn/k), 24 bytes
{t@<t:(x=|/)#??'1++!x#x}
Try it online!
1
05AB1E, 10 bytes
Lœ€æ€`êʒIå
Try it online.
Explanation:
L # Push a list in the range [1,(implicit) input]
œ # Get all permutations of this list
€ # Map each permutation to:
æ # Get its powerset
€` # Flatten it one level down
ê # Sort and uniquify this list of lists
ʒ # Filter it by:
...
3
Scala, 132 124 117 bytes
n=>1.to(n-1).toSet.subsets().flatMap(_.+(n).toSeq.permutations).toSeq.sorted(Ordering.Implicits.seqOrdering[Seq,Int])
Thanks to user for -7 characters!
Try it online!
3
Wolfram Language (Mathematica), 55 45 bytes
Do[i!=##2&&##~#0~i,{i,0!=##||Print@{##2};#}]&
Try it online!
Inspired by xnor's python solution, and borrows from my answers to some prior problems.
Prints the list of sequences.
Recursively traverses through all permutations of subsequences of 1..n in lexicographic order, printing those which contain ...
7
Husk, 9 bytes
Of€¹umu´π
Try it online!
Explanation
Of€¹umu´π
´π All length n combinations of 1..n
mu Get the unique values of each list
u Get the unique lists
f€¹ Filter by those that contain n
O And sort lexographically
3
SageMath, 93 bytes
lambda n:sorted(sum([[*Permutations(l)]for l in Subsets(range(1,n+1))if n in l],[]),key=list)
Try it online!
Inputs \$n\$ and returns a list of all permutations of every \$s\$ in \$\{s\subseteq\{1,2,\dots,n\} \mid n\in s\}\$ sorted lexicographically.
Explanation
lambda n: # function taking integer n
...
2
Charcoal, 46 bytes
Ｎθ≔⟦υ⟧ηＦθ«≔ηζ≔⟦υ⟧ηＦ⊕ιＦζ⊞η⁺⟦κ⟧Ｅλ⁺쬋μκ»ＩΦ⊕η⁼θ⌈ι
Try it online! Link is to verbose version of code. Directly generates all sequences containing values up to n in lexicographical order and then prints those containing n. Outputs values on separate lines with sequences double-spaced. Explanation:
Ｎθ
Input n.
≔⟦υ⟧η
Start off with a list ...
2
Wolfram Language, 109 bytes
{a_,b___}~p~{c_,d___}:=If[a==c,{b}~p~{d},a~Order~c]
Sort[Join@@Permutations/@Append@#/@Subsets@Range[#-1],p]&
Try it online!
Thanks to @att for a suggestion that saves four bytes.
The first line of this answer is actually a lexicographic ordering function since the default sorting is not lexicographic. It checks if the first ...
3
Scala, 140 bytes
n=>(for{i<-1 to n
c<-1 to n combinations i if c contains n
p<-c.permutations}yield p)sortBy(_.map("%10s"format _ replace(' ','0')).mkString)
Wow, this got long.
Try it online
Explanation:
n =>
(for {
i <- 1 to n //For every i in the range [1..n]
c <- 1 to n combinations i //Every ...
4
Brachylog, 10 bytes
{⟦₆⊇,?p}ᶠo
Try it online!
{…}ᶠo: order all results of:
⟦₆: from [1,2,…,N-1]
⊇: try a subset (e.g. [1,2] then [2] then [1] then [])
,?: append the input [1,2,3]
p: permute the list
8
Python 2, 78 bytes
f=lambda n,l=[]:sum([f(n,l+[i+1])for i in range(n)if~-(i+1in l)],[l]*(n in l))
Try it online!
Python 3 lets us save some bytes with set unpacking.
Python 3, 74 bytes
f=lambda n,l=[]:sum([f(n,l+[i])for i in{*range(1,n+1)}-{*l}],[l]*(n in l))
Try it online!
3
Jelly, 10 9 8 7 bytes
œ!RẎṢiƇ
Try it online!
-1 byte thanks to Sisyphus
-1 more byte thanks to Sisyphus
How it works
œ!RẎṢiƇ - Main link. Takes n on the left
R - Yield [1, 2, ..., n]
œ! - For each i = 1, 2, ..., n, yield all length-n permutations of [1, 2, ..., n]
Ẏ - Join into a single list
Ṣ - Sort
Ƈ - Keep those where
i ...
0
Husk, 8 bytes
#¹´×+m□ṡ
Try it online! or Verify first 25 values
Husk, 8 bytes
#¹mṁ□π2ṡ
Try it online!
1
Husk, 14 bytes
moJ',msfo=¹Σπ²
Try it online!
with the correct output format.
Husk, 7 bytes
fo=¹Σπ²
Try it online!
Inputs are taken as \$n,m\$.
Explanation
fo=¹Σπ²
π cartesian power of n, with range 1..m
f filter the terms where
Σ sum
= equals
¹ m
2
Jelly, 11 bytes
ṗS=¥Ƈ⁸j€”,Y
Try it online!
Boo to restrictive output formats. +5 bytes because of that.
How it works
ṗS=¥Ƈ⁸j€”,Y - Main link. Takes m on the left and n on the right
ṗ - Take the cartesian power of m and n
This returns all lists of length n consisting of the integers 1,...,m
¥Ƈ - Keep those where the following ...
1
Jelly, 7 bytes
rNp`²§ċ
Try it online!
How it works
rNp`²§ċ - Main link. Takes n on the left
N - Yield -n
r - Take the range [-n, -n+1, ..., -1, 0, 1, ..., n-1, n]
` - Use this list for both arguments for:
p - Cartesian product
² - Square each number
§ - Take the sums of each pair
ċ - Count the number of times n ...
1
Japt -x, 11 bytes
õUn)ï £¶Xx²
Try it
6
C (Perl) n=5
My first^Wsecond pass at this is available on github ; I think this should in principle be able to calculate up to a(8), but that'll take a while even now it has been recoded in C.
On my machine it takes 42s for a(4) and 14ks for a(5), traversing 63,200,517 and 18,371,175,865 board positions respectively; rewriting in C gave about a 250x ...
1
Jelly, 5 bytes
ẋ⁹œ!Q
Try it online!
Completely different method to Zacharý's existing aanswer, plus two bytes shorter, so I thought I'd post a separate answer.
The Footer in the TIO link simply runs the above link then checks to see if the result is the same as the Cartesian power builtin. Remove it to see the full output
How it works
ẋ⁹œ!Q - Main link. ...
0
05AB1E, 9 bytes
T3㶫3ãJ»
Uses the digits [1,0]. The T could be replaced with ₂, ₃, or ₆ to use the digits [2,6], [9,5], or [3,6] respectively.
Try it online.
Outputting as an unformatted list could have been 5 bytes: T3ã3ã.
Explanation:
T # Push 10
3ã # Take the cartesian power of 3 with its digits:
# ["111","...
Top 50 recent answers are included
