-
Notifications
You must be signed in to change notification settings - Fork 139
Idioms
ihsan edited this page Aug 29, 2022
·
108 revisions
Anyone may add idioms to the list. See also K by example.
| 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]} |
| 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 |
|
|||
| 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 |
|
|||
| 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} |
| 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? | |
| 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]]}
|
| 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 |
|
|||
| 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} |
| 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)]} |
| Is x a leap year? | {(+/~x!'4 100 400)!2} |
| Day of the Week | `Mon`Tue`Wed`Thu`Fri`Sat`Sun@(_ _t%86400)!7 |
| 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)]} |
| 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} |
| 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]} |
| 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) |
|
|||
| Life (Knuth’s approach) |
|
|||
| 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 |