在2D矩阵中排列数字1 [英] Arranging the number 1 in a 2d matrix

问题描述

给出二维矩阵的行数和列数

最初，矩阵的所有元素均为0

给出每行应显示的1的数量

给出每列中应显示的1的数量

确定是否可以形成这样的矩阵.

示例:

Input: r=3 c=2 (no. of rows and columns)
2 1 0 (number of 1's that should be present in each row respectively)
1 2 (number of 1's that should be present in each column respectively)

输出:可能

说明:

1 1
0 1
0 0

我尝试通过检查Ri的总和= Ci的总和来解决这个问题，大约12个小时

但是我想知道对于

这样的情况是否不可能

3 3
1 3 0
0 2 2

r和c最高为10 ^ 5

有什么想法我应该进一步发展吗?

添加的约束和输出只能是可能"或不可能".可能的矩阵不需要显示.

现在有人可以帮我吗?

解决方案

我将通过一个示例来说明该算法.

假设我们有m行和n列.令rows[i]为0 <= i < m行中的i行中的1的数目， cols[j]是0 <= j < n列在j列中的1的数目.

例如，对于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的1系列，一个长度为2的一系列1和一个长度为1的一系列1，它们将分布在数组的各行之间.我们重写cols来捕获COLS = {2/3 1/2 1/1}，即长度2的2系列，长度2的1系列和长度1的1系列.

因为我们有2个序列，长度为3，所以只有在第一行中可以放入两个1时，解决方案才存在.这是可能的，因为rows[0] = 2.我们实际上没有在第一行中放置任何1，而是通过减少长度为3的序列的长度来记录将1放置在其中的事实.因此COLS变为:

COLS = {2/2 1/2 1/1}

，我们将两个用于长度2系列的计数相结合，得出:

COLS = {3/2 1/1}

我们现在有了减少的问题:

3 | 1 1 1 0
4 | 1 1 1 1

同样，我们需要从长度为2的序列中放入1s来解决.幸运的是，rows[1] = 3，我们可以做到这一点.我们减小3/2的长度并得到:

COLS = {3/1 1/1} = {4/1}

我们有减少的问题:

4 | 1 1 1 1

这是由长度为1的4个系列解决的，这就是我们剩下的.如果在任何步骤上COLS中的序列都不能用于满足行数，则无法解决.

每行的一般处理可以描述如下.对于每行r，从COLS中的第一个元素开始，根据需要递减COLS的许多元素count[k]/length[k]的长度，以使count[k]的总和等于rows[r].在COLS中消除长度为0的序列，并组合相同长度的序列.

请注意，由于COLS的元素按长度的降序排列，因此最后一个元素的长度减小后的长度始终小于或等于COLS中的下一个元素(如果存在下一个元素).

示例2:存在解决方案.

rows = {1 3 3}, cols = {2 2 2 1} => COLS = {3/2 1/1}

长度2的1个序列递减以满足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，我们最多需要迭代一次 COLS的rows[i] <= n个元素.时间复杂度是O(m x n).

找到此算法后，我发现以下定理:

Havel-Hakimi定理(Havel 1955，Hakimi 1962)指出存在一个矩阵X 为0和1，行总和为a ₀ =( a ₁ ，a ₂ ，…，a _n )和列总计b ₀ =(b ₁ ，b ₂ ，…，b _m )，使得b _i ≥b _{i + 1} 每0<我<当且仅当具有行的0和1的另一个矩阵X _n-1，m 总计a ₁ =(a ₂ ，a ₃ ，...，a _n )和列总计b ₁ =(b ₁ −1，b ₂ −1，...，b _a1 −1，b _{a1 + 1} ，...，b _m )也存在. /p>

来自帖子查找二进制矩阵给定行和列之和存在.

这基本上是我的算法所做的，同时尝试优化递减部分，即上述定理中的所有 -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;
    }
}

Given the number of rows and columns of a 2d matrix

Initially all elements of matrix are 0

Given the number of 1's that should be present in each row

Given the number of 1's that should be present in each column

Determine if it is possible to form such matrix.

Example:

Input: r=3 c=2 (no. of rows and columns)
2 1 0 (number of 1's that should be present in each row respectively)
1 2 (number of 1's that should be present in each column respectively)

Output: Possible

Explanation:

1 1
0 1
0 0

I tried solving this problem for like 12 hours by checking if summation of Ri = summation of Ci

But I wondered if wouldn't be possible for cases like

3 3
1 3 0
0 2 2

r and c can be upto 10^5

Any ideas how should I move further?

Edit: Constraints added and output should only be "possible" or "impossible". The possible matrix need not be displayed.

Can anyone help me now?

解决方案

I will illustrate the algorithm with an example.

Assume we have m rows and n columns. Let rows[i] be the number of 1s in row i, for 0 <= i < m, and cols[j] be the number of 1s in column j, for 0 <= j < n.

For example, for m = 3, and n = 4, we could have: rows = {4 2 3}, cols = {1 3 2 3}, and the solution array would be:

    1 3 2 3
  +--------
4 | 1 1 1 1
2 | 0 1 0 1
3 | 0 1 1 1

Because we only want to know whether a solution exists, the values in rows and cols may be permuted in any order. The solution of each permutation is just a permutation of the rows and columns of the above solution.

So, given rows and cols, sort cols in decreasing order, and rows in increasing order. For our example, we have cols = {3 3 2 1} and rows = {2 3 4}, and the equivalent problem.

    3 3 2 1
  +--------
2 | 1 1 0 0
3 | 1 1 1 0
4 | 1 1 1 1

We transform cols into a form that is better suited for the algorithm. What cols tells us is that we have two series of 1s of length 3, one series of 1s of length 2, and one series of 1s of length 1, that are to be distributed among the rows of the array. We rewrite cols to capture just that, that is COLS = {2/3 1/2 1/1}, 2 series of length 3, 1 series of length 2, and 1 series of length 1.

Because we have 2 series of length 3, a solution exists only if we can put two 1s in the first row. This is possible because rows[0] = 2. We do not actually put any 1 in the first row, but record the fact that 1s have been placed there by decrementing the length of the series of length 3. So COLS becomes:

COLS = {2/2 1/2 1/1}

and we combine our two counts for series of length 2, yielding:

COLS = {3/2 1/1}

We now have the reduced problem:

3 | 1 1 1 0
4 | 1 1 1 1

Again we need to place 1s from our series of length 2 to have a solution. Fortunately, rows[1] = 3 and we can do this. We decrement the length of 3/2 and get:

COLS = {3/1 1/1} = {4/1}

We have the reduced problem:

4 | 1 1 1 1

Which is solved by 4 series of length 1, just what we have left. If at any step, the series in COLS cannot be used to satisfy a row count, then no solution is possible.

The general processing for each row may be stated as follows. For each row r, starting from the first element in COLS, decrement the lengths of as many elements count[k]/length[k] of COLS as needed, so that the sum of the count[k]'s equals rows[r]. Eliminate series of length 0 in COLS and combine series of same length.

Note that because elements of COLS are in decreasing order of lengths, the length of the last element decremented is always less than or equal to the next element in COLS (if there is a next element).

EXAMPLE 2 : Solution exists.

rows = {1 3 3}, cols = {2 2 2 1} => COLS = {3/2 1/1}

1 series of length 2 is decremented to satisfy rows[0] = 1, and the 2 other series of length 2 remains at length 2.

rows[0] = 1
COLS = {2/2 1/1 1/1} = {2/2 2/1}

The 2 series of length 2 are decremented, and 1 of the series of length 1. The series whose length has become 0 is deleted, and the series of length 1 are combined.

rows[1] = 3
COLS = {2/1 1/0 1/1} = {2/1 1/1} = {3/1}

A solution exists for rows[2] can be satisfied.

rows[2] = 3
COLS = {3/0} = {}

EXAMPLE 3: Solution does not exists.

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.

SPACE COMPLEXITY

It is easy to see that it is O(m + n).

TIME COMPLEXITY

We iterate over each row only once. For each row i, we need to iterate over at most rows[i] <= n elements of COLS. Time complexity is O(m x n).

After finding this algorithm, I found the following theorem:

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.

from the post Finding if binary matrix exists given the row and column sums.

This is basically what my algorithm does, while trying to optimize the decrementing part, i.e., all the -1's in the above theorem. Now that I see the above theorem, I know my algorithm is correct. Nevertheless, I checked the correctness of my algorithm by comparing it with a brute-force algorithm for arrays of up to 50 cells.

Here is the C# implementation.

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

这篇关于在2D矩阵中排列数字1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！