It is necessary to display the indices of zeros, but that in the row and in the column was not more than one value. This picture will tell better:

Solution example

The fact that green - need to display indexes. That red is not needed.

Required answer:

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

It turned out to achieve only this: 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

And how to continue to choose the indexes, I do not know.

The result was to do:

 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)

Thank you all very much who answered my question!

  • I do not know how to R, but would write something like: we start a collection to store the numbers of columns, it is empty. Cycle in rows. Inside the row we go in columns until we meet 0, and this column number should not be contained in the column collection. As soon as we find 0, we remember the number of the column in the collection and break the cycle of the row — go to the next. - Andrei NOP
  • From your formulation of the problem it is not at all clear whether it is necessary to maximize the number of such selected zeros, or you can simply type them at random as much as possible. An example of a bad one is given - not indicative - because in it a simple left-to-right scan from top to bottom randomly results in a sample of the maximum number of zeros. - AnT

3 answers 3

Since the question was originally with the r tag, then I provide a solution using R The logic of the solution is similar to the code in 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) }

If you intend to work with large arrays and require high performance, then it is better to implement an algorithm in C ++. The following is a solution using Rcpp .

test.cpp file:

 #include <Rcpp.h> 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<std::size_t> 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; }

Executed in an R session or script:

 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"

Small benchmark:

 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)

enter image description here

  • Thank you and decide for you. I got it done with R. :) - Belyaev_Al
  • It will be interesting to see if, of course, these are not two nested loops :) - Artem Klevtsov 1:51 pm
  • Yes, you are right in your question, add a separate subtitle (final solution, for example). - Artem Klevtsov 1:58 pm
  • Added by. Hopefully recursion in R works better than cycles - Belyaev_Al
  • My solution on R is a bit simpler (updated solution). I do not like recursion, because it is difficult to understand. it does not predictably use memory, plus dynamic typing. - Artem Klevtsov 2:21 pm

Like this solves your question:

 <?php $v = []; $h = []; $result = []; $array = [ [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] ]; $h_tmp = 0; $v_tmp = 0; foreach ($array as $key_1 => $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); ?>

However, the initial indices here start from 0. You wrote the correct answers 1-4; 2-1 , but in fact it will be 0-3; 1-0 .

If you need exactly 1-4, then just make an increment here:

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

Our result:

 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 ) )
  • I am not familiar with php at all, could you describe this moment in foreach ($ array as $ key_1 => $ arr_1) in some other language? It appeared difficulties in as $ key_1. - Belyaev_Al
  • Foreach function. In JavaScript for (var key_1 in array){ if (array.hasOwnProperty(key_1)) { alert("Key is " + key_1 + ", value is" + array[k]); } } for (var key_1 in array){ if (array.hasOwnProperty(key_1)) { alert("Key is " + key_1 + ", value is" + array[k]); } } - Perfecto Web
  • one
    Thank you very much! - Belyaev_Al 4:56 pm

The task is unclearly set. The optimality criterion has disappeared somewhere, if it ever existed. If the goal is only to get no more than one value in each row and each column, then the problem is trivial: just grab zeros at random and make sure that the "no more than one" requirement is met. Everything.

Moreover, you can generally take only one, the first zero and stop there. The condition of the problem is satisfied.

Apparently, it is required to find the largest set of zeros that satisfy this requirement. Ideally, in an amount equal to the size of the square matrix (if it is always square). That is what you might want to show your "what is green."

As such, it is a classic task of finding the Maximum Matching in a bichromatic graph. For each row of the matrix, a vertex is created in one part of the graph. For each column of the matrix, there is a vertex in a different part of the graph. Vertices are connected by an edge if the intersection of the corresponding row and column is zero.

To solve this problem in the bipartite graph, there are effective algorithms (Hopkroft-Karp, for example).