c# - 如何编写按行和按列排序的二进制矩阵/数组？

Question

我正在尝试编写一个生成 MxN 二进制二维数组的迭代器，如下所示:

1 1 1 1 1 1 0 0
1 1 1 1 0 0 1 1
1 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1

如果我们将每一行都视为二进制，例如11111100，每行从大到小排序。

如果我们将每一列视为二进制，例如1110，每列从大到小排序。

0 的个数 Z 是固定的。

iterator.Next() 应该是这个:

1 1 1 1 1 1 0 0
1 1 1 1 0 0 1 1
1 1 0 0 1 1 1 1
1 0 1 0 1 1 1 1

M,N,Z 可以是任何合理的值。

问题是如果我迭代每一行，就很难照顾每一列，反之亦然。

还应考虑时间复杂度。

Answer 1

这是我的第一个镜头，GetPossibleLines() 方法的性能不是很好。但是，如果您解决了第二个问题，则它会自行解决:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Possible combinations with m=8, z=2");

        var possibleLines = GetPossibleLines(8, 2).ToArray();
        for (int i = 0; i < possibleLines.Length; i++)
        {
            for (int j = 0; j < possibleLines[i].Length; j++)
            {
                Console.Write(possibleLines[i][j] ? 1 : 0);
            }
            Console.WriteLine();
        }
        Console.WriteLine("------------------------------");
        Console.WriteLine("And the Matrices:");

        foreach (var matrix in GetMatrices(8,5,2))
        {
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    Console.Write(matrix[i][j] ? 1 : 0);
                }
                Console.WriteLine();
            }

            Console.WriteLine("------------------------------------");
        }

        Console.WriteLine("---------------End------------------");

    }

    private static IEnumerable<bool[][]> GetMatrices(int m, int n, int z)
    {
        var possibleLines = GetPossibleLines(m, z).ToArray();

        var lineCombinations = GetPossibleLines(possibleLines.Length, n).ToArray();
        for (int i = 0; i < lineCombinations.Length; i++)
        {
            int combinationIndex = 0;
            bool[][] result = new bool[n][];
            for (int j = 0; j < lineCombinations[i].Length; j++)
            {
                if (!lineCombinations[i][j])
                {
                    result[combinationIndex++]= possibleLines[j];
                }
            }
            yield return result;

        }
    }

    private static IEnumerable<bool[]> GetPossibleLines(int m, int z)
    {
        for (int i = 1; i < Math.Pow(2, m); i++)
        {
            var remainder = i;
            var remainingZ = z;
            bool[] result = new bool[m];
            for (int j = 0; j < m && remainingZ > -1; j++)
            {
                bool b = remainder % 2 == 1;
                result[j] = b;
                remainder /= 2;
                if (!b)
                {
                    remainingZ--;
                }
            }
            if (remainder == 0 && remainingZ == 0)
            {
                yield return result;
            }
        }
    }
}