Permutation algorithms in C#

Question

I'm struggling with this algorithm I need to write. I'm using C#.

Say I have a List<Bag> and I have a List<Lunch>. I need to write an algorithm which will enumerate all permutations of lunches in all bags.

For example, say there are 3 lunches and 2 bags:

// Permutation 1
Bag 1, Lunch 1
Bag 2, Lunch 1

// Permutation 2
Bag 1, Lunch 1
Bag 2, Lunch 2

// Permutation 3
Bag 1, Lunch 1
Bag 2, Lunch 3

// Permutation 4
Bag 1, Lunch 2
Bag 2, Lunch 1

// Permutation 5
Bag 1, Lunch 2
Bag 2, Lunch 2

// Permutation 6
Bag 1, Lunch 2
Bag 2, Lunch 3

// Permutation 7
Bag 1, Lunch 3
Bag 2, Lunch 1

// Permutation 8
Bag 1, Lunch 3
Bag 2, Lunch 2

// Permutation 9
Bag 1, Lunch 3
Bag 2, Lunch 3

The two permutations Bag 1 Lunch 1 and Bag 2 Lunch 2 and Bag 1 Lunch 2 and Bag 2 Lunch 1 are different because the bags have different capacities, hence they would both need to be enumerated.

The number of bags and lunches can be any number.

I have created a class called BagLunch which contains a bag and lunch pair. The example list I've given above would be stored in a List<BagLunch>.

Thank you.

Answer 1

Use a cross join in LINQ:

var qry = from bag in bags
          from lunch in lunches
          select new BagLunch 
          { Bag=bag, Lunch=lunch};
var baglunches = qry.ToList();

Edit:
You'll want to modify the select clause to handle the structure of your BagLunch class.

Answer 2

If you allow dupes [a lunch can be in two bags] - as the example suggests you have #bags^#lunches possibilities.

Each bag has its own unique "choice" which lunch to put
To genereate these possibilities - just "choose" a lunch for a bag, and recursively invoke the algorithm. repeat for each lunch.

pseudo code for generating them:

generateAll(bags,lunches,sol):
  if (bags is empty):
      print sol
      return
  bag <- bags.first
  bags.remove(bag)
  for each lunch in lunches:
     sol.append(BagLunch(bag,lunch)
     generateAll(bags,lunches,sol)
     sol.removeLast()

Answer 3

So you want to go over k out of n (k = bags, n = lunches) while keeping the order? I hope you can assume that k<=n, otherwise you're going to get stuck with empty bags...

I don't want to spoil your homework entirely, so I'll just point you in the right direction. This begs for recursion. First choose the lunch for the first bag, then choose the lunches for the k-1 bags that are left. When you have only one bag left, choose each of the remaining lunches until you're done.

EDIT:

Oh, a lunch can reside in two bags at once. So it's n^k. The shortest way would be to use the LINQ cross join suggested above, but it feels a little like cheating. Instead, just create an integer array of K elements, fill it with zeroes, and started adding one to the rightmost element. When you it gets to N, reset it to zero and carry the one to the next element. You're just counting K-digit numbers in base-N. After each iteration, you can output the bag assignment.

Answer 4

I have a method that recreates your example above. The approach is actually to think of the bags as positions of a number... for if you look at your example you could read it as 11, 12,13,21,22,23. Then it's a matter of converting to base Lunch.Count. Also I stole a method from here: https://stackoverflow.com/a/95331/483179 to convert to any base which it was mentioned it was untested so you may have to build something more robust. Finally I didn't do any edge condition testing so feeding in 0 bags could have unexpected results. Here is what I came up with.

class Program
{
    static List<Bag> bags = new List<Bag>();
    static List<Lunch> lunches = new List<Lunch>();

    static void Main(string[] args)
    {
        lunches.Add(new Lunch() { Num = 1 });
        lunches.Add(new Lunch() { Num = 2 });
        lunches.Add(new Lunch() { Num = 3 });
        bags.Add(new Bag() { Num = 1 });
        bags.Add(new Bag() { Num = 2 });

        int count = 0;
        while (count < Math.Pow(lunches.Count, bags.Count))
        {
            Console.WriteLine("Permutation " + count);
            string countNumber = ConvertToBase(count, lunches.Count).PadLeft(bags.Count,'0');
            for (int x = 0; x < bags.Count; x++)
            {
                Console.WriteLine(bags[x] + " " + lunches[Convert.ToInt32((""+countNumber[x]))]);

            }
            Console.WriteLine("");
            count++;
        }
        Console.ReadLine();

    }

    static string ConvertToBase(int value, int toBase)
    {
        if (toBase < 2 || toBase > 36) throw new ArgumentException("toBase");
        if (value < 0) throw new ArgumentException("value");

        if (value == 0) return "0"; //0 would skip while loop

        string AlphaCodes = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        string retVal = "";

        while (value > 0)
        {
            retVal = AlphaCodes[value % toBase] + retVal;
            value /= toBase;
        }

        return retVal;
    }

}

class Lunch
{
    public int Num { get;set;}
    public override string  ToString()
    {
         return "Lunch " + Num;
    }

}
class Bag
{
    public int Num { get;set;}   

    public override string  ToString()
    {
         return "Bag " + Num;
    }
}

and the resultant output:

Permutation 0
Bag 1 Lunch 1
Bag 2 Lunch 1

Permutation 1
Bag 1 Lunch 1
Bag 2 Lunch 2

Permutation 2
Bag 1 Lunch 1
Bag 2 Lunch 3

Permutation 3
Bag 1 Lunch 2
Bag 2 Lunch 1

Permutation 4
Bag 1 Lunch 2
Bag 2 Lunch 2

Permutation 5
Bag 1 Lunch 2
Bag 2 Lunch 3

Permutation 6
Bag 1 Lunch 3
Bag 2 Lunch 1

Permutation 7
Bag 1 Lunch 3
Bag 2 Lunch 2

Permutation 8
Bag 1 Lunch 3
Bag 2 Lunch 3