c++ - 在不违反约束的情况下生成整数数组

Question

我为一个问题苦苦挣扎了几个小时。这是一个约束满足问题。让我用一个简单的例子来描述它:

假设有一个长度为 8 的整数数组。每个单元格都可以取特定的值。前 4 个单元格可以取 0、1 或 2，另一半可以取 0 或 1。这 3 个数组可以作为一些示例。

{2,1,0,2,1,1,0,1}
{2,2,1,0,0,1,0,0}
{0,0,0,2,0,0,0,1}

但是构造数组有一些限制，如下所示:

constraint1 = {1,-,-,-,-,1,-,-}  // !(cell2=1 && cell6=1) cell2 and cell6 can not be in these format. 
constraint2 = {0,-,-,-,-,-,-,0}  // !(cell1=0 && cell8=0)
constraint3 = {-,-,-,2,1,1,-,-}  // !(cell4=2 && cell5=1 && cell6=1)
constraint4 = {1,1,-,-,-,-,-,-}  // !(cell1=1 && cell2=1)

为了更好的理解；

{0,1,1,2,0,1,0,0}  // this is not valid, because it violates the constraint2
{1,1,2,2,1,1,0,1}  // this is not valid, because it violates the constraint3 and constraint4
{1,1,0,0,0,1,0,0}  // this is not valid, because it violates the constraint4

我需要生成一个不违反任何给定约束的整数数组。

在我的方法中；

1) Create an array (called myArray) and initialize every cell to -1
2) Count the number of cells which are used in constraints. Above example, cell1 is used 3 times, cell2 is used 1 time, cell3 is not used, so on so forth.
3) Choose the cell which is used more in constraints (it is cell1, used 3 times)
4) Find the distribution of numbers in this cell. (In cell1, 1 is used 2 times and 0 is used 1 time)
5) Change this chosen cell in myArray to the number which is used less. (In cell1, since 0 is used less than 1, cell1 in myArray will be 0) 
6) Delete all the constraints from the list which has 1 or 2 in their cell1.
7) Go to step 2 and do same steps until all constraints are eliminated

该算法的思想是以消除更多约束的方式选择单元格及其值。

但是，当约束数量较多时，此算法不起作用。

重要提示:这只是一个简单的例子。在正常情况下，数组的长度更长(平均为 100)并且约束的数量更多(超过 200)。我的输入是数组的长度、N 个约束和每个单元格可以取的值。

有没有人有更好的办法来解决这个问题？

Answer 1

这是我用 C# 编写的代码，用于生成随机矩阵，然后删除矩阵中的约束。

class Program
{
    static void Main(string[] args)
    {

        int[] inputData = new int[4] { 3, 7, 3, 3 };
        int matrixRowSize = 6;

        /////////////////////////// Constraints 

        int []constraint1 = new int[4] { 1, -1, -1, 2}; // here is the constaint that i want to remove.
        // note the constaints could be more than 1, so there could be a generic method

        Random r = new Random();
        int[,] Random_matrix = new int[matrixRowSize, inputData.Length];
        ///////////// generate random matrix 
        for (int i = 0; i < inputData.Length; i++)
        {
            for (int j = 0; j < matrixRowSize; j++)
            {       
                int k = r.Next(0, inputData[i]);  


                Random_matrix[j, i] = k;
            }
        }