Алгоритмы перестановки в C #

Question

Я борюсь с этим алгоритмом, который мне нужно написать.Я использую C #.

Скажем, у меня есть List<Bag>, и у меня есть List<Lunch>.Мне нужно написать алгоритм, который будет перечислять все перестановки обедов во всех пакетах.

Например, скажем, есть 3 обеда и 2 пакета:

// 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

Две перестановки Bag 1 Lunch 1 and Bag 2 Lunch 2и Bag 1 Lunch 2 and Bag 2 Lunch 1 различны, потому что пакеты имеют разную вместимость, поэтому их нужно будет перечислить.

Количество пакетов и обедов может быть любым числом.

Я создал классназывается BagLunch, который содержит сумку и обеденную пару.Список приведенных выше примеров будет храниться в List<BagLunch>.

Спасибо.

Answer 1

Использование перекрестного соединения в 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.

Answer 2

Если вы разрешите одноклассников [обед может быть в двух пакетах] - как показывает пример, у вас есть #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()

Answer 3

У меня есть метод, который воссоздает ваш пример выше. Подход на самом деле заключается в том, чтобы думать о сумках как о позициях числа ... поскольку, если вы посмотрите на свой пример, вы можете прочитать его как 11, 12,13,21,22,23. Тогда это вопрос конвертации в базовый Lunch.Count. Также я украл здесь метод: https://stackoverflow.com/a/95331/483179 для преобразования в любую базу, о которой упоминалось, что она не была проверена, поэтому вам, возможно, придется создать что-то более надежное. Наконец, я не проводил тестирование краевых условий, поэтому подача в 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

Answer 4

То есть вы хотите выйти из k из n (k = сумки, n = обеды), сохраняя порядок?Я надеюсь, вы можете предположить, что k <= n, иначе вы застрянете с пустыми сумками ... </p>

Я не хочу полностью портить вашу домашнюю работу, поэтому я просто укажу вам направильное направление.Это требует рекурсии.Сначала выберите обед для первой сумки, затем выберите обеды для оставленных сумок k-1.Если у вас осталась только одна сумка, выбирайте каждый из оставшихся обедов, пока не закончите.

РЕДАКТИРОВАТЬ:

О, обед может находиться в двух пакетах одновременно.Так что это п ^ к.Самый короткий путь - использовать перекрестное соединение LINQ, предложенное выше, но это похоже на читерство.Вместо этого просто создайте целочисленный массив из K элементов, заполните его нулями и начните добавлять один к крайнему правому элементу.Когда вы доберетесь до N, сбросьте его на ноль и перенесите один к следующему элементу.Ты просто считаешь K-цифры в base-N.После каждой итерации вы можете выводить назначение сумки.