Skip to content
ihsan edited this page Aug 29, 2022 · 108 revisions

Idioms

Anyone may add idioms to the list. See also K by example.

Basic

Swap Variable Values x[2 5]:x[5 2]
p:2 5; x[p]:x@|p
Coerce Array (),x
Fill (right) to length fr: {@[y#z;!#x;:;x]}
Fill (left) to length fl: {(#x)!@[y#z;!#x;:;x]}

Numerical

Factorial */1+!:
Fibonacci {(x(|+\)\1 1)[;1]}
Fibonacci {x{x,+/-2#x}/!2}
Recursive Fibonacci {:[x<2;1;_f[x-1]+_f[x-2]]}
Recursive Fibonacci (memoized) {c::.();{v:c[a:`$$x];:[x<3;1;:[_n~v;c[a]:_f[x-1]+_f[x-2];v]]}x}
Maximum subsequence sum |/0(0|+)\
Positive divisors of n, inclusive {&~x!'!1+x}
Positive divisors of n, inclusive (faster) {d:&~x!'!1+_sqrt x;d,_ x%|d}
Reduced digit sum +/0$'$:
Collatz sequence (1<){:[x!2;1+3*x;_ x%2]}\
Collatz sequence (shorter) (1<){(_ x%2;1+3*x)x!2}\
Identity matrix
{a=/:a:!x}
{(x,x)#1,x#0}
{(-!x)!\:1,(x-1)#0}
GCD gcd:{:[~x;y;_f[y;x!y]]} gcd:{*{0<x 1}{{(y;x!y)}.(x)}/(x;y)}
LCM {_ x*y%gcd[x;y]}
Magnitude {_sqrt+/_sqr x}
Log base n logn: {(_log x)%_log y}
Vector Dot Product
_dot
dot: {+/x*y}
3×3 matrix determinant dt33:{-/{+/(*)/(!).'+(y*!3;x)}[x]'1 -1}
3-Vector Cross Product cross: {{-/{(*)/(!).'+(y*1+!2;x)}[x]'1 -1}2 3#x,y}
Unit Vector unit: {x%\:_sqrt x _dot x}

Primality

Primes to n, exclusive 2_&{&/x!'2_!x}'!:
Primes to n, sieve {2_&{:[x@y;x&@[1,-1_ z#(1_ y#1),0;y;:;1];x]}/[x#1;2_!__ceil_sqrt x;x]}
Primes to n, sieve (Arthur 1) {:[x<4;,2;r,1_&~|/x#'~!:'r: _f[_ _ceil _sqrt x]]}
Is n a prime?
isp: {(x>1)&&/x!'2_!1+_sqrt x}
isp2: {2~#&~x!'!1+x}
Next prime {~isp x}{x+1}/
First n primes prsn: {(x-1){:[isp n:x+1;n;_f n]}\2}
N’th prime prn: {*|prsn x}
Prime factors
pfac:{
  n:2,3+2*!.5*_sqrt x
  d:n@&~x!'n
  m:d@&~1<+/~d!\:/:d
  p:,/{n:+/0=x!'y^1+!_ logn[x;y];n#y}[x;]'m
  :[_n~p;x;_dv[p,_ x%*/p;1]]}

Combinatorics

Pascal’s triangle with n+1 rows pasc: {x{+':0,x,0}\1}
Binomial {[n;k]pasc[n][n;k]}
{[n;k]i:!k-1;_*/(n-i)%i+1}
Is x a permutation vector? x~<<x
Random permutation of 0,…,n-1 n _draw -n
Nth permutation nperm: {y@{{<:<:y,x}/|x}'+({a-!a:#x}y)_vs(@x),:/x}
Permutation index {(a-!a:#x)_sv{+/x<*x}'(!#x)_\:x}
Permutations on n elements
perm: {:[1<x;,/(>:'(x,x)#1,x#0)[;0,'1+_f x-1];,!x]}
perm2: {{x@<x}x{,/x(1!)\'x,'#*x}/,!0}
perm3: {nperm[!*/1+!x;!x]}
Permutation cycles {{={x[y]@<x[y]}[x]'!#x}(x\'!#x)}
All permutations of x with the length y permlen:{x@v@&((y;1)~^=:)'v:!y##x}
Combinations, k out of n elements {{x@<x}@&:'k(?,/(1!)\'r,')/,(r:k=y)=&x-k:y&x-y}
Combinations, k out of n elements, unsorted, unoptimized {&:'y(?,/(1!)\'1,')/,&x-y}
Enumerate all values of length x in base y {(x#y)_vs!_ y^x}
{!x#y}
Bitstrings of length x {(x#2)_vs!_ 2^x}
{!x#2}
!2+&:
Power set {x@/:&:'2_vs!_2^#x}
{x[&:'!2+&#x]}
Are all values in the array different? {(#x)=#?x}
Sliding window {(!1+y-x)+\:!x}

Statistics

Arithmetic mean am: {(+/x)%#x}
Harmonic mean %am@%:
Geometric mean {(*/x)^%#x}
Median {(x@<x)@_(#x)%2}
Sample variance sv: {+/(_sqr x-am x)%#x}
Standard deviation {_sqrt sv x}
Histogram {c:w@*:'=w:x;@[(1+|/c)#0;c;:;(#:'=w)]}

Dates

Is x a leap year? {(+/~x!'4 100 400)!2}
Day of the Week `Mon`Tue`Wed`Thu`Fri`Sat`Sun@(_ _t%86400)!7

Sorting

Sort list x@<x
Sort list x[<x]
Sort list function {x@<x}
Sort list descending x@>x
Unique {x[*:'=x]}
Non-unique elements {x@&1<#:'=x}
Quicksort {f:*x@1?#x;:[0=#x;x;,/(_f x@&x<f;x@&x=f;_f x@&x>f)]}

Selections

Overlapping infixes {:[y>#x;,x;x@(!y)+/:!(1-y)+#x]}
Non-overlapping infixes {(y*!_ceil(#x)%y)_ x}
Main diagonal {x ./:n,'n:!#x}
Secondary diagonals {x ./:/:f@-1_1_=+/'f:,/n,/:\:n:!#x}

Strings

Delete leading blanks dlb: {x@&|\~x=" "}
Delete trailing blanks {|dlb@|x}
Delete multiple blanks {x@&a|1_1!1,a:~x=" "}
Left justify {(+/&\x=" ")!x}
Right justify {(1-(x=" ")_sv 1)!x}
Lower Case Letters lcase: _ci 97+!26
Upper Case Letters ucase: _ci 65+!26
To Lower Case {@[x;p;:;lcase@n@p:&26>n:ucase?/:x]}
To Upper Case {@[x;p;:;ucase@n@p:&26>n:lcase?/:x]}

Unsorted

Frequency table (sorted) {b@<b:(x@*:'a),'#:'a:=x}
Anagrams {x g@&1<#:'g:={x@<x}'x}
Rot 13 {a:+65 97+\:2 13#!26;_ci@[!256;a;:;|a]_ic x}
8-queens p@&{a:{(#x)=#?x};i:!#x;a[x[i]+i]&a[x[i]-i]}'(p:perm 8)
Variants:
p@&{&/{(#x)=#?x}'(x[i]+i;x[i]-i:!#x)}'(p:perm 8)
p@&{&/{(#x)=#?x}'(+;-).\:(x[i];i:!#x)}'(p:perm 8)
Perfect shuffle {x@<>(#x)#1 0}
Perfect shuffle (for 2*n)
{{m:_((#x)%2);,/+(x[!m];x[m+!m])}\(!x*2)}
{x@<>(#x)#1 0}\!:2*
Life (Knuth’s approach)
{m:x;m:m+(1!'m)+-1!'m;m:m+(1!m)+-1!m;m:m+m-x;m _lin\:5 6 7}
{((2*+/,/2{-1 0 1!'\:x}/x)-x)_lin\:5 6 7}
{|/(1;x)&3 4=\:+/,/2{-1 0 1!'\:x}/x}
One dimensional cellular automata (rule 104) "_X"@{2=+/(0,x,0)@(!#x)+/:!3}\0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0
Clone this wiki locally