0

使用 JAVA，我需要读取一个包含 n x n 表的文本文件，如下所示（尽管大小可能会有所不同）：

0110
1000
1001
0010

假设 n 是人数。该表描述了一个人（行）和另一个人（列）之间的关系。如果表值为1，则两者是朋友；如果为 0，则他们不是朋友。例如，(0,1) 为 1；因此，1 和 2 是朋友。我需要从给定数量的字母（在此特定表的情况下：2）中为表中的每个人分配一个字母。如果两个人是朋友，他们必须收到不同的信。人们不被视为自己的朋友。使用递归回溯我需要找到这个难题的解决方案并将其打印出来或确定没有解决方案是可能的。

编辑：除非在表格中明确说明，否则朋友的朋友不被视为朋友。例如，在这个表中，1 是 2 和 3 的朋友；但是 2 和 3 不是朋友。1和3是朋友，3和4是朋友，但1和4不是朋友。我还应该注意，我在这里的编号是自然的，而实际上表索引从 0 开始。

我不知道从哪里开始解决这个问题。我确实意识到桌子有一条从 (0,0) 到 (n,n) 的对称线，因为如果 (1,2) 是朋友 (2,1) 也是朋友，因此没有人是他们自己的朋友（ n,n) 将始终为 0。

编辑：为了直观地显示它，在我看来，解决问题只需要粗体信息。

0 110
10 00
100 1
0010

总是将字母 A 分配给第 1 个人似乎是合理的，然后查看行并将不同的字母分配给值为 1 的位置。我不确定如何准确地执行此操作，也没有必要分配 2 和 3 不同此时的字母（回溯将在稍后处理）。

编辑：我可以使用以下内容为一个人分配一个随机数（稍后将转换为一个字母）。然后可以将该号码添加到排除列表中，该列表将排除这些号码分配给具有值 1 的行中的人（朋友）。

public static int getRandomWithExclusion(Random rnd, int start, int end, List<Integer> exclude) {
    int random = start + rnd.nextInt(end - start + 1 - exclude.size());
    for (int ex : exclude) {
        if (random < ex) {
            break;
        }
        random++;
    }
    return random;

编辑：

到目前为止我有这个代码；但是，我似乎无法找到如何使用回溯来做到这一点。另外，我不确定这是否适用于更大的桌子。在我看来，我需要修改我的排除实现。

    public static void assignLetter(int[][] table, int number_of_letters) {
    int[] assignments = new int[table.length];
    Random rnd = new Random();
    List<Integer> exclude = new ArrayList<>();
    // Person 1 is always assigned 1
    assignments[0]= 1;
    // Add 1 to exclusion list
    exclude.add(1);
    int row;
    int col;
    int nextAssignment;

    // Loop through each row
    for(row = 0; row <= table.length; row++) {
        //Loop through each column in each row
        for (col = row + 1; col < table.length; col++) {
            // If column value in row 1 equals 1, assigned number cannot be 1
            if (table[row][col] == 1) {
                // Generate random number within parameters excluding 1
                nextAssignment = getRandomWithExclusion(rnd, 1, number_of_letters, exclude);
                assignments[col] = nextAssignment;
            }
            // If column value in row 1 equals 0, assign person any number within parameters
            if (table[row][col] == 0 && row == 0) {
                // Generate random number within parameters, no exclusions
                nextAssignment = rnd.nextInt(number_of_letters) + 1;
                assignments[col] = nextAssignment;
            }
            // If a value in a subsequent row is 1 and the corresponding assignments are equal,
            // the assignments must be altered per the specifications
            if (table[row][col] == 1 && row > 0 && assignments[row] == assignments[col]) {
                // If the exclude list is equal to the number of letters, there is no solution
                if (exclude.size() == number_of_letters) {
                    System.out.println("There is no solution");
                }
                // If the value in row 1 of the table is not 1, it can be assigned 1
                if (table[0][col] != 1) {
                    nextAssignment = 1;
                    assignments[col] = nextAssignment;
                }
            }
        }
    }
    for (int i = 0; i < assignments.length; i++) {
        int person = i + 1;
        int letterNum = assignments[i];
        char[] alphaArray = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
                'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
        char letter = alphaArray[letterNum-1];
        System.out.println(person + " : " + letter);
    }
}

你有什么建议可以帮助我走上正确的道路吗？

谢谢！

4

0 回答 0