Блог

У меня возникли некоторые проблемы с решением алгоритма, используемого для поиска всех возможных комбинаций, берущих элементы из N различных списков (где N> = 2 amp;amp; N <=7 -> это число фиксировано, и я могу создать другой метод для каждого N). Проблемы заключаются в следующем: у меня есть пять словарей:

 IDictionary<int, MyEnum> listOne; 
IDictionary<int, MyEnum> listTwo;
IDictionary<int, MyEnum> listThree;
IDictionary<int, MyEnum> listFour;
IDictionary<int, MyEnum> listN;

enum MyEnum
    {
    MyEnumOne,
    MyEnumTwo,
    MyEnumThree,
    MyEnumFour,
    MyEnumFive,
    MyEnumOther
   }
  

который может содержать любое количество элементов (не более 100, и в большинстве случаев они будут содержать от 32 до 64 элементов)
и где MyEnum — это простое перечисление имен с некоторыми значениями.

Для каждой возможной комбинации у меня есть некоторый метод, который проверяет комбинацию и проверяет, удовлетворяет ли она некоторым условиям, и если они выполняются, сохраняет некоторые данные на основе комбинации.

Я пробовал простые вложенные итерации, используя foreachs для каждого списка, которые, как и ожидалось, выполняются годами!

Любая помощь, например, с чего мне следует начать, что я должен делать, или событие, которое я не должен делать, будет более чем приветствоваться!, также, если требуется дополнительная информация, пожалуйста, не стесняйтесь спрашивать!

** РЕДАКТИРОВАТЬ: комбинация, основанная на пяти списках, как показано ранее, будет, например:

 (MyEnumOne, MyEnumOne, MyEnumFour, MyEnumFive, MyEnumTwo)
  

и, поскольку эта комбинация может появляться несколько раз (поскольку значение MyEnumOne может быть много раз в listOne и т.д.), Я также должен вести учет того, сколько раз встречается эта комбинация.

Вы можете легко решить такого рода проблемы с помощью LINQ.

 var solutions = from pair1 in listOne
                where IsCandidate(pair1)
                from pair2 in listTwo
                where IsCandidate(pair1, pair2)
                from pair3 in listThree
                where IsCandidate(pair1, pair2, pair3)
                from pair4 in listFour
                where IsCandidate(pair1, pair2, pair3, pair4)
                from pair5 in listFive
                where IsCandidate(pair1, pair2, pair3, pair4, pair5)
                from pair6 in listSix
                where IsCandidate(pair1, pair2, pair3, pair4, pair5, pair6)
                from pair7 in listSeven
                where IsSolution(pair1, pair2, pair3, pair4, pair5, pair6, pair7)
                select new { pair1, pair2, pair3, pair4, pair5, pair6, pair7 };
  

Конечно, этот подход допустим только потому, что количество списков известно во время компиляции. Альтернативным подходом было бы иметь общий способ построения возможных комбинаций, как показывает Эрик Липперт в своем посте.

Все эти промежуточные элементы where по всему запросу предназначены для того, чтобы как можно скорее отфильтровать недопустимые комбинации.

Редактировать

Исправлено решение для эффективного подсчета того, сколько раз встречается одна и та же комбинация, игнорируя ключи исходного источника.

Для достижения этого я собираюсь применить преобразование к каждому словарю. Я собираюсь преобразовать каждый словарь в новый словарь, где ключом будет значение enum, а значением будет количество раз, когда значения enum встречаются в исходном словаре.

 IDictionary<MyEnum, int> CountOccurrences(IEnumerable<MyEnum> values)
{
    return (from e in values group e by e).ToDictionary(grp => grp.Key, grp => grp.Count());
}

var solutions = from p1 in CountOccurrences(listOne.Values)
                where IsCandidate(p1)
                from p2 in CountOccurrences(listTwo.Values)
                where IsCandidate(p1, p2)
                from p3 in CountOccurrences(listThree.Values)
                where IsCandidate(p1, p2, p3)
                from p4 in CountOccurrences(listFour.Values)
                where IsCandidate(p1, p2, p3, p4)
                from p5 in CountOccurrences(listFive.Values)
                where IsCandidate(p1, p2, p3, p4, p5)
                from p6 in CountOccurrences(listSix.Values)
                where IsCandidate(p1, p2, p3, p4, p5, p6)
                from p7 in CountOccurrences(listSeven.Values)
                where IsSolution(p1, p2, p3, p4, p5, p6, p7)
                select new {
                    E1 = p1.Key,
                    E2 = p2.Key,
                    E3 = p3.Key,
                    E4 = p4.Key,
                    E5 = p5.Key,
                    E6 = p6.Key,
                    E7 = p7.Key,
                    Times = p1.Value * p2.Value * p3.Value * p4.Value * p5.Value * p6.Value * p7.Value
                };
  

Как правило, с такими проблемами вам следует пытаться конструировать решения, а не вслепую перебирать все пространство поиска в их поисках.

Я предполагаю, что вам действительно нужно сделать следующее: — у вас есть N списков, каждый список i содержит L (i) элементов. — вы хотите сгенерировать все комбинации длины N, где первый элемент происходит из первого списка, второй элемент из второго списка и так далее.

Кажется, нет никакого способа избежать генерации всех комбинаций сложным способом. Все 100 элементов ^ N ~ 10 ^ 14 … на что уйдут эоны.

Я поддерживаю запрос на небольшие выборки и условия, которые должны быть выполнены.