Friends grouping algorithm in a movie theater

Question

I have a brain teaser for you - it is not as simple as it seems, so please read and try to solve the problem. Before asking if this will be homework - no! I just want to see if there is an elegant way to solve this. Here's the problem:

X-number of friends want to go to the movies and want to sit in the best groups available. The best case is that everyone is sitting together and in the worst case, everyone is sitting alone. Fewer groups are preferable for more groups. Ballistic groups are preferred (3 + 3 more preferably than 4 + 2). Least preferred is the seat.

Input is the number of people going to the cinema, and the output should be an array of integer arrays that contains:

• Ordered combinations (most preferred are the first ones)
• The number of people in each group

The following are some examples of the number of people going to the movies, and a list of preferred combinations that these people can sit:

• 1 person: 1
• 2 people: 2, 1 + 1
• 3 people: 3, 2 + 1, 1 + 1 + 1
• 4 people: 4, 2 + 2, 3 + 1, 2 + 1 + 1, 1 + 1 + 1 + 1
• 5 people: 5, 3 + 2, 4 + 1, 2 + 2 + 1, 3 + 1 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1
• 6 people: 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

An example where more than 7 people explode in combinations, but I think you guessed it.

Question: What is the algorithm that solves this problem? My language of choice is C #, so if you could give an answer in C #, that would be fantastic!

Answer 1

I think you need to do this recursively, but you need to make sure that you will not share the same group again and again. This will give you exponential runtime. In my solution, it looks like I have O (n * n) (you can check it out for me;), see Results below. Another thing is the desirability function that you mentioned. I do not know how such a function might look, but instead you can compare 2 sections. for example, the section 1 + 1 + 2 + 4 is less desirable, then 1 + 2 + 2 + 3, because it has two “units”. A general rule may be that “a section is less desirable if it has more people grouped than another section.” It makes sense the more people sit together, the better. My solution uses this approach to compare two possible groupings, and I get the result you wanted to achieve. Let me show you some results first, and 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 person: 1

2 people: 2, 1 + 1

3 people: 3, 1 + 2, 1 + 1 + 1

4 people: 4, 2 + 2, 1 + 3, 1 + 1 + 2, 1 + 1 + 1 + 1

5 people: 5, 2 + 3, 1 + 4, 1 + 2 + 2, 1 + 1 + 3, 1 + 1 + 1 + 2, 1 + 1 + 1 + 1 + 1

6 people: 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

performance looks like 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 

Let me post 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 (eg 2 + 1 vs. 1 + 2). Only one representant /// of each grouping is returned (ordered ascending. eg 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. Eg /// 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, eg 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. eg 'this' group might have 2 groups with each 2 friends, // but the other solution might have 3 groups with each 2 friends. It 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; } } 

Now to the solution:

The brainteaser class performs recursion. One trick in this class is to use a custom mapper ( PossibleGroupingComparer ) in a hashset. This will make sure that when calculating new groupings (for example, 1 + 1 + 2 versus 2 + 1 + 1) they will be considered the same (our set will contain only one representative for each equivalent group). This should reduce exponential runtime to O (n ^ 2).

The next trick is that ordering the result is possible because our PossibleGroupings class implements IComparable. The implementation of the Compare () method uses the above idea. This method essentially contains salt in this solution, and if you want it to be grouped in different ways, you only need to modify this method.

I hope you understand the code, otherwise let me know. I tried to make it readable and didn't really care about performance. For example, you can order groupings only before you return them to the caller; ordering inside recursions will not bring much.

One comment: a typical scenario may be that the cinema has already "reserved" many seats and will not allow "any" partitions. Here you need to get all the sections, and then check one by one, if possible for the current movie theater. It works, but it costs an extra processor. Instead, we could use input to reduce the number of recursions and improve the overall execution time. Maybe someone wants to post a solution for this;)

Answer 2

Assuming I understand you correctly, you can do this recursively.

• For one person, the only group is 1 .
• For people n all groups are grouped from group 1 and the remaining n-1 people, groups of 2 people and the remaining n-2 people, etc.

Once you have a list of possible groupings, you can sort them by “desirability” based on whatever criteria you want.

Answer 3

Here is a function that lists all sections using the fastest search algorithm

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

And here is a function that will change the order of the lists of returned items (above) according to your preference:

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

Finally, here is a method that can be called from a control event to call these functions and display the results in a ListBox. (note: "Partitons" is a class containing the above functions)

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