Generating all possible x amount of targets from target list

Question

I have a list of cards (Targets) that has all possible targets for a card in a card game. However, I need to have all possible combinations of TargetCount cards to create a minimax tree. How should I approach this in C#?

I tried using the CartesianProduct extension that's been around the site but it doesn't seem to be working (compilation errors when I try to use it).

I'm simply storing the Targets in a List<Card>, and already have all possible targets. Now, for each possible combination of X cards, I want to add a List<Card> containing each X possible targets to my search tree, like below. How should I approach this?

List<GameDecision> Out = new List<GameDecision>();

foreach(Card SpellCard in PlayerSpellbook(Player))
{
    List<Card> PossibleTargets = GetPossibleTargets(SpellCard);

    foreach(all combinations of possible targets)
    {
        List<Card> Targets = new list of Card.TargetCount targets;
        Out.Add(new GameDecision() { Type = GameDecisionType.PlayCard, TheCard = SpellCard, Targets = Targets });
    }
}

Answer 1

As you are saying, you want to create a "min-max tree", that is it... that's the solution. Create a tree. Each tree node has a:

1. Card - to tell what card this node is representing;
2. List - to store the next possible target nodes;
3. Score - Added this because usually min-max trees have a score to hold the result till that node.

Starting from the root node, put all possible starting combinations in the List<Card> of root node. Every node's Card value in this List<Card> will tell what tree can form if you picked this card. This way you will keep building tree and at the bottom-most level all the leaves will represent the possible ways your card game can end. And that's how you should approach this problem.

---

Constructing the minmax tree

In order to construct the minmax tree, you can go for two ways:

1. Recursive, and
2. Iterative.

In the recursive way, you go to each child-node and construct the tree one sub-tree at a time. You explore a branch until you reach the leaf and then you go to explore the next branch until you reach another leaf and so on. When we go for such an approach in Graph traversal, it is called Depth First Traversal.

In the iterative way, you go to a child, process that child only and then put all the children of this child in a queue. Then you dequeue and process the next node that comes out of this queue. In this way, you are effectively building all the branches, one level at a time. This approach in Graph traversal is called Breadth First Traversal.

Finding the code for both approaches is very easy. Coding them yourself, is better though.

Even for small trees with a moderate number of children per node, the recursion can go down to many levels. Therefore, iterative approach is usually preferred. Both the approaches are correct though.

---

There are more questions to be answered and constraints to be taken care of if you are to design a min-max tree. Yet, the answer given above is complete in itself. Answering the additional questions at this stage, especially without your asking, will make this answer unnecessarily complicated and repulsive. Best would be that you create the design and code, and when you are stuck you come back here and ask again.

Answer 2

Your question is a bit unclear.

You say combinations. A combination is simply a list of each available option. For example, you have the array { 1, 2, 3 } and you want a combination length of 2, you will get the arrays:

1. { 1, 2 }
2. { 1, 3 }
3. { 2, 3 }

You might mean permutations. A permutation is every combination in every order. So, beginning with the same array we had before { 1, 2, 3 } all of the permutations of length 2 are:

1. { 1, 2 }
2. { 1, 3 }
3. { 2, 1 }
4. { 2, 3 }
5. { 3, 1 }
6. { 3, 2 }

To get all of the permutations regardless of the array length, you would need to find combinations first and calculate permutations.

Whichever option you may mean, here are a couple of useful extension methods.

using System;
using System.Collections.Generic;
using System.Linq;

public static class IEnumerableExtensions
{
    // Can be used to get all combinations at a certain level
    // Source: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n#1898744
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
    {
        return k == 0 ? new[] { new T[0] } :
            elements.SelectMany((e, i) =>
            elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)));
    }

    private static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource item)
    {
        if (source == null)
            throw new ArgumentNullException("source");

        yield return item;

        foreach (var element in source)
            yield return element;
    }

    // This one came from: http://stackoverflow.com/questions/774457/combination-generator-in-linq#12012418
    public static IEnumerable<IEnumerable<TSource>> Permutations<TSource>(this IEnumerable<TSource> source)
    {
        if (source == null)
            throw new ArgumentNullException("source");

        var list = source.ToList();

        if (list.Count > 1)
            return from s in list
                   from p in Permutations(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1)))
                   select p.Prepend(s);

        return new[] { list };
    }
}

Getting Permutations

It sounds like you just want to get all of the permutations of a combination (in your case PossibleTargets).

foreach (var permutation in PossibleTargets.Permutations())
{
    List<Card> Targets = new List<Card>(permutation);
    Out.Add(new GameDecision() { Type = GameDecisionType.PlayCard, TheCard = SpellCard, Targets = Targets });
}

Getting Combinations

If you do in fact mean combinations, then you need to also provide the length of the result array to solve for. You specify this as X, but you have no indication in your code what X might be. For this to work right, X must be less than Permutations.Count(), or you will always get exactly 1 combination consisting of every element in the list.

var length = X;

foreach (var combination in PossibleTargets.Combinations(length))
{
    List<Card> Targets = new List<Card>(combination);
    Out.Add(new GameDecision() { Type = GameDecisionType.PlayCard, TheCard = SpellCard, Targets = Targets });
}

A common practice is to loop through every possible length (from Combinations.Length to 1) in order to get every possible combination of any length.

for (var length = PossibleTargets.Count(); length > 0; length--)
{

    foreach (var combination in PossibleTargets.Combinations(length))
    {
        List<Card> Targets = new List<Card>(combination);
        Out.Add(new GameDecision() { Type = GameDecisionType.PlayCard, TheCard = SpellCard, Targets = Targets });
    }
}

Getting All Permutations of Every Length

This example gets every permutation (combination of cards in any order) of every possible length.

for (var length = PossibleTargets.Count(); length > 0; length--)
{
    foreach (var combination in PossibleTargets.Combinations(length))
    {
        foreach (var permutation in combination.Permutations())
        {
            List<Card> Targets = new List<Card>(permutation);
            Out.Add(new GameDecision() { Type = GameDecisionType.PlayCard, TheCard = SpellCard, Targets = Targets });
        }
    }
}

Answer 3

This looks mainly like a terminology problem. It's ambiguous from your question, but it appears that what you're looking for is neither a Cartesian product (n^2 elements when joining the set with itself) nor the Combinations (n choose r).

Rather, to fill in your blank above you need to generate the set of non-empty subsets of a set. That should point you in some kind of direction.

I won't say the right direction, because this approach seems flawed. The cardinality of your result will be 2^n - 1. Once your deck of cards starts to get interesting and you get past 20 or so results from GetPossibleTargets() things are going to get hairy, and quickly. I would suggest looking at your use cases for List<GameDecision> Out and finding a more performant way to approach the problem.