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

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

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

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

然后将好友列表的结果提供给该函数，该函数通过枚举密钥拥有的每个好友并尝试这些好友的每个长度排列来MakeTeam组成一个给定的团队。例如，在原始示例中，有的朋友排列。其中，我们通过检查我们之前创建的朋友列表来确保所有三个值都是朋友。如果排列中的所有值都是朋友，那么我们将其添加到结果缓存中。然后将剔除所有重复集的结果。这在 C# 中通过使用which 仅添加尚未在列表中的项目来处理。sizesizea{{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

该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;
        }
    }
}

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

问题描述

解决方案

推荐阅读