Поиск всех комбинаций с использованием рекурсии в R - PullRequest
Новая
       20

Поиск всех комбинаций с использованием рекурсии в R

1 голос
/ 11 марта 2020

У меня проблема с возвратом значений из рекурсивных функций, надеюсь, вы мне поможете. У меня есть список с кучей матриц, каждая матрица представляет набор возможных комбинаций и генерируется с помощью combn (). Например, это может быть 3 матрицы внутри списка: 

# set 1 has 4 elements, do nCk = 4C1:
set1 <- c("b2","b3","b4","b5")
set1 <- combn(set1,1,simplify = T)  

# set 2 has 3 elements, choose 2:
set2 <- c("c1","c2","b2")
set2 <- combn(set2,2,simplify = T)

# set 3 has 10 elements, choose 1:
set3 <- combn(c(1:10),1, simplify = T)

Например, если бы мы печатали set2, в нем было бы 2 строки (выберите 2) и 3 столбца (3C2 = 3). : 

> set2
     [,1] [,2] [,3]
[1,] "c1" "c1" "c2"
[2,] "c2" "b2" "b2"

Мне нужно получить все возможные комбинации из 4 элементов (1 элемент на набор выше). Я могу сделать это, используя while l oop и имитируя конечный автомат, но это решение неуклюже и создает длинный код. Я знаю, что это можно сделать с помощью рекурсии, так как я смог напечатать правильно 120 комбинаций (код ниже), но при попытке вернуть их или сохранить их в переменной я либо получаю ошибку <font color="red">subscript out of bounds или результаты повторяются тысячи раз. Я также хочу избегать глобальных переменных, это будет встроено в довольно большой проект, поэтому я бы предпочел не задевать мое рабочее пространство большим количеством переменных, чем необходимо.

Конечно, при развертывании количество наборов будет будьте динамичны c, и элементы в наборе также изменятся. Наборы также не слишком велики, поэтому я хотел бы реализовать рекурсивный подход!

Рабочий код для печати: 

combb <- function(allsets, number, carry){
  if(number>length(allsets)){
    print(carry)
    return()
  } else{
    for(j in 1:length(allsets[[number]][1,])){
      newcarry <- c(carry, allsets[[number]][,j])
      number2 <- number + 1
      combb(allsets, number2, newcarry)
    }
  }
}

Спасибо!

1 Ответ

1 голос
/ 12 марта 2020

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

combb <- function(allsets){

  carry <- integer(0)
  height <- 0L
  for (j in 1:length(allsets)) {
    height <- height + length(allsets[[j]][, 1])
  }

  output <- matrix(allsets[[1]][0, 1], nrow = height, ncol = 0)

  combb1 <- function(allsets, number, carry) {
    if(number > length(allsets)){
      output <<- cbind(output, carry, deparse.level = 0)
      return()
    } else{
      for (j in 1:length(allsets[[number]][1,])) {
        # Only add unique combinations (some combinations are vectors)
        if((TRUE %in% (allsets[[number]][, j] %in% carry)) == FALSE) {
          newcarry <- c(carry, allsets[[number]][, j], use.names = FALSE)
          number2 <- number + 1
          combb1(allsets, number2, newcarry)
        } else{
          next()
        }
      }
    }
  }

  combb1(allsets, 1, carry)

  return(output)
}

Как вы можете видеть из этого решения, рекурсия аккуратна (функция combb1) и не загромождает ни одну из переменных глобального / рабочего пространства.

...