Geek asks and answers

Permutation Algorithms in C #

I am struggling with this algorithm that I need to write. I am using C #.

Say I have List<Bag>, and I have List<Lunch>. I need to write an algorithm that will list all the permutations of dinners in all packages.

For example, let's say that 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

Two permutations Bag 1 Lunch 1 and Bag 2 Lunch 2and Bag 1 Lunch 2 and Bag 2 Lunch 1different from each other, because the bags have different capacity, so they should both be listed.

The number of bags and dinners can be any number.

I created a class called BagLunchthat contains a pair with a bag and lunch. The list of examples above will be stored in List<BagLunch>.

Thank.

+4
source share
4 answers

LINQ:

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

Edit:
select, BagLunch.

+4

[ ] - , #bags^#lunches.

"",
- "" . .

:

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

, k n (k = bags, n = lunches), ? , , k <= n, ...

, . . , k-1. , , .

EDIT:

, . , n ^ k. - LINQ, , . K , . N, reset . K- -N. .

0

, . ... , , 11, 12,13,21,22,23. . : fooobar.com/questions/395968/..., , , , - . , , 0 . .

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

:

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
0

More articles:


All Articles