All the k-mers/n-grams

Question

Intro

We have had histograms and counting, but not listing all of them.

Every year, Dyalog Ltd. holds a student competition. The challenge there is to write good APL code. This is a language agnostic code-golf edition of this year's sixth problem.

I have explicit permission to post this challenge here from the original author of the competition. Feel free to verify by following the provided link and contacting the author.

Problem

The term k-mer typically refers to all the possible substrings of length k that are contained in a string. In computational genomics, k-mers refer to all the possible subsequences (of length k) from a read obtained through DNA Sequencing. Write a function/program that takes a string and k (the substring length) and returns/outputs a vector of the k-mers of the original string.

Examples

[4,"ATCGAAGGTCGT"] → ["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

k > string length? Return nothing/any empty result:
[4,"AC"] → [] or "" or [""]

Answer 1

Jelly, 1 byte

ṡ

Jelly has a single byte dyadic atom for this very operation

Try it online! (the footer splits the resulting list with newlines, to avoid a mushed representation being printed.)

Answer 2

Octave, 28 bytes

@(N,s)s((1:N)+(0:nnz(s)-N)')

Try it online!

For k > string length works in Octave 4.2.1-windows but in tio (Octave 4.0.3) doesn't work.

Creates numeric indexes of consecutive elements and index the string by it.

s= "ATCGAAGGTCGT"
N = 4
idx = (1:N)+(0:nnz(s)-N)'
 =
    1    2    3    4
    2    3    4    5
    3    4    5    6
    4    5    6    7
    5    6    7    8
    6    7    8    9
    7    8    9   10
    8    9   10   11
    9   10   11   12

s(idx) =

ATCG
TCGA
CGAA
GAAG
AAGG
AGGT
GGTC
GTCG
TCGT

Answer 3

C (GCC on POSIX), 67 66 63 bytes

-3 bytes thanks to @LeakyNun!

f(i,s,j)char*s;{for(;j+i<=strlen(s);puts(""))write(1,s+j++,i);}

Try it online!

Answer 4

05AB1E, 2 bytes

Code:

Ν

Explanation:

Π     # Get all substrings of the input
 ù     # Only keep the substrings of length the second input

Uses the 05AB1E encoding.

Try it online!

Answer 5

Python 3,  47 45 42 bytes

-3 bytes thanks to ovs (use Python 3's unpacking to reuse a[n-1:] at the tail.)

f=lambda a,n:a[n-1:]and[a[:n],*f(a[1:],n)]

A recursive function taking the string, a, and the slice length, n, and returning a list of the slices or an empty string.

a[n-1:] takes a slice of the current string from the n-1^th (0-indexed) element onward to test whether there are enough elements remaining (an empty string is falsey in Python) - this is shorter than the equivalent len(a)>=n.

• If there are enough elements a list is constructed, [...], with the first n elements of the string, a[:n], and the unpacked result of calling the function again, *f(...), with a dequeued version of the current input (without the first element), a[1:].

• If there are not enough elements the tail of the recursion is reached when a[n-1:] is returned (in this case an empty string).

Try it online!

---

45 for Python 2 or 3 with:

f=lambda a,n:a[n-1:]and[a[:n]]+f(a[1:],n)or[]

Answer 6

Brachylog, 3 bytes

s₎ᶠ

Try it online!

Specs:

• Input: ["ATCGAAGGTCGT",4]
• Argument: Z
• Output: Z = ["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

How it works

s₎ᶠ
s    Output is a substring of first element of input,
 ₎   with length specified by second element of input.
  ᶠ  Find all solutions.

Answer 7

J, 2 bytes

,\

It is not a complete program, but a function with an operator.

Call it as such:

echo 4 ,\ 'ATCGAAGGTCGT'

Try it online!

How it works

The operator (called "conjunction") \ (named "infix") is used as such:

(x u\ y) applies verb u to successive parts of list y (called infixes).

The function (called "verb") u in this case is the function , which is a simple "append" function:

Creates an array containing the items of x followed by the items of y.

Answer 8

Mathematica, 21 bytes

##~StringPartition~1&

Anonymous function. Takes a string and a number (in that order) as input and returns a list of strings as output.

Answer 9

R, 65 61 bytes

-2 bytes thanks to MickyT

-2 bytes by changing the indexing

returns an anonymous function.

function(s,n,x=nchar(s))`if`(n>x,'',substring(s,x:n-n+1,n:x))

substring cycles through the indices (as opposed to substr which does not), and if the starting index is less than 1, it defaults to 1 instead, so it checks and returns the empty string.

x:n-n+1 is equivalent to 1:(x-n+1) since : takes precedence over sums/differences

Try it online!

Answer 10

Pyth, 2 bytes

.:

It is not a complete program, but a built-in function.

Call it as such:

.:"ATCGAAGGTCGT"4

Try it online!

Full program:

.:.*

Try it online!

(The .* is splat.)

Answer 11

Jellyfish, 7 bytes

p
_I
\i

Try it online!

How it works

In linear: p(\(I,i)), where p is print and \ gets the required substrings.

I is the raw first input while i is the evaluated second input.

In Jellyfish, every function and operator gets two arguments, one from the right, and one from the bottom. Here, the function p gets the argument from the output of _, which is required if we are to use the operator \ to get substrings.

Answer 12

Java (OpenJDK 8), 92 bytes

void f(String s,int n){for(int i=n;i<=s.length();)System.out.println(s.substring(i-n,i++));}

Try it online!

Answer 13

Retina, 41 38 bytes

.*$
$*
!&`(.)+(?=.*¶(?<-1>.)+(?(1)¶)$)

Try it online!

Takes the string and count on separate lines. The first two lines are used to convert the count from decimal to unary, so if unary input is acceptable then the byte count would be reduced to 34 31. Edit: Saved 3 bytes thanks to @FryAmTheEggman. Or, if you prefer, a 48-byte version that handles newlines in the string, although that does produce confusing output:

.*$
$*
!&`(\S|\s)+(?=[\S\s]*¶(?<-1>.)+(?(1)$.)$)

Answer 14

Octave with Image Package, 29 bytes

@(s,n)[im2col(+s, [1 n])' '']

Try it online!

Explanation

The function im2col(m,b) takes a matrix m, extracts blocks of size b from it, and arranges them as columns. By default blocks are sliding (as opposed to distinct). Here the matrix m is a row vector of the ASCII codes of the input string s (this is done as +s, which is shorter than the standard double(s)), and the size b is [1 n] to obtain horizontally sliding blocks of n elements.

The result is transposed (using complex-conjugate transpose ', which is shorter than transpose .') to turn the columns into rows, and then it is converted back to char ([... ''], which is shorter than the standard char(...)).

Answer 15

Python 2, 54 bytes

lambda x,n:map(''.join,zip(*[x[b:]for b in range(n)]))

Try it online!

Answer 16

Clojure, 19 bytes

Well this is handy:

#(partition % 1 %2)

Examples:

(def f #(partition % 1 %2))
(println [(f 4 "ATCGAAGGTCGT")
          (f 4 "abc")])

[((A T C G) (T C G A) (C G A A) (G A A G) (A A G G) (A G G T) (G G T C) (G T C G) (T C G T))
 ()]

Answer 17

CJam, 4 bytes

{ew}

Anonymous block that expects the arguments on the stack and leaves the result on the stack after.

Try it online!

ew is a built-in that does exactly what is required.

Answer 18

oK, 2 bytes

':

oK has a sliding window operator!

Answer 19

Python 3, 49 bytes

f=lambda a,n:[a[i:i+n]for i in range(len(a)-n+1)]

Try it online!

A non-recursive solution, albeit not shorter.

Compatible with Python 2.

Answer 20

JavaScript (Firefox 30-57), 51 bytes

(s,n,t='')=>[for(c of s)if((t+=c)[n-1])t.slice(-n)]

64 bytes in ES6:

(s,n,t=s.slice(0,--n))=>[...s.slice(n)].map(c=>(t+=c).slice(~n))

Answer 21

PHP, 75 Bytes

Online Version

for([,$n,$s]=$argv;$i+$n-1<strlen($s);)$r[]=substr($s,$i++,$n);print_r($r);

80 Bytes without double values

for([,$n,$s]=$argv;$i+$n-1<strlen($s);)$r[$p=substr($s,$i++,$n)]=$p;print_r($r);

Answer 22

Haskell, 39 bytes

n#s|length s<n=[]|1<2=take n s:n#tail s

Usage example: 4 # "ABCDEF" -> ["ABCD","BCDE","CDEF"]. Try it online!

A simple recursion that keeps the first n chars of the input string an continues with the tail of the string as long as its length is not less than n.

Answer 23

Microsoft Sql Server, 199 bytes

create function dbo.f(@s nvarchar(max),@ int)returns table as return
with v as(select 2 p,left(@s,@)g where len(@s)>=@ union all
select p+1,substring(@s,p,@)from v where len(@s)>p-2+@)select g from v

Check it.

Answer 24

PowerShell, 70 bytes

$b={$c,$s=$args;[regex]::matches($s,"(?=(.{$c}))")|%{''+$_.groups[1]}}

Try it online!

Answer 25

Stacked, 7 bytes

infixes

Try it online!

Pretty standard. Without this builtin, it becomes 20 bytes:

{%x#'y-#+:>y#-#>x\#}

Which is:

{%x#'y-#+:>y#-#>x\#}
{%                 }   dyad; first arg: x, second arg: y
  x#'                  length of x (the array)
     y-                minus y (the skew)
       #+              plus 1
         :>            range [x, y]
           y#-         y minus 1
              #>       range from [[x, y], [x, y] + y]
                x\#    get indices from x

Answer 26

MATL, 3 bytes

YC!

Try it online!

Explanation

YC   % Sliding blocks of input string with input size, arranged as columns
!    % Transpose

Answer 27

C# 89 bytes

void a(string s,int n){for(int i=n;i<=s.Length;)Console.WriteLine(s.Substring(i++-n,n));}

Try it online!

Best method I could find in C# is basically the same as Java

Answer 28

Ruby, 48 46 bytes

->(s,k){0.upto(s.size-k).map{|i|s[i..i+k-1]}}

No particular tricks, just a stabby-lambda defining a function that pulls the required substring from each valid starting point.

Saved two bytes, since there doesn't seem to be a need to store the lambda.

Answer 29

V, 16 bytes

òÀ|ly0Ïp
"_xòkVp

Not terribly well golfed I'm afraid, struggling with "delete the string if k > len(str)". Input is in the file, k is an argument. Golfing before explanation

Try it online!

Answer 30

Dyalog APL, 13 11 bytes

⊢,/⍨⊣⌊1+∘⍴⊢

It does exactly as intended now. Stupid errors. Thanks to Adám for giving me the hint that there is an 11 byte solution, even though this isn't the one he was looking for.

Answer 31

Standard ML (mosml), 109 65 61 bytes

fun f(n,x)=if n>length(x)then[]else List.take(x,n)::f(n,tl x)

Takes a number and a character list (quite a common alternative to strings in the SML world). (Really works on all lists of course.)

Usage:

- f(3,explode("ABCDEFGH"));
> val it =
    [[#"A", #"B", #"C"], [#"B", #"C", #"D"], [#"C", #"D", #"E"],
     [#"D", #"E", #"F"], [#"E", #"F", #"G"], [#"F", #"G", #"H"]] :
  char list list
- f(7, explode("ABCD"));
> val it = [] : char list list

Changelog:

• Right, there is a standard library.. (-44 bytes)
• Change comparison and nil to [] as suggested (-4 bytes)

Answer 32

Standard ML, 68 bytes

fun f$n=List.tabulate(size$ -n+1,fn m=>substring($,m,n))handle _=>[]

Try it online! Example usage: f "abcdef" 3 returns ["abc", "bcd", "cde", "def"].

Explanation:

For two bytes more we can replace the identifier $ by s to get better readable code:

fun f s n=List.tabulate(size s-n+1,fn m=>substring(s,m,n))handle _=>[]

The function takes a string s and an integer n as arguments. List.tabulate(m,g) takes an integer m and some function g and builds the list [g 0, g 1, ..., g(m-1)]. In this case, we give for m the size of the string s minus the n-gram length n (+1 to avoid off-by-one-errors). For each such m we return the substring of s at position m with length n.

In case of n > size s, an exception is thrown. handle _=>[] catches the exception and returns the empty list.

Answer 33

brainfuck, 52 bytes

[[>],+[<]>-]>[->]<[[<]>[.>]<[<]++++++++++.>[-]>[>],]

Try it online!

Takes K as the value on the starting cell and the string as input.

Answer 34

q/kdb+, 19 bytes

Solution:

{(0-x)_x#'next\[y]}

Example:

q){(0-x)_x#'next\[y]}[4;"ABCDEFGHIJ"]
"ABCD"
"BCDE"
"CDEF"
"DEFG"
"EFGH"
"FGHI"
"GHIJ"
q){(0-x)_x#'next\[y]}[4;"AC"]
q)

Explanation:

Use next and scan over the input string, then take the first 'x' (sliding window size), then drop off the extras from the end:

{(0-x)_x#'next\[y]} / the solution
{                 } / anonymous lambda with implicit args x and y
          next\[y]  / take 'next' element of y until exhausted
       x#'          / x take-each (take first x chars of each)
 (0-x)              / negate x
      _             / drop (negative drops from the end rather than front)

Answer 35

Japt, 2 bytes

Straightforward, built-in solution.

ãV

Try it