java - 如果给我一堆组合，每个组合都有 k-1 个元素，如何生成大小为 k 个元素的列表？

Question

在某种程度上，这与从包含 k+1 个元素的数组生成大小为 k 的子集的问题相反。

例如，如果有人给我对 {a,b} 、 {a,c} 、 {b,c} 、{a,e} 、{b,e}、{a,f} ，我需要一个算法来告诉我三元组 {a,b,c} 和 (a,b,e} 完全覆盖了给我的对中的成对组合。我需要从示例中的对/三元组推广到 k/k+1 的情况

我的预感是会有一个记录良好且高效的算法来解决我的问题。遗憾的是，在互联网上搜索并没有帮助获得它。 stackoverflow 中已发布的问题不涵盖此问题。因此，我不得不发布这个问题来找到我的解决方案。

Answer 1

我不熟悉为此建立的算法，并且您没有要求特定的语言，因此我编写了一个 C# 算法来完成您所要求的并与提供的测试值相匹配。它没有太多现实世界的错误检查。我有一个 .Net fiddle，您可以运行它以在网络浏览器中查看结果。 https://dotnetfiddle.net/ErwTeg

它的工作原理是将数组的数组(或类似的容器)转换为字典，其中每个唯一值作为键，每个键的值是在带有该键的任何列表中找到的每个值。从您的示例中，a 获取 {b,c,e,f}(我们称它们为好友，这就是 GetFriends 函数的作用)

AreFriendsWithEachother 函数指示所有传递的值是否与所有其他值都是友元。

然后，好友列表的结果将输入到 MakeTeam 函数，该函数通过枚举某个 key 拥有的每个好友并尝试这些好友的每个 size 长度排列，来创建给定 size 的团队。例如，在原始示例中，a 的友元排列为 {{a,b,c},{a,b,e},{a,b,f},{a,c,b},{a,c,e},{a,c,f},{a,e,b},{a,e,c},{a,e,f},{a,f,b},{a,f,c},{a,f,e}}。其中，我们通过检查我们之前创建的好友列表来确保所有三个值都是好友。如果排列中的所有值都是友元，那么我们将其添加到结果缓存中。然后将剔除所有重复集的结果。这是通过使用 HashSet 在 C# 中处理的，它仅添加列表中尚未存在的项目。

MakeTeam 函数看起来很糟糕，因为它包含运行时可变数量的循环(通常由 foreach 可视化)。我通过枚举器上下滚动并自己模拟 foreach 循环。

我提供了 MakeTeamOf3 和 MakeTeamOf4 的版本，它们显示静态循环结构，当您提前知道 k 值时，可以轻松调整这些结构。

此处提供了相同的代码

using System;
using System.Collections.Generic;
using System.Linq;

namespace kfromkm1 // k elements from k minus 1
{
    public class Program
    {
        static readonly string[][] pairs =
        {
            new string[] { "a", "b" },
            new string[] { "a", "c" },
            new string[] { "b", "c" },
            new string[] { "a", "e" },
            new string[] { "b", "e" },
            new string[] { "a", "f" }
        };

        static readonly string[][] pairsExpectedResult =
        {
            new string[] { "a", "b", "c" },
            new string[] { "a", "b", "e" }
        };

        static readonly string[][] triplets =
        {
            new string[] { "a", "b", "c" },
            new string[] { "a", "b", "d" },
            new string[] { "a", "c", "d" },
            new string[] { "b", "c", "d" },
            new string[] { "b", "c", "e" }
        };

        static readonly string[][] tripletsExpectedResults =
        {
            new string[] { "a", "b", "c", "d" }
        };

        public static void Main(string[] args)
        {
            Dictionary<string, HashSet<string>> friendsList = GetFriends(pairs);
            Dump(nameof(pairs), pairs);
            Console.WriteLine();
            Dump(nameof(pairsExpectedResult), pairsExpectedResult);
            Console.WriteLine();
            HashSet<HashSet<string>> teams = MakeTeams(friendsList, 3);
            Dump(nameof(teams), teams);

            Console.WriteLine();

            friendsList = GetFriends(triplets);
            Dump(nameof(triplets), triplets);
            Console.WriteLine();
            Dump(nameof(tripletsExpectedResults), tripletsExpectedResults);
            Console.WriteLine();
            teams = MakeTeams(friendsList, 4);
            Dump(nameof(teams), teams);

            Console.ReadLine();
        }

        // helper function to display results
        static void Dump<T>(string name, IEnumerable<IEnumerable<T>> values)
        {
            Console.WriteLine($"{name} =");
            int line = 0;
            bool notfirst;
            foreach (IEnumerable<T> layer in values)
            {
                Console.Write($"{line}: {{");
                notfirst = false;
                foreach (T value in layer)
                {
                    if (notfirst)
                        Console.Write($", {value}");
                    else
                    {
                        Console.Write(value);
                        notfirst = true;
                    }
                }
                Console.WriteLine("}");
                line++;
            }
        }

        // items are friends if they show up in a set (pair in the example) together
        // list can be a list of lists, array of arrays, list of arrays, etc
        // {a, b} means a and b are friends
        // {a, b, c} means a is friends with b and c, b is friends with a and c, c is friends with a and b
        static Dictionary<T, HashSet<T>> GetFriends<T>(IEnumerable<IEnumerable<T>> list) where T : IEquatable<T>
        {
            Dictionary<T, HashSet<T>> result = new Dictionary<T, HashSet<T>>();
            foreach (IEnumerable<T> set in list) // one set at a time
            {
                foreach (T current in set) // enumerate the set from front to back
                {
                    foreach (T other in set) // enumerate the set with a second pointer to compare every item
                    {
                        if (!current.Equals(other)) // ignore self
                        {
                            if (!result.ContainsKey(current)) // initialize this item's result hashset
                                result[current] = new HashSet<T>();
                            result[current].Add(other); // add friend (hashset will ignore duplicates)
                        }
                    }
                }
            }
            return result;
        }

        // indicates whether or not all items are friends
        static bool AreFriendsWithEachother<T>(Dictionary<T, HashSet<T>> friendsList, IEnumerable<T> values)
        {
            if (friendsList == null) // no list = no results
                throw new ArgumentNullException(nameof(friendsList));
            foreach (T first in values)
            {
                if (!friendsList.ContainsKey(first)) // not on list, has no friends
                    return false;
                foreach (T other in values)
                {
                    if (!friendsList[first].Contains(other) && !first.Equals(other)) // false if even one doesn't match, don't count self as non-friend for computational ease
                        return false;
                }
            }
            return true; // all matched so true
        }

        // size represents how many items should be in each team
        static HashSet<HashSet<T>> MakeTeams<T>(Dictionary<T, HashSet<T>> friendsList, int size) where T : IEquatable<T>
        {
            if (friendsList == null) // no list = no results
                throw new ArgumentNullException(nameof(friendsList));
            if (size < 2)
                throw new ArgumentOutOfRangeException(nameof(size), size, "Size should be greater than 2");
            HashSet<HashSet<T>> result = new HashSet<HashSet<T>>(HashSet<T>.CreateSetComparer());
            T[] values = new T[size];
            IEnumerator<T>[] enumerators = new IEnumerator<T>[size - 1]; // gotta cache our own enumerators with a variable number of "foreach" layers
            int layer;
            bool moveNext;

            foreach (T key in friendsList.Keys) // this is a mess because it's a runtime variable number of copies of enumerators running over the same list
            {
                values[0] = key;
                for (int index = 0; index < size - 1; index++)
                    enumerators[index] = friendsList[key].GetEnumerator();
                moveNext = true;
                layer = 0;
                while (moveNext)
                {
                    while (layer < size - 1 && moveNext)
                    {
                        if (enumerators[layer].MoveNext())
                            layer++;
                        else
                        {
                            if (layer == 0)
                                moveNext = false;
                            else
                            {
                                enumerators[layer].Reset();
                                layer--;
                            }
                        }
                    }
                    for (int index = 1; index < size; index++)
                        values[index] = enumerators[index - 1].Current;
                    if (values.Distinct().Count() == size && AreFriendsWithEachother(friendsList, values))
                        result.Add(new HashSet<T>(values));
                    layer--;
                }
            }

            return result;
        }

        // provided as an example
        static HashSet<HashSet<T>> MakeTeamsOf3<T>(Dictionary<T, HashSet<T>> friendsList) where T : IEquatable<T>
        {
            if (friendsList == null) // no list = no results
                throw new ArgumentNullException(nameof(friendsList));
            HashSet<HashSet<T>> result = new HashSet<HashSet<T>>(HashSet<T>.CreateSetComparer());
            T[] values;

            foreach (T key in friendsList.Keys) // start with every key
            {
                foreach (T first in friendsList[key])
                {
                    foreach (T second in friendsList[key])
                    {
                        values = new T[] { key, first, second };
                        if (values.Distinct().Count() == 3 && AreFriendsWithEachother(friendsList, values)) // there's no duplicates and they are friends
                            result.Add(new HashSet<T>(values));
                    }
                }
            }

            return result;
        }

        // provided as an example
        static HashSet<HashSet<T>> MakeTeamsOf4<T>(Dictionary<T, HashSet<T>> friendsList) where T : IEquatable<T>
        {
            if (friendsList == null) // no list = no results
                throw new ArgumentNullException(nameof(friendsList));
            HashSet<HashSet<T>> result = new HashSet<HashSet<T>>(HashSet<T>.CreateSetComparer());
            T[] values;

            foreach (T key in friendsList.Keys) // start with every key
            {
                foreach (T first in friendsList[key])
                {
                    foreach (T second in friendsList[key])
                    {
                        foreach (T third in friendsList[key])
                        {
                            values = new T[] { key, first, second, third };
                            if (values.Distinct().Count() == 4 && AreFriendsWithEachother(friendsList, values)) // there's no duplicates and they are friends
                                result.Add(new HashSet<T>(values));
                        }
                    }
                }
            }
            return result;
        }
    }
}