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.

I don't understand your example. There are several rows that list Bag 1, Lunch 1. What are the rules for duplicates in the permutations? — Ted Hopp
– Ted Hopp, Commented Feb 6, 2012 at 22:28
I don't think there are duplicates? You can either have lunch 1 in bag 1 and lunch 2 in bag 2, or you can have lunch 2 in bag 1 and lunch 1 in bag 2. These are two different permutations. — user1002358
– user1002358, Commented Feb 6, 2012 at 22:31
Thanks for adding the homework tag zmbq, but this isn't homework. — user1002358
– user1002358, Commented Feb 6, 2012 at 22:34
@Marty Is it so difficult to believe that such a problem may actually arise in a real problem? — user1002358
– user1002358, Commented Feb 6, 2012 at 22:53

Randolpho · Accepted Answer · 2012-02-06 22:39:39Z

4

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.

edited Feb 6, 2012 at 22:39

answered Feb 6, 2012 at 22:33

Randolpho

56.5k18 gold badges153 silver badges182 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Kirk Broadhurst Over a year ago

Good answer; OP will then have to group the result by 'bag' and then cross join those groups against each other.

user1002358 Over a year ago

I'm new to LINQ, but I've just run your example. It give the same result as a nested for or foreach: B1L1, B1L2, B1L3, B2L1, B2L2, B2L3. This isn't what I need :(

zmbq Over a year ago

That'll work, but it feels a little bit like cheating, even if this isn't homework.

Randolpho Over a year ago

@user1002358 I guess I misunderstand what you need. That gives you all permutations of bag and lunch. For a 2x3 set, there are only 6 permutations.

amit Over a year ago

Let k = #bags and n = #lunches. There are n!/(n-k)! possibilities to do it if you allow each lunch to be "assigned" to only one bag. The op in here allows to each lunch to be assigned to more then one bag, thus there are k^n possibilities to do it.

|

amit · Accepted Answer · 2012-02-06 22:31:51Z

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()

answered Feb 6, 2012 at 22:31

amit

179k27 gold badges245 silver badges348 bronze badges

Comments

zmbq · Accepted Answer · 2012-02-06 22:41:28Z

0

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.

edited Feb 6, 2012 at 22:41

answered Feb 6, 2012 at 22:31

zmbq

39.1k15 gold badges109 silver badges188 bronze badges

3 Comments

Kirk Broadhurst Over a year ago

In this example lunches are replaceable - they can be used in multiple bags.

user1002358 Over a year ago

That's right. I can have 10 bags and 1 lunch. In this case there is only 1 permutation: All 10 bags contain lunch 1.

zmbq Over a year ago

You should really stop calling this a permutation. There's one combination.

Community · Accepted Answer · 2017-05-23 12:27:29Z

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

Collectives™ on Stack Overflow

Permutation algorithms in C#

4 Answers 4

6 Comments

Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

6 Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related