Я проиллюстрирую алгоритм на примере.
Предположим, у нас есть m строк и n столбцов.Пусть rows[i] будет номером 1 в строке i для 0 <= i < m, а cols[j] будет номером 1 в столбце j для 0 <= j < n.
Например, дляm = 3 и n = 4, мы могли бы иметь: rows = {4 2 3}, cols = {1 3 2 3}, и массив решений был бы:
1 3 2 3
+--------
4 | 1 1 1 1
2 | 0 1 0 1
3 | 0 1 1 1
Поскольку мы хотим знать только, существует ли решение, значенияв rows и cols могут быть переставлены в любом порядке.Решением каждой перестановки является просто перестановка строк и столбцов вышеприведенного решения.
Итак, с учетом rows и cols, сортировка cols по убыванию и rows по возрастаниюпорядок.Для нашего примера у нас есть cols = {3 3 2 1} и rows = {2 3 4} и эквивалентная проблема.
3 3 2 1
+--------
2 | 1 1 0 0
3 | 1 1 1 0
4 | 1 1 1 1
Мы преобразуем cols в форму, которая лучше подходит для алгоритма.Что нам говорит cols, так это то, что у нас есть две серии единиц длины 3, одна серия единиц длины 2 и одна серия единиц длины 1, которые должны быть распределены по строкам массива.Мы переписываем cols, чтобы захватить только это, то есть COLS = {2/3 1/2 1/1}, 2 серии длины 3, 1 серия длины 2 и 1 серия длины 1.
Поскольку у нас есть 2 серии длины 3,решение существует, только если мы можем поставить две 1 в первом ряду.Это возможно, потому что rows[0] = 2.На самом деле мы не ставим 1 в первый ряд, а записываем тот факт, что 1-е место было помещено, уменьшая длину ряда на длину 3. Таким образом, COLS становится:
COLS = {2/2 1/2 1/1}
, и мыскомбинируем два числа для серии длины 2, получив:
COLS = {3/2 1/1}
Теперь у нас есть уменьшенная задача:
3 | 1 1 1 0
4 | 1 1 1 1
Снова нам нужно поместить 1 из нашей серии длины 2 весть решение.К счастью, rows[1] = 3 и мы можем это сделать.Мы уменьшаем длину 3/2 и получаем:
COLS = {3/1 1/1} = {4/1}
У нас есть уменьшенная задача:
4 | 1 1 1 1
, которая решается 4 сериями длины 1, как раз то, что мы оставили,Если на каком-либо шаге ряд в COLS не может быть использован для удовлетворения количества строк, то решение невозможно.
Общая обработка каждой строки может быть сформулирована следующим образом.Для каждой строки r, начиная с первого элемента в COLS, уменьшите длину стольких элементов count[k]/length[k], сколько необходимо COLS, чтобы сумма count[k] равнялась rows[r].Исключить серии длины 0 в COLS и объединить серии одинаковой длины.
Обратите внимание, что поскольку элементы COLS расположены в порядке убывания длины, длина последнего уменьшенного элемента всегда меньше или равнак следующему элементу в COLS (если есть следующий элемент).
ПРИМЕР 2: Решение существует.
rows = {1 3 3}, cols = {2 2 2 1} => COLS = {3/2 1/1}
1 серия длины 2 уменьшена для удовлетворения rows[0] = 1, а 2 другие серии длины 2 остаются на длине 2.
rows[0] = 1
COLS = {2/2 1/1 1/1} = {2/2 2/1}
2 серии длины 2 уменьшаются, а 1 серии длины 1. Серия, длина которой стала 0, удаляется.и объединяются серии длины 1.
rows[1] = 3
COLS = {2/1 1/0 1/1} = {2/1 1/1} = {3/1}
Решение существует для rows[2]. Можно удовлетворить.
rows[2] = 3
COLS = {3/0} = {}
ПРИМЕР 3: Решение не существует.
rows = {0 2 3}, cols = {3 2 0 0} => COLS = {1/3 1/2}
rows[0] = 0
COLS = {1/3 1/2}
rows[1] = 2
COLS = {1/2 1/1}
rows[2] = 3 => impossible to satisfy; no solution.
ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ
Легко видеть, что это O(m + n).
СЛОЖНОСТЬ ВРЕМЕНИ
Мы повторяем по каждой строке только один раз.Для каждой строки i нам нужно перебрать не более rows[i] <= n элементов COLS.Временная сложность составляет O(m x n).
Найдя этот алгоритм, я нашел следующую теорему:
Теорема Гавела-Хакими (Havel 1955, Hakimi 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 n − 1, m из 0 и 1 с итоговыми значениями строки a 1 = (a 2 , a 3 , …, A n ) и итоги столбца b 1 = (b 1 -1, b 2 -1,…, b a1 -1, b a1 + 1 ,…, b m ) также существует.
из поста Поиск существования бинарной матрицы по сумме строк и столбцов .
Это в основном то, что делает мой алгоритм, пытаясь оптимизировать убывающую часть, то есть все -1 в приведенной выше теореме. Теперь, когда я вижу приведенную выше теорему, я знаю, что мой алгоритм правильный. Тем не менее я проверил правильность своего алгоритма, сравнив его с алгоритмом грубой силы для массивов до 50 ячеек.
Вот реализация C #.
public class Pair
{
public int Count;
public int Length;
}
public class PairsList
{
public LinkedList<Pair> Pairs;
public int TotalCount;
}
class Program
{
static void Main(string[] args)
{
int[] rows = new int[] { 0, 0, 1, 1, 2, 2 };
int[] cols = new int[] { 2, 2, 0 };
bool success = Solve(cols, rows);
}
static bool Solve(int[] cols, int[] rows)
{
PairsList pairs = new PairsList() { Pairs = new LinkedList<Pair>(), TotalCount = 0 };
FillAllPairs(pairs, cols);
for (int r = 0; r < rows.Length; r++)
{
if (rows[r] > 0)
{
if (pairs.TotalCount < rows[r])
return false;
if (pairs.Pairs.First != null && pairs.Pairs.First.Value.Length > rows.Length - r)
return false;
DecrementPairs(pairs, rows[r]);
}
}
return pairs.Pairs.Count == 0 || pairs.Pairs.Count == 1 && pairs.Pairs.First.Value.Length == 0;
}
static void DecrementPairs(PairsList pairs, int count)
{
LinkedListNode<Pair> pair = pairs.Pairs.First;
while (count > 0 && pair != null)
{
LinkedListNode<Pair> next = pair.Next;
if (pair.Value.Count == count)
{
pair.Value.Length--;
if (pair.Value.Length == 0)
{
pairs.Pairs.Remove(pair);
pairs.TotalCount -= count;
}
else if (pair.Next != null && pair.Next.Value.Length == pair.Value.Length)
{
pair.Value.Count += pair.Next.Value.Count;
pairs.Pairs.Remove(pair.Next);
next = pair;
}
count = 0;
}
else if (pair.Value.Count < count)
{
count -= pair.Value.Count;
pair.Value.Length--;
if (pair.Value.Length == 0)
{
pairs.Pairs.Remove(pair);
pairs.TotalCount -= pair.Value.Count;
}
else if(pair.Next != null && pair.Next.Value.Length == pair.Value.Length)
{
pair.Value.Count += pair.Next.Value.Count;
pairs.Pairs.Remove(pair.Next);
next = pair;
}
}
else // pair.Value.Count > count
{
Pair p = new Pair() { Count = count, Length = pair.Value.Length - 1 };
pair.Value.Count -= count;
if (p.Length > 0)
{
if (pair.Next != null && pair.Next.Value.Length == p.Length)
pair.Next.Value.Count += p.Count;
else
pairs.Pairs.AddAfter(pair, p);
}
else
pairs.TotalCount -= count;
count = 0;
}
pair = next;
}
}
static int FillAllPairs(PairsList pairs, int[] cols)
{
List<Pair> newPairs = new List<Pair>();
int c = 0;
while (c < cols.Length && cols[c] > 0)
{
int k = c++;
if (cols[k] > 0)
pairs.TotalCount++;
while (c < cols.Length && cols[c] == cols[k])
{
if (cols[k] > 0) pairs.TotalCount++;
c++;
}
newPairs.Add(new Pair() { Count = c - k, Length = cols[k] });
}
LinkedListNode<Pair> pair = pairs.Pairs.First;
foreach (Pair p in newPairs)
{
while (pair != null && p.Length < pair.Value.Length)
pair = pair.Next;
if (pair == null)
{
pairs.Pairs.AddLast(p);
}
else if (p.Length == pair.Value.Length)
{
pair.Value.Count += p.Count;
pair = pair.Next;
}
else // p.Length > pair.Value.Length
{
pairs.Pairs.AddBefore(pair, p);
}
}
return c;
}
}