Все к-меры / н-граммы

21

вступление

У нас были гистограммы и подсчеты , но мы не перечислили их все.

Ежегодно ООО «Дьялог» проводит студенческий конкурс. Задача состоит в том, чтобы написать хороший код APL. Это не зависящее от языка издание шестой проблемы этого года.

У меня есть явное разрешение опубликовать этот вызов здесь от первоначального автора конкурса. Не стесняйтесь проверить, перейдя по предоставленной ссылке и связавшись с автором.

проблема

Термин k-mer обычно относится ко всем возможным подстрокам длины k , которые содержатся в строке. В вычислительной геномике k-меры относятся ко всем возможным подпоследовательностям (длиной k ) из чтения, полученного с помощью секвенирования ДНК. Напишите функцию / программу, которая принимает строку и k (длину подстроки) и возвращает / выводит вектор k-мер исходной строки.

Примеры

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

k > длина строки? Ничего не вернуть / пустой результат:
[4,"AC"][]или ""или[""]

Адам
источник
4
Имеет ли значение порядок вывода? Когда подстрока встречается несколько раз, должна ли она быть повторена в выходных данных?
feersum
1
Могу ли я вернуть строку обязательных подстрок, разделенных символами новой строки вместо массива строк, как это ?
Утренняя монахиня
Можем ли мы также ввести и вывести строку в виде массива символов (например, ['A', 'T', 'C', 'G']вместо "ATCG"?
Аднан,
Разрешены ли ответы Dyalog APL в этом вызове PPCG (поскольку вызов также проводится Dyalog)?
Kritixi Lithos
1
@feersum Порядок имеет значение, и повторы должны быть повторены. Это как скользящее окно.
Адам

Ответы:

15

Желе , 1 байт

У желе есть однобайтовый диадический атом для этой самой операции

Попробуйте онлайн! (нижний колонтитул разделяет результирующий список с помощью новых строк, чтобы избежать печатного представления.)

Джонатан Аллан
источник
1
Каким-то образом ОП должен был знать ...
Утренняя монахиня
1
@ LeakyNun Я действительно не сделал.
Адам
8

Октава, 28 байт

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

Попробуйте онлайн!

Для k> длина строки работает в окнах Octave 4.2.1, но в tio (Octave 4.0.3) не работает.

Создает числовые индексы последовательных элементов и индексирует строку по ним.

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
rahnema1
источник
7

C (GCC на POSIX), 67 66 63 байта

-3 байта благодаря @LeakyNun!

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

Попробуйте онлайн!

betseg
источник
Я не думаю, что вам нужно j=0.
Утренняя монахиня
@LeakyNun функция должна быть многоразовой. Попробуйте онлайн! vs Попробуйте онлайн!
betseg
Хотя, если я сделаю это ...
betseg
1
Вы можете заменить j+i<=strlen(s)на простоs[j+i]
Kritixi Lithos
5

Брахилог , 3 байта

s₎ᶠ

Попробуйте онлайн!

Технические характеристики:

  • Входные данные: ["ATCGAAGGTCGT",4]
  • Аргумент: Z
  • Выход: Z = ["ATCG","TCGA","CGAA","GAAG","AAGG","AGGT","GGTC","GTCG","TCGT"]

Как это устроено

s₎ᶠ
s    Output is a substring of first element of input,
 ₎   with length specified by second element of input.
  ᶠ  Find all solutions.
Дрянная Монахиня
источник
5

Python 3 ,  47 45 42 байта

-3 байта благодаря ovs (используйте распаковку Python 3 для повторного использования a[n-1:]в конце)

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

Рекурсивная функция, принимающая строку, aдлину среза nи возвращающая список срезов или пустую строку.

a[n-1:]берет фрагмент текущей строки из n-1- го (0-индексированного) элемента и далее, чтобы проверить, достаточно ли осталось элементов (пустая строка - ложная в Python) - это короче, чем эквивалент len(a)>=n.

  • Если имеется достаточное количество элементов списка конструируют, [...]с первыми nэлементами строки, a[:n]и распакованного результате повторного вызова функции, *f(...)с версией из очереди на вход тока (без первого элемента), a[1:].

  • Если элементов недостаточно, хвост рекурсии достигается, когда a[n-1:]возвращается (в этом случае пустая строка).

Попробуйте онлайн!


45 для Python 2 или 3 с:

f=lambda a,n:a[n-1:]and[a[:n]]+f(a[1:],n)or[]
Джонатан Аллан
источник
f=lambda a,n:a[n-1:]and[a[:n],*f(a[1:],n)]42 байт (Python 3) Тио
овс
@ovs, очень приятно, я спросил, приемлемо ли это (поскольку пустым результатом является строка, а непустым результатом является список).
Джонатан Аллан
4

J , 2 байта

,\

Это не полная программа, а функция с оператором.

Назовите это так:

echo 4 ,\ 'ATCGAAGGTCGT'

Попробуйте онлайн!

Как это устроено

Оператор (называемый «конъюнкция») \(называемый « инфикс ») используется следующим образом:

(x u\ y)применяет глагол uк последовательным частям списка y(называемым инфиксами).

Функция (называемая «глаголом») uв этом случае является функцией, ,которая является простой функцией « добавления »:

Создает массив, содержащий элементы, за xкоторыми следуют элементы y.

Дрянная Монахиня
источник
3

Mathematica, 21 байт

##~StringPartition~1&

Анонимная функция. Принимает строку и число (в этом порядке) в качестве входных данных и возвращает список строк в качестве выходных данных.

LegionMammal978
источник
3

Р, 65 61 байт

-2 байта благодаря MickyT

-2 байта путем изменения индексации

возвращает анонимную функцию.

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

substringциклически перебирает индексы (в отличие от substrкоторых нет), и если начальный индекс меньше 1, по умолчанию1 вместо этого, поэтому он проверяет и возвращает пустую строку.

x:n-n+1эквивалентно 1:(x-n+1)с: имеет приоритет над суммами / разностями

Попробуйте онлайн!

Giuseppe
источник
Вы можете сохранить пару байтов с помощью function(s,n,x=nchar(s))if(n>x,'',substring(s,1:(x-n+1),n:x))
MickyT
@ MickyT, спасибо! Я также заметил, что могу изменить некоторые байты, изменив вычисление индекса
Giuseppe
2

Pyth , 2 байта

.:

Это не полная программа, а встроенная функция.

Назовите это так:

.:"ATCGAAGGTCGT"4

Попробуйте онлайн!

Полная программа:

.:.*

Попробуйте онлайн!

( .*Сплат.)

Дрянная Монахиня
источник
Хотя это на самом деле не имеет значения, .:Fэто короче байта для полной программы.
FryAmTheEggman
2

Медуза , 7 байт

p
_I
\i

Попробуйте онлайн!

Как это устроено

В линейном:, p(\(I,i))где pпечать и \получает необходимые подстроки.

Iявляется необработанным первым вводом, в то время iкак оценивается вторым вводом.

В Jellyfish каждая функция и оператор получают два аргумента: один справа и один снизу. Здесь функция pполучает аргумент из выходных данных _, который необходим, если мы хотим использовать оператор \для получения подстрок.

Дрянная Монахиня
источник
2

Clojure, 19 байт

Ну это удобно

#(partition % 1 %2)

Примеры:

(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))
 ()]
NikoNyrh
источник
2

CJam , 4 байта

{ew}

Анонимный блок, который ожидает аргументы в стеке и оставляет результат в стеке после.

Попробуйте онлайн!

ew это встроенный, который делает именно то, что требуется.

Бизнес Кот
источник
5
У меня есть только одна вещь, чтобы сказать: ew
Adám
2

Retina , 41 38 байт

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

Попробуйте онлайн!

Берет строку и рассчитывает на отдельные строки. Первые две строки используются для преобразования числа из десятичного в унарное, поэтому, если унарный ввод допустим, то количество байтов будет уменьшено до 34 31. Редактирование: 3 байта сохранены благодаря @FryAmTheEggman. Или, если вы предпочитаете, 48-байтовую версию, которая обрабатывает символы новой строки в строке, хотя это приводит к сбивающему с толку выводу:

.*$
$*
!&`(\S|\s)+(?=[\S\s]*¶(?<-1>.)+(?(1)$.)$)
Нил
источник
@KritixiLithos Я не понимаю, как ваше решение учитывает счет ...
Нил
Ой, извини, у меня только что
пукнул
Это не обязательно работает, если строка может содержать символ новой строки, поэтому я думаю, что вы можете изменить (?!)на .
FryAmTheEggman
2

Октава с пакетом изображений, 29 байт

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

Попробуйте онлайн!

объяснение

Функция im2col(m,b)берет матрицу m, извлекает bиз нее блоки размером и размещает их в виде столбцов. По умолчанию блоки являются скользящими (в отличие от отдельных). Здесь матрица mпредставляет собой вектор-строку кодов ASCII входной строки s(это делается как +s, что короче, чем стандарт double(s)), а размер bпредназначен [1 n]для получения горизонтально скользящих блоковn элементов.

Результат транспонируется (используя сложное-сопряженное транспонирование ', которое короче, чем транспонирование .'), чтобы превратить столбцы в строки, и затем он преобразуется обратно в символ ( [... '']который короче, чем стандарт char(...)).

Луис Мендо
источник
1

Python 3 , 49 байт

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

Попробуйте онлайн!

Нерекурсивное решение, хотя и не короче.

Совместим с Python 2.

Дрянная Монахиня
источник
Вы можете удалить f=, сохранив два байта, потому что вы не используете fгде-либо еще. По умолчанию функции, которые только что объявлены и не используются, могут быть оставлены без имени.
г-н Xcoder
1

PHP, 75 байт

Онлайн версия

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

80 байт без двойных значений

for([,$n,$s]=$argv;$i+$n-1<strlen($s);)$r[$p=substr($s,$i++,$n)]=$p;print_r($r);
Йорг Хюльсерманн
источник
1

Haskell, 39 байт

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

Пример использования: 4 # "ABCDEF"-> ["ABCD","BCDE","CDEF"]. Попробуйте онлайн!

Простая рекурсия, которая сохраняет первые nсимволы входной строки, продолжается с хвоста строки, пока ее длина не меньше чем n.

Ними
источник
1

Microsoft Sql Server, 199 байт

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

Проверь это.

Андрей Одегов
источник
1

С накоплением , 7 байтов

infixes

Попробуйте онлайн!

Довольно стандартный. Без этого встроенного, это становится 20 байтами:

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

Который:

{%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
Конор О'Брайен
источник
1

C # 89 байт

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

Попробуйте онлайн!

Лучший метод, который я мог найти в C #, в основном такой же, как Java

Skidsdev
источник
1

Рубин, 48 46 байт

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

Никаких особых трюков, просто лямбда-определение, определяющая функцию, которая извлекает необходимую подстроку из каждой действительной начальной точки.

Сохранено два байта, поскольку нет необходимости хранить лямбду.

Chowlett
источник
1

V , 16 байтов

òÀ|ly0Ïp
"_xòkVp

Боюсь, не очень хорошо в гольф, борясь с "удалить строку, если k> len (str)". Вход находится в файле, k является аргументом. Гольф перед объяснением

Попробуйте онлайн!

nmjcman101
источник
Что произойдет, если вы не попытаетесь разобраться с делом k> len (str)?
Адам
В зависимости от метода, который я использую (в частности, в этом), он просто оставляет строку как есть
nmjcman101
1

Стандарт ML (mosml), 109 65 61 байт

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

Принимает число и список символов (довольно распространенная альтернатива строкам в мире SML). (Действительно работает во всех списках, конечно.)

Использование:

- 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:

  • Хорошо, есть стандартная библиотека .. (-44 байта)
  • Измените сравнение и nil на [] как предложено (-4 байта)
L3viathan
источник
1
Вы можете сохранить байт, изменив if length(x)<n thenна if n>length(x)then. Однако, поскольку SML вполне может обрабатывать строки, я не уверен, что разрешено требовать, чтобы explodeего уже применяли к входной строке.
Лайкони
Также then nil elseможет быть сокращено до then[]else.
Лайкони
@ Лайкони тоже не уверен, но ¯ \ _ (ツ) _ / ¯
L3viathan
Используя некоторые другие библиотечные функции, я получил 68-байтовую версию, которая работает со строками вместо списков символов. Кроме того, ваш подход может быть сокращен до 54 байт: fun f$n=if n>length$then[]else List.take($,n)::f(tl$)n.
Лайкони
1

JavaScript (Firefox 30-57), 51 байт

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

64 байта в ES6:

(s,n,t=s.slice(0,--n))=>[...s.slice(n)].map(c=>(t+=c).slice(~n))
Нил
источник