Как узнать, возможно ли построить двоичную матрицу с заданными суммами строк и столбцов - PullRequest
Новая
       32

Как узнать, возможно ли построить двоичную матрицу с заданными суммами строк и столбцов

0 голосов
/ 29 мая 2019

Как узнать, возможно ли построить двоичную матрицу с заданными суммами строк и столбцов.

Теорема Гавел - Хакими ( Гавел 1955 , Хакими 1962 ) утверждает, что существует матрица X n, m из 0 и 1с итогами строк a 0 = ( a 1 , a 2 ,…, a n ) и итоги столбцов b 0 = ( b 1 , b 2 ,…, b m ) таких, что b i ≥ b i + 1 для каждого 0 <<i> i <<i> m тогда и только тогда, когда другая матрица X n -1, m из 0 и 1 со строкойИтого a 1 = ( a 2 , a 3 ,…, a n ) и всего столбцаls b 1 = ( b 1 -1, b 2 -1,…, b a 1 -1, b a 1 + 1 ,…, b m ) также существует.

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

Выражено моими собственными словами: выберите любую строку, удалите ее из списка итогов.Позвоните на этот удаленный номер k .Также вычтите один из столбцов k с большими суммами.Вы получаете описание меньшей матрицы и рекурсивно.Если в какой-то момент у вас нет k столбцов с ненулевыми суммами, то такая матрица не может существовать.В противном случае вы можете рекурсивно построить соответствующую матрицу, используя обратный процесс: возьмите матрицу, возвращенную рекурсивным вызовом, затем добавьте еще одну строку с k , расположенными в столбцах, из которых вы изначально вычли одну.1143 *

Реализация 

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;
}

данный код кажется неправильным, поскольку в некоторых случаях он дает неправильный ответ

...