LEXF: Enumerating k-mers Lexicographically | Ben Cunningham

# LEXF: Enumerating k-mers Lexicographically

Problem by Rosalind · on July 1, 2012

Assume that an alphabet $\mathscr{A}$ has a predetermined order; that is, we write the alphabet as a permutation $\mathscr{A} = (a_1, a_2, \ldots, a_k)$, where $% $. For instance, the English alphabet is organized as $(\textrm{A}, \textrm{B}, \ldots, \textrm{Z})$.

Given two strings $s$ and $t$ having the same length $n$, we say that $s$ precedes $t$ in the lexicographic order (and write $% $) if the first symbol $s[j]$ that doesn’t match $t[j]$ satisfies $% $ in $\mathscr{A}$.

Given: A collection of at most 10 symbols defining an ordered alphabet, and a positive integer $n$ ($n \leq 10$).

Return: All strings of length $n$ that can be formed from the alphabet, ordered lexicographically (use the standard order of symbols in the English alphabet).

## Sample Dataset

A C G T
2


## Sample Output

AA
AC
AG
AT
CA
CC
CG
CT
GA
GC
GG
GT
TA
TC
TG
TT


# R

library(readr)
library(gtools)

Error in library(gtools): there is no package called 'gtools'

library(magrittr)

f <- "lexf.txt"

raw <-
strsplit(split = "\n") %>%
unlist()

a <-
raw[1] %>%
strsplit(split = " ") %>%
unlist()
n <- as.numeric(raw[2])

p <- permutations(length(a), n, v = a, repeats.allowed = TRUE)

Error in permutations(length(a), n, v = a, repeats.allowed = TRUE): could not find function "permutations"

apply(p, 1, paste, collapse = "") %>%
cat(sep = "\n")

Error in apply(p, 1, paste, collapse = ""): object 'p' not found