Построение рандомизированной матрицы без дубликатов, но с фиксированным частичным вводом

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

Посмотрим:

матрица должна получиться 10 на 10

 n <- 10

Я хочу, чтобы мои первые строки были данными, которые я ввожу. например:

  row1<- c(1,4,7,6,5,3,2,8,9,10)
  row2<- c(10,7,3,2,1,4,5,9,8,6)
  row3<- c(9,2,4,3,8,7,10,1,6,5)

Чтобы построить матрицу с 10 строками (и 10 столбцами), я объединил эти строки с образцами (без замены, потому что я хочу, чтобы каждое число было уникальным в каждой строке).

 first.rows<-rbind(row1,row2,row3,sample(n,n,replace=F),sample(n,n,replace=F),sample(n,n,replace=F),sample(n,n,replace=F),sample(n,n,replace=F),sample(n,n,replace=F),sample(n,n,replace=F))

выход:

     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
row1    1    4    7    6    5    3    2    8    9    10
row2   10    7    3    2    1    4    5    9    8     6
row3    9    2    4    3    8    7   10    1    6     5
        6    1    5    4    2   10    3    8    7     9
        2    5    7    8    9    6    1    3    4    10
       10    6    4    1    8    3    7    2    5     9
        8    5    3    2    4    1   10    7    6     9
       10    7    9    6    8    2    5    4    3     1
        1   10    8    4    7    3    5    2    6     9
        2    1   10    4    8    9    3    6    5     7

Пока все хорошо.. Однако теперь у меня проблема, что нет контроля над уникальными числами в столбцах. Хотя это то, что мне нужно. Я понимаю, что это так, потому что я использовал rbind (и поэтому только функция отсутствия дубликатов работает только для строк). Но я не знаю, как еще подойти к этой проблеме. Ряды 1-3 должны остаться точно такими же, как сейчас.

Любые идеи?


r matrix backtracking recursive-backtracking
person shampoo    schedule 12.09.2017    source источник
comment
Что вы подразумеваете под отсутствием контроля уникальных чисел в столбцах?   -  person pogibas    schedule 13.09.2017
comment
Я хотел бы иметь уникальные значения в каждом столбце (например, в каждой строке). Однако с моим кодом я не могу это контролировать, т.е. на выходе есть дубликаты значений в каждом столбце.   -  person shampoo    schedule 13.09.2017
comment
о, вы имеете в виду, что в столбце 1 3 десятки, две единицы и т. д. И вы хотите, чтобы были только уникальные (одна 1, одна 2 и т. д.)?   -  person pogibas    schedule 13.09.2017
comment
Да, точно!!!   -  person shampoo    schedule 13.09.2017
comment
Пятый элемент в row3 такой же, как и пятый элемент в row1.. Если я вас правильно понял, это противоречит правилу, которое вы навязываете, не так ли?   -  person KenHBS    schedule 13.09.2017
comment
Также в третьем ряду две пятерки и нет восьмерок.   -  person KenHBS    schedule 13.09.2017
comment
Вы правы - произошла ошибка. Я исправил это сейчас.   -  person shampoo    schedule 13.09.2017
comment
Я думаю, что какой-то возврат назад, вероятно, лучший подход. Однако я не могу справиться..   -  person shampoo    schedule 13.09.2017
comment
Вам нужен решатель, мое решение вашего предыдущего связанного вопроса может быть изменено.   -  person Fernando    schedule 13.09.2017

Ответы (1)


arrow_upward
2
arrow_downward

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

# x is your matrix, "not filled" values should be NA
# x is a square matrix with dimension n (big n will take longer to converge)
backtrack = function(x){
  n = ncol(x)
  stopifnot(ncol(x)==nrow(x))

  cells = list()
  k = 1
  for (i in 1:n){
    for (j in 1:n){

      if (is.na(x[i, j]))
        cells[[k]] = sample(1:n)
      else
        cells[[k]] = NULL
      k = k + 1
    }
  }

  i = 0
  while (i < n*n){

    if (is.null(cells[[i+1]])){
        i=i+1
        next
    }

    candidates = cells[[i + 1]]
    idx = sample(1:length(candidates), 1)
    val = candidates[idx]

    if (length(candidates) == 0){
      cells[[i + 1]] = sample(1:n)
      i = i - 1
      x[as.integer(i/n) + 1,  i %% n + 1] = NA
    }
    else {
      rr = as.integer(i/n) + 1
      cc = i %% n + 1
      if ((val %in% x[rr, ]) || (val %in% x[, cc])){
        candidates = candidates[-idx]
        cells[[i + 1]] = candidates
      }
      else{
        x[as.integer(i/n) + 1, i %% n + 1] = val
        candidates = candidates[-idx]
        cells[[i + 1]] = candidates
        i = i + 1
      }
    }
  }
  x
}

Пустая исходная матрица

set.seed(1)
x = backtrack(matrix(NA, nrow = 10, ncol = 10))
print(x)
    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]    8   10    4    6    9    7    1    2    3     5
 [2,]    5    6    9    8    1   10    4    3    2     7
 [3,]   10    7    1    2    8    9    5    4    6     3
 [4,]    3    9    8   10    6    5    7    1    4     2
 [5,]    9    1    6    4    7    3    2    5   10     8
 [6,]    1    4   10    3    2    6    8    7    5     9
 [7,]    2    8    5    9   10    1    3    6    7     4
 [8,]    6    5    2    7    3    4   10    9    8     1
 [9,]    4    3    7    1    5    2    6    8    9    10
[10,]    7    2    3    5    4    8    9   10    1     6

Предварительно заполненная исходная матрица

m = matrix(NA, ncol = 10, nrow = 10)
m[1, ] = c(1,4,7,6,5,3,2,8,9,10)
m[2, ] = c(10,7,3,2,1,4,5,9,8,6)
m[3, ] = c(9,2,4,3,8,7,10,1,6,5)

x = backtrack(m)
print(x)
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]    1    4    7    6    5    3    2    8    9    10
 [2,]   10    7    3    2    1    4    5    9    8     6
 [3,]    9    2    4    3    8    7   10    1    6     5
 [4,]    5    9    6    8    3    2    4    7   10     1
 [5,]    7    1    5   10    9    6    3    2    4     8
 [6,]    2    5    8    1   10    9    6    3    7     4
 [7,]    6    3    1    4    7    5    8   10    2     9
 [8,]    8   10    9    5    4    1    7    6    3     2
 [9,]    3    6   10    9    2    8    1    4    5     7
[10,]    4    8    2    7    6   10    9    5    1     3

ПРИМЕЧАНИЕ. Я не проверял его на наличие ошибок.

person Fernando    schedule 13.09.2017
comment
Потрясающе @Фернандо!!! Большое спасибо!! Это именно то, что я искал!! - person shampoo; 13.09.2017