Как создать матрицу всех двоичных последовательностей 2^n длины n, используя рекурсию в R?

Я знаю, что могу использовать для этого файл expand.grid, но я пытаюсь научиться программировать. Моя цель - взять то, что у меня есть ниже, и использовать рекурсию, чтобы получить все 2 ^ n двоичных последовательностей длины n.

Я могу сделать это для n = 1, но я не понимаю, как я мог бы использовать ту же функцию рекурсивным способом, чтобы получить ответ для более высоких измерений.

Вот для n = 1:

binseq <- function(n){
  binmat <- matrix(nrow = 2^n, ncol = n)
  r <- 0 #row counter
  for (i in 0:1) {
        r <- r + 1
        binmat[r,] <- i
    }
  return(binmat)
  }

Я знаю, что мне, вероятно, придется использовать cbind в операторе return. Моя интуиция подсказывает, что оператор return должен быть чем-то вроде cbind(binseq(n-1), binseq(n)). Но, честно говоря, я совершенно потерялся в этом месте.

Желаемый результат должен в основном рекурсивно производить это для n = 3:


binmat <- matrix(nrow = 8, ncol = 3)
r <- 0 # current row of binmat
for (i in 0:1) {   
for (j in 0:1) {
for (k in 0:1) {
r <- r + 1
binmat[r,] <- c(i, j, k)}   
} 
}
binmat

Это должна быть просто матрица, так как binmat заполняется рекурсивно.


r binary recursion
person Michael    schedule 15.10.2019    source источник
comment
Ваша примерная функция производит NA в матрице. Можете ли вы исправить это или предоставить желаемый результат?   -  person yusuzech    schedule 15.10.2019
comment
это не должно для binseq (1). Моя проблема заключается в обобщении до n › 1 с использованием рекурсии. Желаемый результат также был добавлен.   -  person Michael    schedule 15.10.2019

Ответы (1)


arrow_upward
0
arrow_downward

Я быстро написал эту функцию для генерации всех N^K перестановок длины K для заданных N символов. Надеюсь, это будет полезно.

gen_perm <- function(str=c(""), lst=5, levels = c("0", "1", "2")){
  if (nchar(str) == lst){
    cat(str, "\n")
    return(invisible(NULL))
  }
  for (i in levels){
    gen_perm(str = paste0(str,i), lst=lst, levels=levels)
  }
}

# sample call
gen_perm(lst = 3, levels = c("x", "T", "a"))

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

ОБНОВЛЕНИЕ Я изменил приведенный выше код для решения вашей проблемы. Обратите внимание, что заполняемая матрица находится в глобальной среде. Функция также использует переменную tmp для передачи строк в глобальную среду. Для меня это был самый простой способ решить проблему. Возможно, есть и другие способы.

levels <- c(0,1)
nc <- 3

m <- matrix(numeric(0), ncol = nc)

gen_perm <- function(row=numeric(), lst=nc, levels = levels){
  if (length(row) == lst){
    assign("tmp", row, .GlobalEnv)
    with(.GlobalEnv, {m <- rbind(m, tmp); rownames(m) <- NULL})
    return(invisible(NULL))
  }
  for (i in levels){
    gen_perm(row=c(row,i), lst=lst, levels=levels)
  }
}

gen_perm(lst=nc, levels=levels)

ОБНОВЛЕНИЕ 2. Чтобы получить ожидаемый результат, запустите

m <- matrix(numeric(0), ncol = 3)
gen_perm(lst = 3, levels = c(0,1))
m

levels задает диапазон значений для генерации (бинарных в нашем случае) для генерации перестановок, m — пустая матрица для заполнения, gen_perm генерирует строки и добавляет их в матрицу m, lst — длина перестановки (соответствует количеству столбцы матрицы).

person slava-kohut    schedule 15.10.2019
comment
Я в основном понимаю, что это делает, хотя я ищу более числовой подход, а не вставку символов. Я посмотрю, поможет ли это мне понять, где я ошибаюсь, хотя дополнительная помощь, безусловно, будет оценена. Спасибо! - person Michael; 15.10.2019
comment
не совсем. это далеко за пределами моего уровня. я в основном работаю с учебником, и я изменил свой ожидаемый ответ, чтобы показать, что именно я пытаюсь воспроизвести, но рекурсивно для больших n. Мое исходное решение, или первый шаг, технически даже не дает всех возможностей только для n = 1. - person Michael; 15.10.2019
comment
@Michael Я включил пример и некоторые разъяснения в свой пост выше. - person slava-kohut; 15.10.2019