Get All Possible Combinations and Sum Results

Question

I have a list a simple Player object, as follows

 Name            | Team   | Position | Total 
 Tom Brady       | Team 1 | QB       | 200
 Adrian Peterson | Team 1 | RB       | 250
 Calvin Johnson  | Team 2 | WR       | 260
 LeVon Bell      | Team 2 | RB       | 220
 Peyton Manning  | Team 3 | QB       | 220
 Arian Foster    | Team 3 | RB       | 220

This is a simple sample, in reality there are about 200 records. What I want to do is to get all possible combinations of players per team, and sum their total, so the end product would be as follows

Possibilities

 Teams   | Players                         | Total 
 Team 1  | Tom Brady, Adrian Peterson      | 450 
 Team 2  | Calvin Johnson, LeVon Bell      | 480
 Team 3  | Peyton Manning, Arian Foster    | 440

Basically I am looking for trade possibilities, so I need to get combinations of players per team. The largest possible combination I am looking for is 5 players per team, where I would have the Players and their points combined in a new object. Right now I can get there with below.

  var playerList = players.GroupBy(p => p.Team)
    .Select(g => new
    {
        Team = g.Key,
        g
    }).ToList();

        List<Possibilities> possibilities = new List<Possibilities>();

        foreach (var a in playerList)
        {
            List<Possibilities> onePlayer = (from b in a.g
                                             select new Possibilities
                                             {
                                                 Players = b.Name,
                                                 Total = b.Total,
                                                 Team = a.Team
                                             }).ToList();


            List<Possibilities> twoPlayer = (from b in a.g
                                             from c in a.g
                                             select new Possibilities
                                             {
                                                 Players = b.Name + ", " + c.Name,
                                                 Total = b.Total + c.Total,
                                                 Team = a.Team
                                             }).ToList();

And this gives me all combinations of 1,2,3 players per team, but I want to add 4 and 5. This also does not remove duplicate combinations (Player 1, Player 2 and Player 2,Player1). Is there a cleaner way to do this?

Answer 1

You can generate all combinations of a limited set of items (where the number of items is <= 31) by counting using a binary number. Each set bit in the binary number represents an item being present in the combination.

For example, counting (in binary) for a set of 3 items:

000, 001, 010, 011, 100, 101, 110, 111

A 1 in the binary number indicates that the corresponding item in the set should be included in that combination.

If you want to ensure that the combination includes number of items in a certain range, you need to count the bits set in the binary number and check if that count is in range. There's an efficient way to do that using bit twiddling (see here for examples).

Putting that together gives code like the following. Run it and check the output. Hopefully you can see how to use it with your program.

This example produces all combinations of between 2 and 3 items taken from A, B, C, D. Its output is:

A,B
A,C
B,C
A,B,C
A,D
B,D
A,B,D
C,D
A,C,D
B,C,D

The code is:

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    public class Program
    {
        public static void Main()
        {
            var data = new [] {"A", "B", "C", "D"};

            // Get all the combinations of elements from A,B,C,D with between 2 and 3 values:

            var combinations = Combinations(data, 2, 3);

            // Combinations() has returned an IEnumerable<IEnumerable<T>>,
            // that is, a sequence of subsequences where each subsequence is one combination.

            foreach (var combination in combinations)
                Console.WriteLine(string.Join(",", combination));
        }

        public static IEnumerable<IEnumerable<T>> Combinations<T>(T[] input, int minElements, int maxElements)
        {
            int numCombinations = 2 << (input.Length - 1);

            for (int bits = 0; bits < numCombinations; ++bits)
            {
                int bitCount = NumBitsSet(bits);

                if (minElements <= bitCount && bitCount <= maxElements)
                    yield return combination(input, bits);
            }
        }

        private static IEnumerable<T> combination<T>(T[] input, int bits)
        {
            for (int bit = 1, i = 0; i < input.Length; ++i, bit <<= 1)
                if ((bits & bit) != 0)
                    yield return input[i];
        }

        public static int NumBitsSet(int i)
        {
            i = i - ((i >> 1) & 0x55555555);
            i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
            return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
        }
    }
}

Answer 2

Although probably very inefficient, the below might work. Of course that's just a simple example and you'll need to adjust the code to your situation.

static void Main(string[] args)
    {
        var nums = new[] { 1, 2, 3, 4, 5, 6 };
        var combinations = new List<int[]>();
        int[] current;

        foreach (int i in nums)
        {
            combinations.Add(new[] { i });

            foreach (int j in nums.Where(n => n != i))
            {
                current = new[] { i, j };
                if (!combinations.Any(c => current.Length == c.Length && current.All(n => c.Contains(n))))
                {
                    combinations.Add(current);
                }

                foreach (int k in nums.Where(n => n != i && n != j))
                {
                    current = new[] { i, j, k };
                    if (!combinations.Any(c => current.Length == c.Length && current.All(n => c.Contains(n))))
                    {
                        combinations.Add(current);
                    }

                    foreach (int l in nums.Where(n => n != i && n != j && n != k))
                    {
                        current = new[] { i, j, k, l };
                        if (!combinations.Any(c => current.Length == c.Length && current.All(n => c.Contains(n))))
                        {
                            combinations.Add(current);
                        }

                        foreach (int m in nums.Where(n => n != i && n != j && n != k && n != l))
                        {
                            current = new[] { i, j, k, l, m };
                            if (!combinations.Any(c => current.Length == c.Length && current.All(n => c.Contains(n))))
                            {
                                combinations.Add(current);
                            }
                        }
                    }
                }
            }
        }

        foreach (var c in combinations)
        {
            foreach (var num in c)
            {
                Console.Write(num + " ");
            }

            Console.WriteLine();
        }

        Console.ReadKey();
    }