Поиск комбинаций значений с ограничениями в R - PullRequest
Новая
       10

Поиск комбинаций значений с ограничениями в R

0 голосов
/ 26 ноября 2018

У меня есть набор значений в векторе, например, 

all_points <- c(1, 4, 2, 12, 6, 5, 25)

Я хочу найти все возможные комбинации, где числа слева направо расположены в порядке возрастания.Первый и последний номера всегда будут включены.Например, в этом случае они будут: 

1, 4, 12, 25
1, 4, 6, 25
1, 4, 25
1, 2, 12, 25
1, 2, 6, 25
1, 2, 5, 25
1, 2, 25
1, 12, 25
1, 6, 25
1, 5, 25
1, 25

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

my_recursive_function <- function(input_points, running_vector = c(1)){
    start_point <- input_points[1]
    rightward_points <- input_points[2:length(input_points)
    for(i in 1:length(rightward_points)){
        if(rightward_points[i] != 25 & rightward_points[i] > start_point){
            set_of_points <- c(running_vector, rightward_points[i])
            my_recursive_function(rightward_points, set_of_points)
        }
        if(rightward_points[i] == 25){
            print(c(running_vector, 25)
            flush.console()
            #I will end up doing more than printing here, but this is enough for the example
        }

        #do something to return to the previous level of recursion, 
        #including returning running_vector and rightward_points
        #to the appropriate states
    }

Так что, надеюсь, это имеет смысл.У меня есть 2 вопроса:

  1. Я слишком усложняю это, и есть лучший способ?Это своего рода алгоритм поиска, пересекающий древовидную структуру, поэтому здесь я могу сделать что-то умное, чего не вижу.
  2. Если это лучший способ, как мне сделать бит псевдокодавнизу?Я очень запутался, пытаясь понять, как выглядит каждый вектор, на каждом уровне рекурсии, и как извлечь элементы из моего running_vector.

Ответы [ 2 ]

0 голосов
/ 26 ноября 2018

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

non_recursive_function <- function(X){
  N <- length(X)
  X2 <- X[-c(1, N)]
  res <- lapply(seq_along(X2), function(k) t(combn(X2, k)))
  inx <- lapply(res, function(x){
    apply(x, 1, function(y) all(diff(y) > 0))
  })
  res <- lapply(seq_along(res), function(i) res[[i]][inx[[i]], ])
  res <- res[sapply(res, length) > 0]
  res <- lapply(res, function(x) 
    apply(as.matrix(x), 1, function(y) c(X[1], y, X[N])))
  res
}

all_points <- c(1, 4, 2, 12, 6, 5, 25)
x <- non_recursive_function(all_points)
0 голосов
/ 26 ноября 2018

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

combis <- lapply(0L:(length(all_points)-2L), 
            function(n) combn(
                seq_along(all_points)[c(-1L, -length(all_points))], 
                n, 
                function(x) all_points[x],
                FALSE))

lapply(unlist(combis, recursive=FALSE),
    function(x) c(all_points[1L], x, all_points[length(all_points)]))

Пояснение

1) Первая строкакода берет число элементов (n) между первым и последним элементом и генерирует все возможные комбинации индексов, а затем извлекает соответствующие элементы, используя function(x) all_points[x]

2) unlist(..., recursive=FALSE), отмените список на 1level.

3) lapply(..., function(x) c(sorted[1L], x, sorted[length(sorted)])) добавляет первый и последний элемент к каждой комбинации

Выход 

[[1]]
[1]  1 25

[[2]]
[1]  1  4 25

[[3]]
[1]  1  2 25

[[4]]
[1]  1 12 25

[[5]]
[1]  1  6 25

[[6]]
[1]  1  5 25

[[7]]
[1]  1  4  2 25

[[8]]
[1]  1  4 12 25

[[9]]
[1]  1  4  6 25

[[10]]
[1]  1  4  5 25

[[11]]
[1]  1  2 12 25

[[12]]
[1]  1  2  6 25

[[13]]
[1]  1  2  5 25

[[14]]
[1]  1 12  6 25

[[15]]
[1]  1 12  5 25

[[16]]
[1]  1  6  5 25

[[17]]
[1]  1  4  2 12 25

[[18]]
[1]  1  4  2  6 25

[[19]]
[1]  1  4  2  5 25

[[20]]
[1]  1  4 12  6 25

[[21]]
[1]  1  4 12  5 25

[[22]]
[1]  1  4  6  5 25

[[23]]
[1]  1  2 12  6 25

[[24]]
[1]  1  2 12  5 25

[[25]]
[1]  1  2  6  5 25

[[26]]
[1]  1 12  6  5 25

[[27]]
[1]  1  4  2 12  6 25

[[28]]
[1]  1  4  2 12  5 25

[[29]]
[1]  1  4  2  6  5 25

[[30]]
[1]  1  4 12  6  5 25

[[31]]
[1]  1  2 12  6  5 25

[[32]]
[1]  1  4  2 12  6  5 25
...