Все возможные комбинации точек между алфавитами в R - PullRequest
Новая
       8

Все возможные комбинации точек между алфавитами в R

0 голосов
/ 14 января 2019

У меня есть строка "ab", и я хочу сгенерировать все возможные комбинации точек между a, b. Например,

imageenter image description here">

В этом случае может быть максимум 3 точки (нет двух последовательных точек), а минимальные точки равны 0. «ab» - просто игрушечный пример, а длина строки может достигать 30. Я понятия не имею, с чего начать. Любая помощь будет высоко оценена. Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 15 января 2019

Это похоже на Звезды и бары . Здесь наши буквы аналогичны звездам, а точки аналогичны столбцам: 

## transform string into stars and bars format
ab

## add spaces around each letter    
_a_b_

## substitute stars (i.e. asterisks) for letters
_*_*_

Теперь мы просто задаем вопрос:

Учитывая n пробелов, сколько способов мы можем заполнить эти пробелы с 0 до n баров?

Как указал @Gregor, это оказывается суммой биномиальных коэффициентов (при условии n букв): 

sum(sapply(0:(n + 1), function(x) combinat::nCm(n + 1, x))) == 2^(n + 1)

С помощью базы R мы можем легко достичь желаемого результата: 

myStr <- "abcd"
indStr <- strsplit(myStr, split = "")[[1]]
strTemplate <- vector("character", length = (length(indStr) * 2 + 1))
strTemplate[seq(2, length(strTemplate), 2)] <- indStr

strTemplate
[1] ""  "a" ""  "b" ""  "c" ""  "d" "" 

dotVec <- seq(1L, length(strTemplate), 2L)

dotVec
[1] 1 3 5 7 9

unlist(lapply(1:length(dotVec), function(x) {
    combn(dotVec, x, FUN = function(y) {
        temp <- strTemplate
        temp[y] <- "."
        paste0(temp, collapse = "")
    })
}))

 [1] ".abcd"     "a.bcd"     "ab.cd"     "abc.d"     "abcd."    
 [6] ".a.bcd"    ".ab.cd"    ".abc.d"    ".abcd."    "a.b.cd"   
[11] "a.bc.d"    "a.bcd."    "ab.c.d"    "ab.cd."    "abc.d."   
[16] ".a.b.cd"   ".a.bc.d"   ".a.bcd."   ".ab.c.d"   ".ab.cd."  
[21] ".abc.d."   "a.b.c.d"   "a.b.cd."   "a.bc.d."   "ab.c.d."  
[26] ".a.b.c.d"  ".a.b.cd."  ".a.bc.d."  ".ab.c.d."  "a.b.c.d." 
[31] ".a.b.c.d."
0 голосов
/ 14 января 2019

Это намеренно не полный ответ, но это очень хорошее начало.

Если у вас есть n буквы, есть n + 1 возможные позиции для точек и 2^(n + 1), поскольку каждая позиция может иметь либо точку, либо отсутствие точки. Вам просто нужно перебрать эти возможности. Мы начнем с генерации этих 2^(n + 1) точечных образцов, используя expand.grid: 

input = "abc"
n = nchar(input)
dots = do.call(expand.grid, rep(list(c("", ".")), n + 1))
dots
#    Var1 Var2 Var3 Var4
# 1                     
# 2     .               
# 3          .          
# 4     .    .          
# 5               .     
# 6     .         .     
# 7          .    .     
# 8     .    .    .     
# 9                    .
# 10    .              .
# 11         .         .
# 12    .    .         .
# 13              .    .
# 14    .         .    .
# 15         .    .    .
# 16    .    .    .    .

Я дам вам закончить - разбить вашу входную строку на отдельные буквы strsplit(input, "") и использовать paste0 или аналогичный для объединения букв с точками.

Вы говорите, что ваш ввод может иметь длину до 30. В результате будет 2 ^ 31 = 2 147 483 648 комбинаций, что довольно много. Вы можете столкнуться с ограничениями памяти, делая это в R, в зависимости от вашей машины. Я бы подумал о том, нужно ли вам действительно генерировать все комбинаций. Обычно лучше подходить к использованию итераторов (см., Например, пакет iterators). Это может помочь вам создать любую произвольную комбинацию, которую вы хотите, без необходимости генерировать каждую комбинацию.

...