комбинация чисел из разных групп

Question

У меня есть 5 групп, каждая из которых имеет 4 разных номера;Я хочу сделать все возможные комбинации (каждая из которых имеет 4 номера) так, чтобы 2 номера были выбраны из одной группы, а остальные числа (по одному) из оставшихся групп.Я искал во многих местах и ​​успешно написал код для выбора комбинаций из 1 группы, но изо всех сил пытался найти решение вышеупомянутого сценария.Кто-нибудь может дать некоторые указания на это?Спасибо за помощь!

ввод: -

Group 1: 1,2,3,4
Group 2: 7,8,9,10
Group 3: 15,16,17,18
Group 4: 22,23,24,25
Group 5: 27,28,29,30

Ожидаемый вывод: -

1,2,7,15 (2 numbers from group 1 and 1 each from group 2 and 3)
7,8,1,22 (2 numbers from group 2 and 1 each from group 1 and 4)

и т. Д. *

Ниже приведеномой код: -

private static bool NextCombination(IList<int> num, int n, int k)
      {
         bool finished;

         var changed = finished = false;

         if (k <= 0) return false;

         for (var i = k - 1; !finished && !changed; i--)
         {
            if (num[i] < n - 1 - (k - 1) + i)
            {
               num[i]++;

               if (i < k - 1)
                  for (var j = i + 1; j < k; j++)
                     num[j] = num[j - 1] + 1;
               changed = true;
            }
            finished = i == 0;
         }


     return changed;
  }

  private static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
  {
     var elem = elements.ToArray();
     var size = elem.Length;

     if (k > size) yield break;

     var numbers = new int[k];

     for (var i = 0; i < k; i++)
        numbers[i] = i;

     do
     {
        yield return numbers.Select(n => elem[n]);
     } while (NextCombination(numbers, size, k));
  }


  private static void Main()
  {
     const int k = 3;
     var n = new[] {"1", "2", "3", "4", "5"};

     Console.Write("n: " );
     foreach (var item in n)
     {
        Console.Write("{0} ", item);
     }
     Console.WriteLine();
     Console.WriteLine("k: {0}", k);
     Console.WriteLine();

     foreach (IEnumerable<string> i in Combinations(n, k))
        Console.WriteLine(string.Join(" ", i));
  }
}

Answer 1

Вот фрагмент кода, который выполняет то, что кажется необходимым:

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

public class Program
{
    class SelectedGroups<T>
    {
        public readonly IList<T> Choose2; // group to Chose 2 elements from
        public readonly IList<T> Choose1_1; // first group to Chose 1 element from
        public readonly IList<T> Choose1_2; // second group to Chose 1 element from

        public SelectedGroups(IList<T> choose2, IList<T> choose11, IList<T> choose12)
        {
            Choose2 = choose2;
            Choose1_1 = choose11;
            Choose1_2 = choose12;
        }
    }

    static IEnumerable<SelectedGroups<T>> ChooseGroups211<T>(IList<IList<T>> groups)
    {
        for (var i = 0; i < groups.Count; i++)
        {
            var outer = groups[i];
            for (var j = 0; j < groups.Count - 1; j++)
            {
                if (i == j)
                    continue;
                var first = groups[j];
                // start from j+1 so  k > j so groups[k] and groups[j] cover all the groups pairs excactly once
                for (var k = j + 1; k < groups.Count; k++) 
                {
                    if (i == k)
                        continue;
                    yield return new SelectedGroups<T>(outer, first, groups[k]); ;
                }
            }
        }
    }

    public class SelectionResult<T>
    {
        public readonly T Value11; // first value from the group #1
        public readonly T Value12; // second value from the group #1
        public readonly T Value3; // value from the group #2
        public readonly T Value4; // value from the group #3


        public SelectionResult(T value11, T value12, T value3, T value4)
        {
            Value11 = value11;
            Value12 = value12;
            Value3 = value3;
            Value4 = value4;
        }

        public override string ToString()
        {
            return string.Format("{0} {1} {2} {3}", Value11, Value12, Value3, Value4);
        }
    }

    static IEnumerable<SelectionResult<T>> Select211FromGroups<T>(SelectedGroups<T> groups)
    {
        for (var i = 0; i < groups.Choose2.Count - 1; i++)
        {
            var value11 = groups.Choose2[i];
            // start from i+1 so  j > i so groups.Choose2[i] and groups.Choose2[j] cover all the pairs excactly once
            for (var j = i + 1; j < groups.Choose2.Count; j++)
            {
                var value12 = groups.Choose2[j];
                foreach (var value3 in groups.Choose1_1)
                {
                    foreach (var value4 in groups.Choose1_2)
                    {
                        yield return new SelectionResult<T>(value11, value12, value3, value4);
                    }
                }

            }
        }
    }

    public static IEnumerable<SelectionResult<T>> Select211<T>(IList<IList<T>> groups)
    {
        return ChooseGroups211(groups).SelectMany(g => Select211FromGroups(g));
    }

    public static void Main(string[] args)
    {
        //PrintHex(4);
        List<int> g1 = new List<int>() { 1, 2, 3, 4 };
        List<int> g2 = new List<int>() { 7, 8, 9, 10 };
        List<int> g3 = new List<int>() { 15, 16, 17, 18 };
        List<int> g4 = new List<int>() { 22, 23, 24, 25 };
        List<int> g5 = new List<int>() { 27, 28, 29, 30 };

        var allGroups = new List<IList<int>>() { g1, g2, g3, g4, g5 };

        foreach (var selectionResult in Select211(allGroups))
        {
            Console.WriteLine(selectionResult);
        }
    }
}

См. онлайн-демонстрация .

Идея кода заключается в следующем:

1. Сначала выберите из всех групп 3, чтобы выбрать элементы.Т.е. генерировать IEnumerable всего такого SelectedGroups.Это делается по методу ChooseGroups211.Важным моментом здесь является то, что Choose1_1 и Choose1_2 полностью симметричны, поэтому вы хотите выбрать только одну из двух пар (Gi, Gj) и (Gj, Gi).

2. Из каждого фиксированного SelectedGroups производят все комбинации из 4 элементов (SelectionResult<T>).Это делается методом Select211FromGroups.Снова Value11 и Value12 симметричны, поэтому вы хотите выбрать только одну из двух пар.

3. Используйте SelectMany, чтобы объединить эти строительные блоки вметод, который делает то, что вы хотите - Select211.

Примечания : этот код довольно прост, но в то же время он довольно жестко запрограммирован для этой конкретной задачито есть выбор ровно 4 элементов как 2 + 1 + 1. Это позволило мне использовать именованные типы вместо IEnumerable<T> для результатов и промежуточных результатов, которые я обычно предпочитаю.Если бы требования были другими, я бы, вероятно, использовал бы общий IEnumerable или массив T[] и некоторые более продвинутые трюки, такие как Вычисление декартового произведения с помощью LINQ