LINQ реализация декартового произведения с обрезкой

Question

Я надеюсь, что кто-то сможет помочь мне с тем, что, по крайней мере для меня, довольно сложный алгоритм.

Проблема

У меня есть список (1 <= size <= 5, но размернеизвестно до времени выполнения) списков (1 <= size <= 2), которые мне нужно объединить.Вот пример того, на что я смотрю: -

ListOfLists = { {1}, {2,3}, {2,3}, {4}, {2,3} }

Итак, мне нужно сделать 2 этапа: -

(1).Мне нужно объединить внутренние списки таким образом, чтобы любая комбинация имела ровно ОДИН элемент из каждого списка, то есть возможные комбинации в наборе результатов здесь были бы: -

• 1,2,2,4,2
• 1,2,2,4,3
• 1,2,3,4,2
• 1,2,3,4,3
• 1,3,2,4,2
• 1,3,2,4,3
• 1,3,3,4,2
• 1,3,3,4,3

Декартово произведение позаботится об этом, поэтому этап 1 завершен ..... теперь, вот поворот, который я не могу понять- по крайней мере, я не могу понять способ LINQ сделать это (я все еще новичок LINQ).

(2).Теперь мне нужно отфильтровать дубликаты результатов этого декартова произведения.Дубликат в этом случае представляет собой любую строку в наборе результатов с тем же количеством каждого отдельного элемента списка, что и другая строка, то есть

1,2,2,4,3 - это то же самое, что и 1, 3,2,4,2

, поскольку каждый отдельный элемент в первом списке встречается одинаковое количество раз в обоих списках (1 встречается один раз в каждом списке, 2 встречается дважды в каждом списке, ....

Поэтому итоговый набор результатов должен выглядеть следующим образом ...

• 1,2,2,4,2
• 1,2,2,4,3
• -
• 1,2,3,4,3
• -
• -
• -
• 1,3,3,4,3

Другим примером является сценарий наихудшего случая (с комбинированной точки зрения), где ListOfLists равен {{2,3}, {2,3}, {2,3}, {2,3}, {2,3}}, то есть список, содержащий внутренние списки максимального размера - в этом случае, очевидно, будет 32 результата в результате декартового произведения.установлен, но сокращенный набор результатов, который я пытаюсь получить, будет просто: -

• 2,2,2,2,2
• 2,2,2,2,3 <- все остальные результаты с четырьмя 2 и одним 3 (в любом порядке) подавляются </li>
• 2,2,2,3,3 <- все остальные результаты стри 2 и 2 3 подавляются и т. д. </li>
• 2,2,3,3,3
• 2,3,3,3,3
• 3,3,3, 3,3

Любым математически настроенным людям - надеюсь, вы поможете.На самом деле у меня есть рабочее решение для части 2, но это полный взлом и требует больших вычислительных ресурсов, и я ищу руководство по поиску более элегантного и эффективного решения LINQ для решения проблемы сокращения.

Спасибо за чтение.

pip

Некоторые ресурсы, использованные до сих пор (чтобы получить декартово произведение)

• computing-a-cartesian-product-with-linq
• c-перестановка массива массивов
• msdn

ОБНОВЛЕНИЕ - Решение

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

Answer 1

Вы должны реализовать свой собственный IEqualityComparer<IEnumerable<int>>, а затем использовать его в Distinct().

Выбор хеш-кода в IEqualityComparer зависит от ваших реальных данных, но я думаю, что что-то вроде этого должно быть адекватным, если ваши фактические данные похожи на те, что в ваших примерах:

class UnorderedQeuenceComparer : IEqualityComparer<IEnumerable<int>>
{
    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        return x.OrderBy(i => i).SequenceEqual(y.OrderBy(i => i));
    }

    public int GetHashCode(IEnumerable<int> obj)
    {
        return obj.Sum(i => i * i);
    }
}

Важной частью является то, что GetHashCode() должно быть O (N), сортировка будет слишком медленной.

Answer 2

Окончательное решение для всего объединения мультимножеств, а затем обрезка наборов результатов для удаления дубликатов проблема оказалась в классе помощника в качестве статического метода. Он принимает высоко ценимый ответ svick и вводит зависимость IEqualityComparer в существующий ответ CartesianProduct, который я нашел в блоге Эрика Липпертса здесь (я бы рекомендовал прочитать его пост, поскольку он объясняет итерации в его мышлении и почему подразумевается linq самый лучший).

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sequences,
                                                       IEqualityComparer<IEnumerable<T>> sequenceComparer)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    var resultsSet = sequences.Aggregate(emptyProduct, (accumulator, sequence) => from accseq in accumulator
                                                                                  from item in sequence
                                                                                  select accseq.Concat(new[] { item }));

    if (sequenceComparer != null)
        return resultsSet.Distinct(sequenceComparer);
    else
        return resultsSet;
}

Answer 3

void Main()
{
    var query =     from a in new int[] { 1 }
                    from b in new int[] { 2, 3 }
                    from c in new int[] { 2, 3 }
                    from d in new int[] { 4 }                   
                    from e in new int[] { 2, 3 }
                    select new int[] { a, b, c, d, e }; 
    query.Distinct(new ArrayComparer());
        //.Dump();
}
 public class ArrayComparer : IEqualityComparer<int[]>
    {
        public bool Equals(int[] x, int[] y)
        {            
            if (x == null || y == null)
                return false;

            return x.OrderBy(i => i).SequenceEqual<int>(y.OrderBy(i => i));

        }

        public int GetHashCode(int[] obj)
        {
            if ( obj == null || obj.Length == 0)
                return 0;
            var hashcode = obj[0];
            for (int i = 1; i < obj.Length; i++)
            {
                hashcode ^= obj[i];
            }
            return hashcode;
        }
    }