java - 检查集合是否对称的有效方法

Question

我需要编写一个 validator 来检查使用 Gson 从 JSON 解析的房间，对于每一对房间 A 和 B，如果你可以从 A 到 B，那么你就可以从 B 到 A。

JSON 的格式如下: https://jsfiddle.net/tgtbqzky/

{
  "initialRoom": "MatthewsStreet",
  "rooms": [
    {
      "name": "MatthewsStreet",
      "description": "You are on Matthews, outside the Siebel Center",
      "directions": [
        {
          "direction": "East",
          "room": "SiebelEntry"
        }
      ]
    },
    {
      "name": "SiebelEntry",
      "description": "You are in the west entry of Siebel Center.  You can see the elevator, the ACM office, and hallways to the north and east.",
      "directions": [
        {
          "direction": "West",
          "room": "MatthewsStreet"
        },
        {
          "direction": "Northeast",
          "room": "AcmOffice"
        },
        {
          "direction": "North",
          "room": "SiebelNorthHallway"
        },
        {
          "direction": "East",
          "room": "SiebelEastHallway"
        }
      ]
    },
    {
      "name": "AcmOffice",
      "description": "You are in the ACM office.  There are lots of friendly ACM people.",
      "directions": [
        {
          "direction": "South",
          "room": "SiebelEntry"
        }
      ]
    },
    {
      "name": "SiebelNorthHallway",
      "description": "You are in the north hallway.  You can see Siebel 1112 and the door toward NCSA.",
      "directions": [
        {
          "direction": "South",
          "room": "SiebelEntry"
        }, 
        {
          "direction": "NorthEast",
          "room": "Siebel1112"
        }
      ]
    },
    {
      "name": "Siebel1112",
      "description": "You are in Siebel 1112.  There is space for two code reviews in this room.",
      "directions": [
        {
          "direction": "West",
          "room": "SiebelNorthHallway"
        }
      ]
    },
    {
      "name": "SiebelEastHallway",
      "description": "You are in the east hallway.  You can see Einstein Bros' Bagels and a stairway.",
      "directions": [
        {
          "direction": "West",
          "room": "SiebelEntry"
        },
        {
          "direction": "South",
          "room": "Siebel1314"
        },
        {
          "direction": "Down",
          "room": "SiebelBasement"
        }
      ]
    },
    {
      "name": "Siebel1314",
      "description": "You are in Siebel 1314.  There are happy CS 126 students doing a code review.",
      "directions": [
        {
          "direction": "North",
          "room": "SiebelEastHallway"
        }
      ]
    },
    {
      "name": "SiebelBasement",
      "description": "You are in the basement of Siebel.  You see tables with students working and door to computer labs.",
      "directions": [
        {
          "direction": "Up",
          "room": "SiebelEastHallway"
        }
      ]
    }
  ]
}

我想知道要走的路是否是两个嵌套的 for 循环，其中外层的 for 循环将遍历所有房间，内层的 for 循环将遍历每个循环内的每个可能的方向，然后我将添加每一对我进入一个 ArrayList。

如果我遇到一些已经存在的东西，我会将它从 ArrayList 中删除，如果在我的 for 循环结束时，ArrayList 仍然包含一个元素，这意味着它对应的对不存在，因此JSON 无效。如果 ArrayList 的大小为零，则数据有效。

有没有人有更有效的方法来解决这个问题？我觉得既然它本质上是在证明一个给定的集合是否是对称的，那么一定有一个更优化的方法。

Answer 1

您应该能够通过定义一对房间的“规范名称”来验证集合的对称性，例如，按字母顺序对房间名称进行排序，并将所有房间对映射到它们的规范名称:

static String canonicalName(String roomA, String roomB) {
    if (roomA.compareTo(roomB) < 0) {
        return roomA + "|" + roomB;
    } else {
        return roomB + "|" + roomA;
    }
}

这将为一对房间生成相同的 key "AcmOffice|MatthewsStreet"，其中一个是 "AcmOffice"，另一个是 “MatthewsStreet”，无论顺序如何。

现在您可以将它们映射到列表，如下所示:

Map<String,List<String>> mp = new HashMap<>();
for (PairOfRooms pair : allRoomPairs) {
    String key = canonicalName(pair.roomA, pair.roomB);
    List<String> list = mp.get(key);
    if (list == null) {
        list = new ArrayList<>();
        mp.put(key, list);
    }
    list.add(pair.roomA + "|" + pair.roomB);
}

遍历所有对后，检查 map 中的列表:

• 如果一个列表有两个不同的项目，一切都很好
• 如果列表只有一项，则其对称项缺失
• 如果列表有两个以上的项目，则有重复项