Использование R: поиск наименьшего набора числовых подстрок c, которые могут «определить» все возможные перестановки последующих цифр в более длинных строках

Question

Если мне даны два произвольных числа, которые являются началом и концом (включительно) непрерывной последовательности натуральных чисел, каков эффективный способ в R найти самый маленький набор подстрок, которые «содержат» каждое число в этой последовательности из начало до конца?

Редактировать: Чтобы прояснить, что происходит, следующая ссылка имеет два примера, выбранных для представления различных случаев и для удобства просмотра. Наш фактический рабочий ввод включает в себя намного большие числовые последовательности с гораздо большим количеством цифр, поэтому наш текущий подход основан на рекурсии.

Первый пример имеет начальную точку 500 и конечную точку 699, что означает набор оперируются все числа чисел c от 500 до 699 включительно. Решение "5", потому что оно содержит каждую строку, символы которой начинаются с "5". IE от 500 до 599. Аналогично для "6".

Второй пример более сложный. Заданные начальная и конечная точки - от 533 до 555. Это означает, что первая часть решения - «533-539». Это не может быть просто «53», потому что это будет включать «530, 531, 532», которые не включены в заданный исходный диапазон. Таким образом, 533 - 539 должны быть перечислены полностью. Однако следующая часть решения на одну git короче, это всего лишь "54", потому что каждая перестановка "54X" от "540" до "549" включена. Затем последняя часть отсчитывает «550-555», потому что опять-таки не каждое число, которое может начинаться с подстроки «55», является частью данного диапазона.

Итак, вы можете увидеть, как это выглядит визуально, вот наш текущий код и некоторые примеры данных . Вы можете вставить это прямо в что-то вроде PHPtester. net и посмотреть, как каждая пара «начало» и «конец» превращается в набор подстрок.

Я пытался преобразовать это в R и заменить его циклы на векторизованные альтернативы или функции, такие как map, насколько это возможно, но я все еще в основном следую его первоначальному решению:

1. Разделите всю последовательность от начала до конца на группы по 10, где "имя" каждой группы является родительской строкой (IE "55" = c (550: 559)).

2. Проверьте, какова длина каждой группы и, если ее длина меньше 10, экспортируйте ее в список вывода и удалите ее, в противном случае, если длина составляет 10 элементов, удалите ее и замените ее на one-di git -shorter подстрока.

3. Повторяйте процесс рекурсивно до тех пор, пока вы не перестанете получать группы длиной 10 элементов.

Я понял, что это напомнило мне о том, что Я смутно помню из теории множеств в бакалавриате. Существует ли пакет анализа строк или наборов, который уже решает эту конкретную проблему c? Или лучший способ для реализации этого решения? Прямо сейчас лучшая реализация R, о которой я могу думать, это в значительной степени опираться на purrr и dplyr для группирования и вложения / удаления вложений по мере необходимости, но инстинкт подсказывает мне, что это, вероятно, будет плохо масштабироваться, когда я начну бросать десятки тысяч начальных и конечных пар в это.

Я также готов дать python шанс, если это могло бы предложить намного лучшее решение, хотя я все еще новичок в этом и намного лучше знаком с R.

Answer 1

Вот один из способов сделать это. По сути, начиная с начальной последовательности, вы ищите полные последовательности из сотен, удаляете их из последовательности. Затем найдите полные последовательности десятков, удалите их из последовательности и объедините остальные.

x <- 533:555
result <- NULL

#full hundreds
my.list <- split(x,floor(x/100)*100)
full_hundreds <- which(lengths(my.list)==100)
if(length(full_hundreds)>0){
  result <- c(result,substring(names(full_hundreds), 1,1))
  x <- as.vector(unlist(my.list[-full_hundreds]))
}

#full tens
if(length(x)>0){
  my.list <- split(x,floor(x/10)*10)
full_tens <- which(lengths(my.list)==10)
if(length(full_tens)>0){
  result <- c(result,substring(names(full_tens), 1,2))
  x <- as.vector(unlist(my.list[-full_tens]))
  }
}

result <- c(result,x)
# [1] "54"  "533" "534" "535" "536" "537" "538" "539" "550" "551" "552" "553" "554" "555"

С:

x <- 500:699
#[1] "5" "6"

Answer 2

Вот как будет выглядеть ответ Пьера ЛаПуанта в общем случае (обратите внимание, что вы делаете 10 ** (j-1), а не 10 ** j, как я упоминал в комментарии).

x <- 780:913
result <- NULL
ndigits <- as.integer(log10(max(x))) + 1
for (j in seq(ndigits, 1, -1)) {
    ej <- 10 ** (j - 1)
    my.list <- split(x, floor(x / ej) * ej)
    full_0s <- which(lengths(my.list) == ej)
    if (length(full_0s) > 0){
        result <- c(result, substring(names(full_0s), 1, 1 + (ndigits - j)))
        x <- as.vector(unlist(my.list[-full_0s]))
    }
}

result <- c(result, x)

Возвращает:

> sort(result)
[1] "78"  "79"  "8"   "90"  "910" "911" "912" "913"