电影院朋友分组算法

Question

我给你出一个脑筋急转弯——这个问题并不像听起来那么简单，请仔细阅读并尝试解决。在你问这是否是作业之前，我告诉你不是！我只是想看看是否有一种优雅的方法来解决这个问题。下面是问题描述：

一定数量的朋友想去电影院，并希望坐在最好的位置。最好的情况是每个人都坐在一起，最差的情况是每个人都坐得很孤单。较少的组更受欢迎，平衡的组更受欢迎（3+3比4+2更受欢迎）。独自坐着最不受欢迎。

输入为去电影院的人数，输出应该是一个包含以下内容的整数数组的数组：

- 排列组合（首选排在最前面） - 每组的人数

以下是一些去电影院的人数及其可以坐的首选组合的示例：

- 1个人：1 - 2个人：2、1+1 - 3个人：3、2+1、1+1+1 - 4个人：4、2+2、3+1、2+1+1、1+1+1+1 - 5个人：5、3+2、4+1、2+2+1、3+1+1、2+1+1+1、1+1+1+1+1 - 6个人：6、3+3、4+2、2+2+2、5+1、3+2+1、2+2+1+1、2+1+1+1+1、1+1+1+1+1+1

人数超过7人的示例会爆炸，但我认为你现在明白了问题所在。

问题是：解决这个问题的算法是什么？

我的语言选择是C#，如果您能用C#回答，那就太好了！

- Tim Skauge

---

适合发布在Programmers.SE还是CodeGolf.SE？ - Yuck

如果“少组优于多组”，那么为什么“2+2+2”比“5+1”更受欢迎？ - Tung

您只需要列举可能的划分并应用某些（目前还未确定的）排名函数。这是一个稍微更适用的维基链接（在我看来）：http://en.wikipedia.org/wiki/Integer_partition - RBarryYoung

@KendallFrey，不完全正确。正如Tim所指出的那样，让某人独自坐着是最不理想的，这就是为什么在6个人的例子中，2+2+2比5+1更受欢迎的原因。 - Tung

重新开放投票：如果这个问题被标记为“面试题”，它就不会被关闭。 - BlackBear

Answer 1

我认为你需要递归执行，但要确保不要一遍又一遍地对同一组进行分区，否则执行时间将呈指数级增长。在我的解决方案中，看起来我有O(n*n)的复杂度（你可以验证一下；），请参见下面的结果。另一件事是你提到的期望函数。我不知道这样的函数会是什么样子，但你可以比较两个分区。例如，分区1 + 1 + 2 + 4不如1 + 2 + 2 + 3好，因为它有两个“1”。一个通用规则可能是“如果一个分区中有更多相同人数的人被分组，则该分区不太理想”。这很有道理，人们越聚在一起，就越好。我的解决方案采用这种方法比较两种可能的分组方式，并得到了你想要实现的结果。让我先展示一些结果，然后是代码。

        var sut = new BrainTeaser();

        for (int n = 1; n <= 6; n++) {
            StringBuilder sb = new StringBuilder();
            sb.AppendFormat("{0} person{1}: ", n, n > 1 ? "s" : "");

            var array = sut.Solve(n).Select(x => x.ToString()).ToArray();
            sb.AppendLine(string.Join(", ", array));

            Console.WriteLine(sb.ToString());
        }

1个人：1

2个人：2，1+1

3个人：3，1+2，1+1+1

4个人：4，2+2，1+3，1+1+2，1+1+1+1

5个人：5，2+3，1+4，1+2+2，1+1+3，1+1+1+2，1+1+1+1+1

6个人：6，3+3，2+4，2+2+2，1+5，1+2+3，1+1+4，1+1+2+2，1+1+1+3，1+1+1+1+2，1+1+1+1+1+1

性能看起来是O(n*n)：

var sut = new BrainTeaser();

 for (int n = 1; n <= 40; n++) {
   Stopwatch watch = new Stopwatch();
   watch.Start();
   var count = sut.Solve(n).Count();
   watch.Stop();
   Console.WriteLine("Problem solved for {0} friends in {1} ms. Number of solutions {2}", n, watch.ElapsedMilliseconds, count);
}

Problem solved for 1 friends in 17 ms. Number of solutions 1
Problem solved for 2 friends in 49 ms. Number of solutions 2
Problem solved for 3 friends in 2 ms. Number of solutions 3
Problem solved for 4 friends in 1 ms. Number of solutions 5
Problem solved for 5 friends in 0 ms. Number of solutions 7
Problem solved for 6 friends in 2 ms. Number of solutions 11
Problem solved for 7 friends in 0 ms. Number of solutions 15
Problem solved for 8 friends in 0 ms. Number of solutions 22
Problem solved for 9 friends in 1 ms. Number of solutions 30
Problem solved for 10 friends in 1 ms. Number of solutions 42
Problem solved for 11 friends in 4 ms. Number of solutions 56
Problem solved for 12 friends in 4 ms. Number of solutions 77
Problem solved for 13 friends in 7 ms. Number of solutions 101
Problem solved for 14 friends in 9 ms. Number of solutions 135
Problem solved for 15 friends in 15 ms. Number of solutions 176
Problem solved for 16 friends in 21 ms. Number of solutions 231
Problem solved for 17 friends in 30 ms. Number of solutions 297
Problem solved for 18 friends in 43 ms. Number of solutions 385
Problem solved for 19 friends in 61 ms. Number of solutions 490
Problem solved for 20 friends in 85 ms. Number of solutions 627
Problem solved for 21 friends in 117 ms. Number of solutions 792
Problem solved for 22 friends in 164 ms. Number of solutions 1002
Problem solved for 23 friends in 219 ms. Number of solutions 1255
Problem solved for 24 friends in 300 ms. Number of solutions 1575
Problem solved for 25 friends in 386 ms. Number of solutions 1958
Problem solved for 26 friends in 519 ms. Number of solutions 2436
Problem solved for 27 friends in 677 ms. Number of solutions 3010
Problem solved for 28 friends in 895 ms. Number of solutions 3718
Problem solved for 29 friends in 1168 ms. Number of solutions 4565
Problem solved for 30 friends in 1545 ms. Number of solutions 5604
Problem solved for 31 friends in 2025 ms. Number of solutions 6842
Problem solved for 32 friends in 2577 ms. Number of solutions 8349
Problem solved for 33 friends in 3227 ms. Number of solutions 10143
Problem solved for 34 friends in 4137 ms. Number of solutions 12310
Problem solved for 35 friends in 5300 ms. Number of solutions 14883
Problem solved for 36 friends in 6429 ms. Number of solutions 17977
Problem solved for 37 friends in 8190 ms. Number of solutions 21637
Problem solved for 38 friends in 10162 ms. Number of solutions 26015
Problem solved for 39 friends in 12643 ms. Number of solutions 31185

现在让我贴出解决方案中涉及的3个类：

public class BrainTeaser {
    /// <summary>
    /// The possible groupings are returned in order of the 'most' desirable first. Equivalent groupings are not returned (e.g. 2 + 1 vs. 1 + 2). Only one representant
    /// of each grouping is returned (ordered ascending. e.g. 1 + 1 + 2 + 4 + 5)
    /// </summary>
    /// <param name="numberOfFriends"></param>
    /// <returns></returns>
    public IEnumerable<PossibleGrouping> Solve(int numberOfFriends) {
        if (numberOfFriends == 1) {
            yield return new PossibleGrouping(1);
            yield break;
        }
        HashSet<PossibleGrouping> possibleGroupings = new HashSet<PossibleGrouping>(new PossibleGroupingComparer());
        foreach (var grouping in Solve(numberOfFriends - 1)) {
            // for each group we create 'n+1' new groups 
            // 1 + 1 + 2 + 3 + 4 
            // Becomes
            //      (1+1) + 1 + 2 + 3 + 4  we can add a friend to the first group
            //      1 + (1+1) + 2 + 3 + 4  we can add a friend to the second group
            //      1 + 1 + (2+1) + 3 + 4  we can add a friend to the third group
            //      1 + 1 + 2 + (3+1) + 4  we can add a friend to the forth group
            //      1 + 1 + 2 + 3 + (4+1) we can add a friend to the fifth group
            //      (1 + 1 + 2 + 3 + 4) + 1  friend has to sit alone

            AddAllPartitions(grouping, possibleGroupings);
        }
        foreach (var possibleGrouping in possibleGroupings.OrderByDescending(x => x)) {
            yield return possibleGrouping;
        }
    }

    private void AddAllPartitions(PossibleGrouping grouping, HashSet<PossibleGrouping> possibleGroupings) {
        for (int i = 0; i < grouping.FriendsInGroup.Length; i++) {
            int[] newFriendsInGroup = (int[]) grouping.FriendsInGroup.Clone();
            newFriendsInGroup[i] = newFriendsInGroup[i] + 1;
            possibleGroupings.Add(new PossibleGrouping(newFriendsInGroup));
        }
        var friendsInGroupWithOneAtTheEnd = grouping.FriendsInGroup.Concat(new[] {1}).ToArray();
        possibleGroupings.Add(new PossibleGrouping(friendsInGroupWithOneAtTheEnd));
    }
}

/// <summary>
/// A possible grouping of friends. E.g.
/// 1 + 1 + 2 + 2 + 4 (10 friends). The array is sorted by the least friends in an group.
/// </summary>
public class PossibleGrouping : IComparable<PossibleGrouping> {
    private readonly int[] friendsInGroup;

    public int[] FriendsInGroup {
        get { return friendsInGroup; }
    }

    private readonly int sum;

    public PossibleGrouping(params int[] friendsInGroup) {
        this.friendsInGroup = friendsInGroup.OrderBy(x => x).ToArray();
        sum = friendsInGroup.Sum();
    }

    public int Sum {
        get { return sum; }
    }

    /// <summary>
    /// determine which group is more desirable. Example:
    /// Consider g1: 1 + 2 + 3 + 4 vs g2: 1 + 1 + 2 + 2 + 4  
    /// Group each sequence by the number of occurrences:
    /// 
    /// group   | g1   | g2
    /// --------|-------------
    /// 1       | 1    | 2
    /// ----------------------
    /// 2       | 1    | 2
    /// ----------------------
    /// 3       | 1    | 0
    /// ----------------------
    /// 4       | 1    | 1
    /// ----------------------
    /// 
    /// Sequence 'g1' should score 'higher' because it has 'less' 'ones' (least desirable) elements. 
    /// 
    /// If both sequence would have same number of 'ones', we'd compare the 'twos'.
    /// 
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public int CompareTo(PossibleGrouping other) {
        var thisGroup = (from n in friendsInGroup group n by n).ToDictionary(x => x.Key,
                                                                             x => x.Count());

        var otherGroup = (from n in other.friendsInGroup group n by n).ToDictionary(x => x.Key,
                                                                                    x => x.Count());

        return WhichGroupIsBetter(thisGroup, otherGroup);
    }

    private int WhichGroupIsBetter(IDictionary<int, int> thisGroup, IDictionary<int, int> otherGroup) {
        int maxNumberOfFriendsInAGroups = Math.Max(thisGroup.Keys.Max(), otherGroup.Keys.Max());

        for (int numberOfFriendsInGroup = 1;
             numberOfFriendsInGroup <= maxNumberOfFriendsInAGroups;
             numberOfFriendsInGroup++) {
            // zero means that the current grouping does not contain a such group with 'numberOfFriendsInGroup'
            // in the example above, e.g. group '3'
            int thisNumberOfGroups = thisGroup.ContainsKey(numberOfFriendsInGroup)
                                         ? thisGroup[numberOfFriendsInGroup]
                                         : 0;
            int otherNumberOfGroups = otherGroup.ContainsKey(numberOfFriendsInGroup)
                                          ? otherGroup[numberOfFriendsInGroup]
                                          : 0;

            int compare = thisNumberOfGroups.CompareTo(otherNumberOfGroups);

            if (compare != 0) {
                // positive score means that the other group has more occurrences. e.g. 'this' group might have 2 groups with each 2 friends,
                // but the other solution might have 3 groups with each 2 friends. It's obvious that (because both solutions must sum up to the same value)
                // this 'solution' must contain a grouping with more than 3 friends which is more desirable.
                return -compare;
            }
        }
        // they must be 'equal' in this case.
        return 0;
    }

    public override string ToString() {
        return string.Join("+", friendsInGroup.Select(x => x.ToString()).ToArray());
    }
}

public class PossibleGroupingComparer : EqualityComparer<PossibleGrouping> {
    public override bool Equals(PossibleGrouping x, PossibleGrouping y) {
        return x.FriendsInGroup.SequenceEqual(y.FriendsInGroup);
    }

    /// <summary>
    /// may not be the best hashcode function. for alternatives look here: http://burtleburtle.net/bob/hash/doobs.html
    /// I got this code from here: https://dev59.com/c3A75IYBdhLWcg3wPmZ8
    /// </summary>
    /// <param name="obj"></param>
    /// <returns></returns>
    public override int GetHashCode(PossibleGrouping obj) {
        var array = obj.FriendsInGroup;

        int hc = obj.FriendsInGroup.Length;
        for (int i = 0; i < array.Length; ++i) {
            hc = unchecked(hc*314159 + array[i]);
        }
        return hc;
    }
}

现在来介绍解决方案：

递归的功能由脑筋急转弯类完成。该类中的一个技巧是在哈希集中使用自定义比较器（PossibleGroupingComparer）。这将确保当我们计算新的分组时（例如，1 + 1 + 2与2 + 1 + 1），它们将被视为相同（我们的集合将只包含每个等效分组的一个代表）。这应该将指数运行时间降至O（n ^ 2）。

下一个技巧是可以对结果进行排序，因为我们的PossibleGroupings类实现了IComparable。 Compare（）方法的实现使用上述思想。这种方法本质上包含了此解决方案中的关键点，如果您想以不同的方式对其进行分组，则应仅修改此方法。

希望您能理解代码，否则请告诉我。我试图使其易读，并且并不太关心性能。例如，您可以仅在将它们返回给调用者之前对分组进行排序，在递归内部进行排序并没有太大作用。

但是需要注意的一点是：典型情况可能是电影院已经预订了许多座位，并且不允许进行任何分区。在这种情况下，您需要获取所有分区，然后逐个检查是否可以用于当前电影院。这可以工作，但会浪费不必要的CPU。相反，我们可以使用输入来减少递归的次数并提高整体执行时间。也许有人想发布此解决方案;)

- shaft

---

我不是很确定，但我认为该算法可以归类为动态规划问题（http://en.wikipedia.org/wiki/Dynamic_programming）。指数级增长但不断解决同一问题的分治算法可以使用缓存来提高性能。一个著名的例子是Lehvenstein距离。 - shaft

我刚刚注意到我的解决方案存在风险。可比较的实现必须保证是可传递的：如果a < b且b < c，则a < c，否则排序可能会无限运行。我不确定如何证明它（但它似乎有效;）。 - shaft

@shaft：如果排序不是传递的，它不会导致无限循环。相反，它将根据元素最初的顺序以不同的有序列表进行排序。 - Oliver

@shaft 太棒了！昨晚我自己在研究解决方案，最终想出了一个效率低下的办法，但至少它能够工作。这看起来很酷！ - Tim Skauge

Answer 2

假设我理解你的意思正确，你可以递归地完成这个任务。

• 对于一个人，唯一的分组是 1。
• 对于 n 个人，分组包括一个人和剩下的 n-1 人的分组、两个人和剩下的 n-2 人的分组等等。

一旦你获得了可能的分组列表，你可以根据任何你想要的标准按“可取性”对它们进行排序。

- Li-aung Yip

---

我的最初想法也是如此。直到我开始编写解决问题的代码，才发现对数组进行排序并不像听起来那么容易。另外，2+1和1+2是同一种组合。 - Tim Skauge

@TimSkauge：最困难的部分是创建一个计算“可取性”得分的函数。一旦你有了这个函数，你就可以将其用作排序的标准。 - Chris Laplante

Answer 3

这是一个函数，它使用已知最快的算法枚举所有分区。

    public static List<List<int>> EnumerateAll(int n)
    {
        /* Fastest known algorithim for enumerating partitons
         * (not counting the re-ordering that I added)
         * Based on the Python code from http://homepages.ed.ac.uk/jkellehe/partitions.php
         */
        List<List<int>> lst = new List<List<int>>();
        int[] aa = new int[n + 1];
        List<int> a = new List<int>(aa.ToList<int>());
        List<int> tmp;
        int k = 1;

        a[0] = 0;
        int y = n - 1;

        while (k != 0)
        {
            int x = a[k - 1] + 1;
            k -= 1;
            while (2 * x <= y)
            {
                a[k] = x;
                y -= x;
                k += 1;
            }
            int l = k + 1;
            while (x <= y)
            {
                a[k] = x;
                a[l] = y;

                // copy just the part that we want
                tmp = (new List<int>(a.GetRange(0, k + 2)));

                // insert at the beginning to return partions in the expected order
                lst.Insert(0, tmp);
                x += 1;
                y -= 1;
            }
            a[k] = x + y;
            y = x + y - 1;

            // copy just the part that we want
            tmp = (new List<int>(a.GetRange(0, k + 1)));

            // insert at the beginning to return partions in the expected order
            lst.Insert(0, tmp);
        }

        return lst;
    }

这里有一个函数，它可以根据您的偏好重新排序返回的分区列表（如上所示）：

    /// <summary>
    /// ReOrders a list of partitons placing those with the smallest groups last
    ///   NOTE: this routine assumes that each partitoning lists the smallest 
    ///   integers *first*.
    /// </summary>
    public static IList<List<int>> ReOrderPartitions(IList<List<int>> source)
    {
        // the count is used in several places
        long totalCount= source.Count;
        long k = 0;     // counter to keep the keys unique

        SortedList<long, List<int>> srt = new SortedList<long, List<int>>(source.Count);

        foreach (List<int> prt in source)
        {
            srt.Add(-(prt[0] * totalCount) + k, prt);
            k++;
        }

        return srt.Values;
    }

最后，这里有一个可以从控件事件中调用这些函数并在ListBox中显示结果的方法。（注意：“Partitons”是包含上述函数的类）

    private void ListPreferredPartitons(int n, ListBox listOut)
    {
        IList<List<int>> pts = Partitions.EnumerateAll(n);
        pts = Partitions.ReOrderPartitions(pts);

        listOut.Items.Clear();

        foreach (List<int> prt in pts)
        {
            // reverse the list, so that the largest integers will now be first.
            prt.Reverse();
            string lin = "";
            foreach (int k in prt)
            {
                if (lin.Length > 0) lin += ", ";
                lin += k.ToString();
            }
            listOut.Items.Add(lin);
        }
    }

- RBarryYoung