New answers tagged combinatorics
0
J, 18 bytes
*/@,@(1+%)1++/&i./
Try it online!
Takes z on its left and x y on the right.
Uses modified formula by Peter Taylor:
$$
\begin{align}
\prod_{i=1}^x \prod_{j=1}^y \frac{i+j+z-1}{i+j-1} &= \prod_{i=1}^x \prod_{j=1}^y \left(1 + \frac{z}{i+j-1}\right) \\
&= \prod_{i=0}^{x-1} \prod_{j=0}^{y-1} \left(1 + \frac{z}{i+j+1}\right)
\end{align}...
0
Charcoal, 112 104 bytes
⊞υＥθ⁰Ｆυ¿¬ⅈ¿№…ιＬθη⪫✂ιＬθＬι¹ «ＦＬθＦ²⊞υ⁺Ｅι⎇⁼κν∧λ§θκμ⟦§EFλκ⟧ＦＬθＦＬθ¿⁻λκ«≔⌊⟦§ιλ⁻§θκ§ικ⟧ε⊞υ⁺Ｅι⎇⁼κν⁺με⎇⁼λν⁻μεμ⟦Pλκ
Try it online! Link is to verbose version of code. Could save 6 bytes by including the final bucket state in the output. The code spends most of its time emptying or pouring empty buckets, so don't try it on the harder problems. ...
3
JavaScript (ES6), 197 191 188 bytes
Takes input as (a)(t).
Returns a string of concatenated operations Fx, Ex or Px>y, with 0-indexed buckets.
a=>F=(t,N)=>(g=(b,n,o)=>[...b,0].some((V,i,x)=>(x=a[i])-V^t?n&&b.some((v,j,[...B])=>(s='F',B[j]=i-j?x?(v+=V)-(B[s=`P${i}>`,i]=x<v?x:v):a[s='E',j]:0,g(B,n-1,[o]+s+j))):O=o)...
0
Javascript, 364 bytes
I'm sure this can be golfed much better pretty easily.
S=t=>G=>{L=t.length;r=(f,n,a,i,e=0)=>{if(0==n)return f.indexOf(G)>=0&&[];a=(A,B,C,D)=>(X=f.slice(),X[A]=B,X[C]=D,X);for(;e<L;++e){for(K of[0,t[e]])if(F=r(a(e,K),n-1))return[[+!K,e]].concat(F);for(i=0;i<L;++i)if(i!=e&&(O=r(a(e,Math.max(0,f[e]-t[...
6
Python 3, 243 239 bytes
-4 bytes thanks to @JonathanFrech!
def f(a,t,k=1):
while g(a,t,[0]*len(a),[],k):k+=1
def g(a,t,c,p,k):n=len(a);k,i=k//n,k%n;k,j=k//n,k%n;exec(["c[i]=0","c[i]=a[i]","x=min(a[j]-c[j],c[i]);c[i]-=x;c[j]+=x"][k%3]);p+=k%3,i,j;return g(a,t,c,p,k//3)if k>2else{t}-{*c}or print(p)
Try it online!
Input: a list of bucket capacities a, ...
0
x86 machine code, 155 bytes
Hexdump:
60 8b fa 51 b0 20 f3 aa 59 51 b0 5f 03 c9 f3 aa
5e b0 0a aa 57 5f 57 b7 2f 8d 14 36 8b ce 2b ca
75 03 80 f7 73 7d 02 f7 d1 51 b0 20 f3 aa 59 8a
c7 aa 8b ee 53 6b d9 fe 8d 5c b3 ff 53 6b de fc
8b 5c 1f fe 8b 47 fe 80 fc 5f 74 23 8a c4 34 73
3c 2f 75 0a 80 ff 5f 74 3e 80 ff 5c 74 37 c1 eb
08 66 81 fb 2f 5c 74 2f 0f c7 f3 ...
1
Jelly, 14 bytes
A monadic link taking an integer as input; computes the first n terms of the sequence.
÷3Ḟ,ĊƊḶ+
ŻÇ€Fḣ
Try it online! This is a port of Bubbler's answer, so be sure to upvote him as well!
How it works:
ŻÇ€Fḣ Main link: monad taking integer n as input
Ż Create the range [0, ..., n]
Ç€ Map the auxiliar link over the ...
3
APL (Dyalog Unicode), 23 bytesSBCS
⊢↑∘(∊⊢+∘(⍳¨⌊,⌈)¨÷∘3)⍳,⊢
Try it online!
A tacit function that returns the first n terms of the sequence.
Observation
n m | f(n,m): m consecutive integers starting at n
---------------
1 0 |
1 1 | 1
2 0 |
2 1 | 2
3 1 | 3
3 1 | 3
4 1 | 4
4 2 | 4 5
5 1 | 5
5 2 | 5 6
6 2 | 6 7
6 2 | 6 7
7 2 | 7 8
7 3 | 7 8 9
8 2 | 8 9
8 3 ...
2
MATL, 48 bytes
0i:"J_Q@q:gJJq1_J_tQ5$h@Y"&h]YsG:)&Zjyy+vt0Z)=as
Try it online! Or verify all test cases.
Explanation
This uses coordinate axes 60 degrees apart, so that cell coordinates are integer values. In addition, coordinates (r,s) are stored as a complex number r+j*s, where j is the imaginary unit.
The code first creates n layers of the ...
9
JavaScript (ES6), 178 169 168 bytes
Returns the \$n\$ first terms as an array.
n=>(X=[1],Y=[L=1],d=5,j=x=y=0,g=a=>--n?g([...a,(X[x+=~-'210012'[d%=6]]=-~X[x])+(Y[y+=~-'1221'[j?d:d++]]=-~Y[y])+(Z[x+y]=-~Z[x+y])-2],++j%L?0:(j%=L*6)?d++:L++):a)(Z=[1])
Try it online!
How?
This is a rather naive approach that actually computes the spiral ...
1
C (gcc), 38 bytes
f(n){n=n>1?(n+n--)*f(n)-n*n*f(n-1):n;}
Port of Jonathan Allan's Python 3.8 answer.
Try it online!
1
Haskell, 34 bytes
a 0=0
a n=n*a(n-1)+product[1..n-1]
Try it online!
This implements the OEIS definition.
0
MathGolf, 5 bytes
╒k!╠Σ
Try it online.
Or
!k╒/Σ
Try it online.
Explanation:
╒ # Push a list in the range [1, (implicit) input-integer]
k! # Push the input-integer again, and pop and push its factorial
╠ # Divide the factorial by each value in the list (b/a builtin)
Σ # And sum that list
# (after which the entire stack joined ...
1
J, 9 bytes
1#.!%1+i.
Try it online!
1#. the sum of (by conversion to base 1)
! n factorial
% divided by
1+i. the list 1..n
K (oK), 16 12 bytes
-4 bytes thanks to ngn!
+/*/'1+&:'~=
Try it online!
0
Factor, 61 bytes
: f ( n -- n ) [1,b] dup [ product ] dip [ / ] with map sum ;
Try it online!
0
Racket, 70 bytes
(λ(x)(let([a(range 1(+ 1 x))])(apply +(map(λ(y)(/(apply * a)y))a))))
Try it online!
2
Python 3, 389
import itertools as I
S=sorted
P=I.product
def C(n,m,k):
Q=[((-1,)*(n-m)+(0,)*m,)]
for i in' '*(k-1):Q=set(tuple(S(q+(v,)))for q in Q for v in P(*[(-1,0,1)]*n)if sum(map(abs,v))==n-m if not v in q and any(sum((a!=b)*(1+2*a*b)for a,b in zip(v,u))==2for u in q))
return sum(all(S(q)<=S(zip(*r))for X in I.permutations(zip(*q))for r in P(*((p,...
1
W j, 5 4 bytes
After scanning through the source, I realized an undocumented feature - the j flag can actually sum the output at the end!
7Uëÿ
Uncompressed:
*rak/
Explanation
*r % Reduce via multiplication
% (Contains implicit range)
ak % Range from input to 1
/ % Division (integer division when
% none of the operands are ...
4
APL (Dyalog), 5 bytes
+/!÷⍳
Try it online!
Calculates the sum of (+/) the factorial of \$n\$ (!) divided by (÷) the range 1 to \$n\$ (⍳).
1
Perl 6, 22 bytes
{sum [*]($_)X/$_}o^*+1
Try it online!
Returns the sum of the factorial of \$n\$ divided by the range 1 to \$n\$.
0
C (gcc), 70 \$\cdots\$ 64 63 bytes
Saved a byte thanks to ceilingcat!!!
Saved a byte thanks to Surculose Sputum!!!
l;c;i;t;f(n){l=0;for(c=i=1;i<n;l=c,c=t)t=-l*i*i+c*(i+++i);n=c;}
Try it online!
Uses Arnauld's formula.
2
Charcoal, 12 bytes
≔…·¹ＮθＩΣ÷Πθθ
Try it online! Link is to verbose version of code. Explanation:
≔…·¹Ｎθ
Create a range from 1 to n.
θ Range `1`..`n`
Π Product i.e. `n!`
÷ Vectorised divide by
θ Range `1`..`n`
Σ Sum
Ｉ Cast to string
Implicitly print
3
Python 3.8, 50 49 bytes
-1 thanks to Surculose Sputum (using walrus in 3.8 to save some ~-s)
f=lambda n:n>1and(2*n-1)*f(n:=n-1)-n*n*f(n-1)or n
Try it online!
A 52 using a different approach:
f=lambda n,k=2:n*k and~-n*f(n-1,k)+f(n-1,k-1)or n==k
Try it online!
3
Python 3, 57 bytes
f=lambda n:n and n*f(n-1)+math.factorial(n-1)
import math
Try it online!
Implements the recurrence relation given by
$$\begin{cases}a(n) = n\times a(n-1) + (n-1)! \\
a(0) = 0 \end{cases}$$
How: If you have \$n\$ trains on the railway, consider removing the faster one from the railway and take the \$(n-1)!\$ permutations of the ...
3
05AB1E, 5 bytes
!IL÷O
Try it online!
0
Japt -x, 5 bytes
ÆÊ/°X
Try it
2
Python 2, 57 52 50 bytes
-2 bytes thanks to @JonathanAllan !
i=x=0
f=1
exec"i+=1;x=i*x+f;f*=i;"*input()
print x
Try it online!
If the sequence is 0-indexed, we can cut down 2 more bytes
Python 2, 48 bytes
i=x=f=1
exec"i+=1;x=i*x+f;f*=i;"*input()
print x
Try it online!
How:
This solution uses the exec trick, which repeats the code n times, then exec ...
4
JavaScript (ES6), 34 bytes
f=n=>n>1?(n+--n)*f(n)-n*n*f(n-1):n
Try it online!
This is an implementation of the recurrence relation:
$$\cases{
a(0)=0\\
a(1)=1\\
a(n) = a(n-1) \times (2n - 1) - a(n-2) \times (n - 1)^2,\:n>1}$$
3
Wolfram Language (Mathematica), 15 bytes
Tr[#!/Range@#]&
-1 byte from @Greg Martin
Try it online!
9
Jelly, 5 4 bytes
!:RS
Try it online! Or see the test-suite.
How?
When we introduce an \$n^{\text{th}}\$ train it allows:
\$(n-1)!\$ states - by being placed behind none of the \$n-1\$ existing trains and being faster than all of them.
all the previous end states, each in \$n\$ different ways - by being placed behind at least one existing ...
0
Jelly, 9 bytes
Œ!«\€Q€FL
Try it online!
this is the non-smart trivial approach
Explanation
Observe that if we have a list of trains' speeds, moving left, then we can cumulatively reduce by minimum to get the final list of trains' speeds.
Œ!«\€Q€FL Main Link
Œ! all permutations (defaults over a range)
€ For each permutation
\ ...
1
C (gcc), 1769 bytes, n=14 in 31 sec. on TIO
n=15 in 2 min 7sec on my MacBook Pro (3.1 GHz Intel Core i7)
NOTE: If you test this program to see how far it can get in one minute,
change #define END to be some larger number, say (17). The value
of (14) was picked so as not to time out in 1 minute on TIO.
Output will be computed from n = START to n = END.
...
0
PHP, 117
function f1($a1){
$a2=[[]];
foreach($a1 as $a3){
foreach($a2 as $a4){
$a2[]=array_merge([$a3],$a4);
}
}
return $a2;
}
2
Rust, (n=15 ~6 sec, n=16 ~25 sec on 2.5GHz intel i7)
More heavily parallelised rewrite of @monicareinstate's answer in rust
src/main.rs
use rayon::prelude::*;
const MAX_N: usize = 22;
const ARRAY_SIZE: usize = 1 << MAX_N;
static mut LOOKUP: [u8; ARRAY_SIZE] = [0; ARRAY_SIZE];
#[inline]
fn longest_sub(left: u32, right: u32, bits: u8) -> (u8, ...
8
C++, n = 21 (40s on an AMD Ryzen 5 2500U)
This used to be a fast brute force answer that got up to n=17. That is currently preserved in the revision history.
#include <cstring>
#include <omp.h>
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#include <unordered_map>
#...
2
Java, n=11 (~30-35 sec on TIO)
import java.util.ArrayList;
import java.util.List;
class Main{
public static void main(String[] args){
for(int n=1; ; n++){
String binaryFormat="%"+n+"s";
int sum=0, c=0;
double powerOf2=Math.pow(2,n);
for(int a=0; a<powerOf2; a++){
String binaryA=toBinary(n,a);
for(int b=0; b&...
2
Python 3 308 293 bytes, n=10 (30sec TIO)
a=lambda S,T:max((*(i+1 for i in range(len(S)) for j in range(len(S)-i)if S[j:j+i+1]in T),0));b=lambda i,n:'0'*(n-len(bin(i)[2:]))+bin(i)[2:]
for n in range(1,11):m=2**n;t=sum([a(b(i,n),b(j,n))for i in range(m)for j in range(m)]);y=bin(t);v=2**(len(y)-len(y.rstrip('0')));print(t/v,'/',4**n/v)
Try it online!
Not ...
1
Pyth, 20 bytes
{SMfqQlMTSMMs./M.pUs
Try it online!
Explanation
{SMfqQlMTSMMs./M.pUsQ # full program (Q=input, last one is implicit)
UsQ # range(sum(Q))
.p # get all permutations
s./M # for each permutation, get all partitions, concatenate to one list
SMM # sort each list in each ...
4
Wolfram Language (Mathematica), n=12 (~53s TIO)
t=0;
For[i=0,i<2^a,i++,
For[j=0,j<2^(a-1),j++,
t=t+Length@LongestCommonSubsequence[IntegerDigits[i,2,a],IntegerDigits[j,2,a]]]]
Try it online!
1
R (with partitions library), 86 bytes
function(l,n)lapply(partitions::listParts(n),function(x)if(all(lengths(x)==l))show(x))
Try it online at RDRR!
Assumes that l is sorted in decreasing order. Will print a lot of fluff after the answer, so I advise to call invisible(f(l, n)) rather than f(l, n).
The function listParts lists all the partitions of 1:n; ...
1
Charcoal, 95 bytes
⊞υＥ⊕⌈θＥ№θι⟦⟧Ｆη«≔υζ≔⟦⟧υＦζＦＬκＦ∨⊕⌕§κλ⟦⟧№θλ¿‹Ｌ§§κλμλ⊞υＥκ⎇⁻ξλνＥν⎇⁻ρμπ⁺π⟦ι⟧»≔⟦⟧ζＦυ«≔⟦⟧εＦιＦκ⊞ελ⊞ζε»⪫ζ¶
Try it online! Link is to verbose version of code. I don't often get to use the r variable; I think this might be only the second time ever. Takes the set counts and unique entries as arguments. Explanation:
⊞υＥ⊕⌈θＥ№θι⟦⟧
Make a list of lists ...
1
GAP, 145 127 105 bytes
f:={l,c}->(i->Orbit(SymmetricGroup(c),Set(l,n->Set([1..n],k->NextIterator(i))),OnSetsSets))(Iterator(c));
Try it online!
This is absurdly long, but I like computing the answer as an orbit of a group action. I have mixed feelings about creating the first element using an Iterator...
1
Husk, 14 bytes
u→SġÖȯLuΣmOΠMṖ
Try it online!
...I feel like the →SġÖȯLuΣ (last-entry-of hook group-by sort-by compose length deduplicate concatenated) should be XȯLuΣ where X is "maximals-by-predicate", saving 3 bytes, but I can't seem to find such a high-level-function. Maybe I'm being blind?
2
Japt -Q, 13 bytes
á £V®Xj0Z ñ
â
Try it
Submissions
(1/5) Japt, 9 bytes
(2/5) CJam, 23 bytes
(3/5) Japt, 40 or 41 bytes (I don't know which one to use, I'm not sure if the 40 byte one is valid)
(4/5) Magma, 34 bytes
Total Score: 120 (or maybe 119)
1
J, 47 bytes
[:~.~:@I.(/:(#,])&.>)@(<@/:~;.1)"1[:(!A.&i.])+/
Try it online!
I entirely missed the Portuguese one, so I'm out of the final prize anyway.
And J is not so good for handling non-rectangular arrays.
How it works
[:~.~:@I.(/:(#,])&.>)@(<@/:~;.1)"1[:(!A.&i.])+/
[:(!A.&i.])+/ NB. all permutations of 0..n-1
...
3
Jelly, 12 bytes
œcŒpṢ€FQƑ$ƇQ
Try it online!
Overal RGS admissible competition entries:
RGS 1/5 - Jelly, 7
RGS 2/5 - Husk, 22
RGS 3/5 - Jelly, 36
RGS 4/5 - MATL, 26 *
This: 12
Total = 103 bytes
* Might be 25, but I haven't proven that the 25 would never yield multiple results
3
Jelly, 12 bytes
œcŒpFQƑ$ƇṢ€Q
Try it online!
A dyadic link taking the list of \$n\$ integers as the left argument and the list of set lengths as the right. Returns a list of lists.
Thanks to @KevinCruijssen for pointing out an omission in my original answer.
Previous RGS submissions:
Jelly 12 bytes
BBC BASIC V 92 bytes
Jelly 37 bytes
R 128 bytes
Jelly ...
3
Jelly, 16 15 13 bytes
Œ!ṁ€R}Ṣ€Ṣ¥€ṢQ
-2 bytes thanks to @NickKennedy by golfing the loose link to an inline one with }.
Try it online.
Explanation:
Œ!ṁ€R}Ṣ€Ṣ¥€ṢQ # Main link taking two list arguments
# i.e. left=[0,1,2,3,4]; right=[1,2,2]
Œ! # Get all permutations of the (implicit) left argument
# i.e. [0,1,2,...
5
Python 3, 123 118 114 112 bytes
Input: set s representing a list of n unique elements, and an iterable l representing the multiset.
Output: a set of all partitions, where each partition is a tuple of tuples of elements (aka output is a set of tuples of tuples).
lambda s,l:{(*sorted(p),)for p in product(*(combinations(s,i)for i in l))if{*sum(p,p)}>s}
...
5
05AB1E, 9 bytes
œεI£€{{}ê
Try it online!
œ # permutations of the [0, ..., n-1] input
ε } # for each permutation:
I£ # cut it in parts of lengths given by the second input
€{ # sort each part
{ # sort the list of parts
ê # sort and uniquify the list of lists of parts
Top 50 recent answers are included
