Поиск неповторяющихся значений

#математика #r

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



То, что зеленое - нужно вывести индексы. 
То, что красное - не нужно.

Необходимый ответ: 

1-4; 2-1; 3-6; 4-2; 5-7; 6-3; 7-5


Получилось добиться лишь такого:which(tabl_w==0, arr.ind = T)

      row col
 [1,]   2   1
 [2,]   4   1
 [3,]   5   1
 [4,]   6   1
 [5,]   2   2
 [6,]   4   2
 [7,]   6   3
 [8,]   1   4
 [9,]   7   4
[10,]   7   5
[11,]   3   6
[12,]   1   7
[13,]   5   7


А как дальше выбрать индексы, я не знаю.

В итоге получилось сделать:

zero_index <- which(tabl_w==0, arr.ind = T)

choose_unique_zero <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){
  zero_temp <- x[(!x[,1] %in% i) & (!x[,2] %in% j),]
  if(length(zero_temp)>2){
    i <- c(i,as.vector(zero_temp[1,1]))
    j <- c(j,as.vector(zero_temp[1,2]))
    index <- rbind(index,setNames(as.list(zero_temp[1,]), names(index)))
    choose_unique_zero(zero_temp,i,j,index)}
  else
    rbind(index,zero_temp)
}

unique_index <- choose_unique_zero(zero_index)


Спасибо всем огромное кто отозвался на мой вопрос!
    

Ответы

Ответ 1

Раз уж вопрос изначально был с тэгом r, то привожу решение с использованием R. Логика
решения аналогична коду на PHP.

find_ind_r <- function(x, value = 0L) {
  # Опередляем индексы
  idx <- which(x == value, arr.ind = TRUE)
  # Выделяем результирующий объект
  res <- list(
    row = rep(NA_integer_, nrow(x)),
    col = rep(NA_integer_, ncol(x))
  )
  # Счётчик
  count <- 1L
  # Считаем не повторяющиейся индексы
  for (i in seq_len(nrow(idx))) {
    r <- idx[i, ]
    if (!(r[1] %in% res$row) && !(r[2] %in% res$col)) {
      res$row[count] <- r[1]
      res$col[count] <- r[2]
      count <- count + 1L
    }
  }
  # Убираем незаполненные элементы
  length(res$row) <- count - 1L
  length(res$col) <- count - 1L
  return(res)
}


Если предполагается работа с большими массивами и требуется высокая производительность,
то лучше реализовать алгоритм на C++. Ниже приведено решение с использованием Rcpp.

Файл test.cpp:

#include 
using namespace Rcpp;

// [[Rcpp::export]]
List find_ind_cpp(const NumericMatrix & x, double value) {
  std::size_t ncols = x.ncol(), nrows = x.nrow();

  typedef std::unordered_set ind_set;
  ind_set rows, cols;
  ind_set::iterator rows_end = rows.end(), cols_end = cols.end();

  for (std::size_t i = 0; i < nrows; ++i) {
    for (std::size_t j = 0; j < ncols; ++j) {
      if (x[i + nrows * j] == value) {
        if (rows.find(i + 1) == rows_end && cols.find(j + 1) == cols_end) {
          rows.insert(i + 1);
          cols.insert(j + 1);
        }
      }
    }
  }
  List res = List::create(rows, cols);
  res.attr("names") = CharacterVector::create("rows", "cols");

  return res;
}


Выполняется в R-сессии или скрипте:

x <- c(4,6,3,0,1,5,0,
       0,0,4,3,3,1,12,
       8,1,3,3,3,0,2,
       0,0,10,5,3,5,12,
       0,2,9,8,9,13,0,
       0,15,0,1,2,6,10,
       2,4,6,0,0,12,1)
m <- matrix(x, nrow = 7, ncol = 7, byrow = TRUE)
Rcpp::sourceCpp("/tmp/test.cpp")
res <- find_ind_r(m, 0)
paste(res$row, res$col, sep = "-", collapse = "; ")
#> [1] "2-1; 4-2; 6-3; 1-4; 7-5; 3-6; 5-7"


Небольшой бенчмарк:

set.seed(42)

create_mat <- function(n) {
  matrix(sample(0:15, size = n * n, replace = TRUE), nrow = n, ncol = n)
}

res <- bench::press(
  n = c(10, 100, 1000),
  {
    mat <- create_mat(n)
    value <- 0
    bench:::mark(
      min_iterations = 100,
      find_ind_cpp(mat, value),
      find_ind_r(mat, value),
      check = FALSE
    )
  }
)

plot(res)


Ответ 2

Вроде это решает ваш вопрос:

 $arr_1) {

            foreach ($arr_1 as $key_2 => $val) {

                $v_tmp++;

                if ($val == 0 && !in_array($v_tmp, $v) && !in_array($h_tmp, $h)) {
                    $h[] = $h_tmp;
                    $v[] = $v_tmp;
                    $result[] = array('key1' => $key_1, 'key2' => $key_2);
                }

            }
            $v_tmp = 0;

            $h_tmp++;


        }

    var_dump($result);
?>


Однако начальные индексы тут начинаются с 0. Вы писали правильные ответы 1-4; 2-1,
но на деле будет 0-3; 1-0.

Если вам нужно именно 1-4, то просто сделайте инкремент тут:

$result[] = array('key1' => $key_1+1, 'key2' => $key_2+1);


Наш результат:

Array
(
    [0] => Array
        (
            [key1] => 0
            [key2] => 3
        )

    [1] => Array
        (
            [key1] => 1
            [key2] => 0
        )

    [2] => Array
        (
            [key1] => 2
            [key2] => 5
        )

    [3] => Array
        (
            [key1] => 3
            [key2] => 1
        )

    [4] => Array
        (
            [key1] => 4
            [key2] => 6
        )

    [5] => Array
        (
            [key1] => 5
            [key2] => 2
        )

    [6] => Array
        (
            [key1] => 6
            [key2] => 4
        )

)


Ответ 3

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

Более того, можно вообще взять только один, первый попавшийся ноль и на этом остановиться.
Условию задачи это удовлетворяет.

По-видимому, требуется найти наибольший набор нулей, удовлетворяющих данному требованию.
В идеале - в количестве, равном размеру квадратной матрицы (если она всегда квадратна).
Именно это вы, возможно, и хотели показать своим "то, что зеленое".

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

Для решения этой задачи в двудольном графе существуют эффективные алгоритмы (Хопкрофт-Карп,
например).