在给定行和列总和的情况下查找二进制矩阵是否存在 [英] Finding if binary matrix exists given the row and column sums

问题描述

如何确定是否可以构造具有给定行和列总和的二进制矩阵.

How to find out if it is possible to contruct a binary matrix with given row and column sums.

输入:

输入的第一行包含两个数字1≤m，n≤1000，即矩阵的行数和列数.下一行包含m个数字0≤ri≤n–矩阵中每一行的总和.第三行包含n个数字0≤cj≤m–矩阵中每一列的总和.

The first row of input contains two numbers 1≤m,n≤1000, the number of rows and columns of the matrix. The next row contains m numbers 0≤ri≤n – the sum of each row in the matrix. The third row contains n numbers 0≤cj≤m – the sum of each column in the matrix.

输出:

如果存在一个m×n矩阵A(每个元素为0或1)，则输出"YES".否则为"NO".

Output "YES" if there exists an m-by-n matrix A, with each element either being 0 or 1. Else "NO".

我试图阅读有关层析成像算法的文章，但由于与层析成像算法有关的所有论文都非常复杂，因此无法找到答案.

I tried reading about Tomography algorithms but could not figure out an answer as all the papers related to Tomography algorithm is very complicated.

有人可以帮我吗?.

推荐答案

我已经成功实现了使用基于在场—不在场矩阵的随机化:评论和新算法米克洛斯(Miklós)和波达尼(Podani):

I've successfully implemented randomly generating such matrices for R using a modeling based on network flow. I intend to write up those ideas one day, but haven't found the time yet. Reasearching for that, I read in Randomization of Presence–absence Matrices: Comments and New Algorithms by Miklós and Podani:

Havel - Havel 1955 ， Hakimi 1962 )指出存在一个矩阵 X _n，m 为0和1，行总计为 a ₀ =( a ₁ ， a ₂ ，…， a _n )和列总计 b ₀ =( b ₁ ， b ₂ ，…， b _m )，这样 b _i ≥ b _{i +1} ，每0< i < m 当且仅当另一个矩阵 X _{n −1， m} 为0和1的行总计 a ₁ =( a ₂ ， a ₃ ，…， a _n )，列总计为 b ₁ =( b ₁ −1， b ₂ −1，…， b _{a 1} -1， b _{a 1 +1} ，…， b _m )也存在.

The Havel-Hakimi theorem (Havel 1955, Hakimi 1962) states that there exists a matrix X_n,m of 0’s and 1’s with row totals a₀=(a₁, a₂,… , a_n) and column totals b₀=(b₁, b₂,… , b_m) such that b_i ≥ b_i+1 for every 0 < i < m if and only if another matrix X_n−1,m of 0’s and 1’s with row totals a₁=(a₂, a₃,… , a_n) and column totals b₁=(b₁−1, b₂−1,… ,b_a1−1, b_a1+1,… , b_m) also exists.

我想这应该是递归确定问题的最佳方法.

I guess that should be the best method to recursively decide your question.

用我自己的话来说:选择任意行，将其从总计列表中删除.呼叫删除的号码 k .还要从 k 列中减去一个大和.您可以获得一个较小矩阵的描述，然后递归.如果在任何时候您都没有 k 列的总和不为零，那么就不会存在这样的矩阵.否则，您可以使用相反的过程来递归地建立一个匹配矩阵:取递归调用返回的矩阵，然后再添加一个带有 k 个行，并排在您最初从中减去一列的列中.

Phrased in my own words: Choose any row, remove it from the list of totals. Call that removed number k. Also subtract one from the k columns with larges sums. You obtain a description of a smaller matrix, and recurse. If at any point you don't have k columns with non-zero sums, then no such matrix can exist. Otherwise you can recursively build a matching matrix using the reverse process: take the matrix returned by the recursive call, then add one more row with k ones, placed in the columns from whose counts you originally subtracted one.

bool satisfiable(std::vector<int> a, std::vector<int> b) {
  while (!a.empty()) {
    std::sort(b.begin(), b.end(), std::greater<int>());
    int k = a.back();
    a.pop_back();
    if (k > b.size()) return false;
    if (k == 0) continue;
    if (b[k - 1] == 0) return false;
    for (int i = 0; i < k; i++)
      b[i]--;
  }
  for (std::vector<int>::iterator i = b.begin(); i != b.end(); i++)
    if (*i != 0)
      return false;
  return true;
}

这篇关于在给定行和列总和的情况下查找二进制矩阵是否存在的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！