查找字符串 HashSet 的组合

Question

我有一个HashMap<String, HashSet>。 String 存储此人的姓名，HashSet 存储与此人成为好友的人员列表。

KEY<STRING>   VALUE<HASHSET>
Dave          Steve
Steve         Dave
Bob           Dalton
Dalton        Bob, Sue
Anne          Sue
Sue           Dalton, Anne

在上面的数据中，Dave 是 Steve 的朋友（第 1 行和第 2 行）。从第 4 行开始，Dalton 是 Bob 和 Sue 的朋友。但是，Bob 和 Sue 不一定是朋友。该程序需要输入 Bob 和 Sue 作为朋友。换言之，Bob 应该被添加到 Sue 的好友列表中，而 Sue 也应该被添加到 Bob 的好友列表中。然而，道尔顿的好友列表可能有无限多的人。我也不允许将朋友列表数据存储到 Array 或 ArrayList.

我正在考虑（但尚未尝试）的一个解决方案是编辑我的 read(String name1, String name2) 方法。 （注意：在我的runner class中，每当调用这个方法时，它被调用为read(name1, name2)和read(name2, name1)）简而言之，这个方法读取在两个友谊中并将友谊添加到地图中。在 else 块中（如果 name1 已经是 HashMap 中的 key），我想添加代码以获取现有的好友列表（只有一个） name1 的值）并再次调用 read。

这里是read方法，如果你需要的话

private Map<String, Set> friends;

// Adds two friends, name1 and name2, to the HashMap of friendships
public void read(String name1, String name2)
{
    // Temporary HashSet in case a person has more than one friend
    Set<String> strSet = new HashSet<String>();     

    if (!friends.containsKey(name1))
    {
        strSet.add(name2);

        friends.put(name1, strSet);
    }

    else
    {
        strSet.clear();

        // Set strSet to the current friendlist of name1
        strSet = friends.get(name1);            

        strSet.add(name2);

        // Make a new entry in the HashMap with name1 and the updated friend list
        friends.put(name1, strSet);
    }
}

另一种解决方案（脱离该线程的标题）是找到好友列表的所有可能组合。例如如果 Dalton 在他的朋友列表中有 Bob、Sue 和 Dave，我可以找到一种方法来找到两种友谊的所有可能组合（记住，顺序无关紧要）：

Bob Sue
Bob Dave
Sue Dave

但是，我不知道如何编写代码。有什么建议吗？

Answer 1

这里有一个伪代码的做法（以后可以查Java）

假设每次添加时朋友的所有朋友都正确匹配。

获取两个新输入，并创建一个包含所有朋友以及输入值的临时集合。

对于临时集合中的每个值，将所有其他值添加为好友。（集合应该只保留唯一值，但您可以明确检查是否需要）。

这可能不是最有效的解决方案（在每一步中，一半的添加都是重复的），但它应该是一个起点。

Func (friend1, friend2)
    tempSet = masterSet(friend1).Hashset
    UNION
    masterSet(friend2).Hashset
    UNION
    friend1, friend2

     foreach (friend in tempSet)
         foreach(otherFriend in tempSet - friend)
             friend.AddFriend(otherFriend)
             otherFriend.AddFriend(friend)

Answer 2

您描述的第二种解决方案等同于disjoint-set data structure。你的朋友最终会成群结队，每组中的每个人都与该组中的其他人成为朋友，而不是其他人。

实现此数据结构的棘手部分是当您发现不同集合中的两个人是朋友时合并两个集合。

这是一个天真的实现：

public class DisjointFriendSet {
    private final Map<String, Set<String>> personToFriends = new HashMap<>();

    /**
     * Includes the person themselves in their group of friends.
     * 
     * If no friendships have been registered for this person, then returns a set
     * containing just themselves.
     * 
     * @param person
     * @return
     */
    public Set<String> getFriends(String person) {
        if(personToFriends.containsKey(person)) {
            return personToFriends.get(person);
        } else {
            final Set<String> result = new HashSet<>();
            result.add(person);
            return result;
        }
    }

    public void addFriendship(String person1, String person2) {
        final Set<String> friends1 = getFriends(person1);
        final Set<String> friends2 = getFriends(person2);

        if(friends1 == friends2) {
            return;
        } else {
            personToFriends.put(person1, friends1);
            friends1.addAll(friends2);
            for(String person: friends2) {
                personToFriends.put(person, friends1);
            }
        }
    }

    /**
     * 
     * @return All unique friendship groups
     */
    public Collection<Set<String>> getAllFriendshipGroups() {
        return new HashSet<>(personToFriends.values());
    }

    public static void main(String[] args) {
        final DisjointFriendSet disjointFriendSet = new DisjointFriendSet();

        disjointFriendSet.addFriendship("Alice","Beowulf");
        disjointFriendSet.addFriendship("Charity","Donald");
        disjointFriendSet.addFriendship("Eduardo","Frank");
        disjointFriendSet.addFriendship("Grendel","Harriet");

        System.out.println("Friendship groups: "+disjointFriendSet.getAllFriendshipGroups());

        System.out.println("Adding friendship between Grendel and Beowulf");
        disjointFriendSet.addFriendship("Grendel","Beowulf");
        System.out.println("Friendship groups: "+disjointFriendSet.getAllFriendshipGroups());
        System.out.println();

        for(String person: new String[]{"Alice","Beowulf","Charity","Donald","Eduardo","Frank","Grendel","Harriet","Zod"}) {
            System.out.println(person+"'s friends: "+disjointFriendSet.getFriends(person));
        }
    }
}

查找字符串 HashSet 的组合

Finding combinations of a HashSet of Strings

java

combinations

dictionary

set