算法在电影院分组朋友 [英] Algorithm for grouping friends at the cinema
问题描述
我有脑筋急转弯你 - 它不是那么简单，因为它听起来那么请阅读并尝试解决问题。之前你问，如果它的功课 - 这不是！我只是想看看是否有解决这个优雅的方式。这里的问题：
I got a brain teaser for you - it's not as simple as it sounds so please read and try to solve the issue. Before you ask if it's homework - it's not! I just wish to see if there's an elegant way of solving this. Here's the issue:
朋友都想X个是去电影院，希望就座 在最好的群体。最好的情况是，大家坐在一起 而最坏的情况是，每个人都独自坐在那儿。较少的群体pferred超多组$ P $。营养均衡的基团是preferred（3 + 3更preferred大于4 + 2）。 独坐是至少preferred。
X-number of friends want's to go to the cinema and wish to be seated in the best available groups. Best case is that everyone sits together and worst case is that everyone sits alone. Fewer groups are preferred over more groups. Ballanced groups are preferred (3+3 is more preferred than 4+2). Sitting alone is least preferred.
输入是人们去电影院和输出应该是整型数组的数组包含数字：
Input is the number of people going to the cinema and output should be an array of integer arrays that contains:
- 有序组合（最多preferred是第一个）
- 人数每组
下面是人去电影院数量的一些例子和preferred组合的名单，这些人可以坐：
Below are some examples of number of people going to the cinema and a list of preferred combinations these people can be seated:
- 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
例有超过700人在爆炸组合，但我认为你现在明白了吧。
Example with more than 7 persons explodes in combinations but I think you get the point by now.
问题是：什么是算法的样子，解决这个问题呢？ 我的语言被选择的是C＃，所以如果你能给在C＃的答案那就太棒了！
Question is: What does an algorithm look like that solves this problem? My language by choice is C# so if you could give an answer in C# it would be fantastic!
推荐答案
我认为你需要递归地做到这一点，但你必须确保你不保持一遍又一遍的分区在同一组。这会给你指数的执行时间。在我的解决方案看起来我有O（N * N）（您可以验证这对我来说），请参阅下面的结果。另一件事是你提到的desirablity功能。我不知道怎么这样的功能看起来是这样，但你可以比较，而不是2个分区。例如分区1 + 1 + 2 + 4是不太理想的，然后1 + 2 + 2 + 3，因为它有两个1。一般规则可以是一个分区是不理想的，如果它有更多的人进行分组比另一个分区相同数量的'。有道理，更多的人坐在一起，就更好了。我的解决方案采用这种方法比较2可能的分组，我得到你想要达到的结果。首先，让我告诉你一些结果，那么code。
I think you need to do it recursively but you need to make sure that you don't keep partitioning the same group over and over again. This will give you exponential execution time. In my solution it looks I have O(n*n) (you can verify it for me ;) , see the results below. Another thing is the desirablity function you mention. I don't know how such a function could look like, but you can instead compare 2 partitions. e.g. partition 1 + 1 + 2 + 4 is less desirable then 1 + 2 + 2 + 3 because it has two 'ones'. A general rule could be 'a partition is less desirable if it has more of the same number of people grouped than another partition'. Makes sense, the more people sit together, the better. My solution takes this approach for comparing 2 possible groupings and I get the result that you wanted to achieve. Let me show you some results first, then the code.
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
1 person: 1
2人：2，1 + 1
2 persons: 2, 1+1
3人：3，1 + 2，1 + 1 + 1
3 persons: 3, 1+2, 1+1+1
4人：4，2 + 2,1 + 3，1 + 1 + 2，1 + 1 + 1 + 1
4 persons: 4, 2+2, 1+3, 1+1+2, 1+1+1+1
5人：5，2 + 3 + 4，1 + 2 + 2，1 + 1 + 3，1 + 1 + 1 + 2，1 + 1 + 1 + 1 + 1
5 persons: 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，l + 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
6 persons: 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）：
performance looks to be 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类：
Let me post now the 3 classes involved in the solution:
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: http://stackoverflow.com/questions/3404715/c-sharp-hashcode-for-array-of-ints
/// </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;
}
}
现在到了解决办法：
的谜题类做递归。在这个类的一个技巧就是在HashSet的使用自定义比较（ PossibleGroupingComparer ）。这将确保当我们计算新的分组（例如1 + 1 + 2对2 + 1 + 1），这些将被视为是相同的（我们的集将仅包含一个重新presentant每个等效分组）。这将减少指数的运行时为O（n ^ 2）。
The brainteaser class does the recursion. One trick in this class is to use a custom comparer (PossibleGroupingComparer) in the hashset. This will make sure that when we calculate new groupings (e.g. 1+1+2 vs 2+1+1), those will be treated as the same (our set will contain only one representant for each equivalent grouping). This should reduce exponential runtime to O(n^2).
接下来的诀窍是，排序的结果是可能的，因为我们的 PossibleGroupings 类实现IComparable的。的比较（）方法的实现使用上述想法。该方法主要包含盐在此解决方案，如果你想拥有它分为不同的，你应该只修改这个方法。
The next trick is that ordering the result is possible because our PossibleGroupings class implements IComparable. The implementation of the Compare() method uses the idea mentioned above. This method essentially contains the salt in this solution and if you want to have it grouped differently you should only modify this method.
我希望你能理解code，否则让我知道。我试图使它可读，并没有在意性能。你可以如命令分组只有之前它们返回给调用者，在递归内的顺序不会带来太大。
I hope you can understand the code otherwise let me know. I tried to make it readable and didn't care much about performance. You could for instance order the groupings only before you return them to the caller, the ordering within the recursions doesn't bring much.
一个评论，但：一个典型的场景可能是一个电影院有'已经'预订的席位，也不会允许任何分区。在这里，你需要得到所有分区，然后检查一个接一个，如果有可能用于当前电影院。这样的作品，但成本不必要的CPU。相反，我们可以使用输入来减少递归的次数，提高整体的执行时间。也许有人要发布一个解决方案;）
One comment though: A typical scenario might be that a cinema has 'already' booked many seats and won't allow for 'any' partition. Here you need to get all partitions and then check one-by-one if it's possible to use for the current cinema. That works, but costs unnecessary CPU. Instead, we could use the input to reduce the number of recursions and improve the overall execution time. Maybe someone wants to post a solution for this ;)
这篇关于算法在电影院分组朋友的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
