Все комбинации списка объектов. Все объекты вплоть до одинокого - PullRequest
Новая
       7

Все комбинации списка объектов. Все объекты вплоть до одинокого

0 голосов
/ 03 июля 2018

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

Мне нужна функция, которая берет список, а затем возвращает список со списком всех этих комбинаций. Списки должны быть комбинациями со всеми объектами вплоть до одного-единственного объекта.

Пример: 

fun(new List<obj> {objA, objB, objC});

Должен вернуться 

public List<List<obj>> fun(List<obj> L){

...

return List{
            List{objA},
            List{objB},
            List{objC},
            List{objA, objB},
            List{objA, objC},
            List{objB, objC},
            List{objA, objB, objC};
}

И я не знаю заранее, как долго будет составлен список.

Я знаю математическое выражение

п! / к! (П-к)! + п! / (к-1)! (П (к-1))! + ... + n! / 1! (П-1)!

Где n - количество доступных объектов, а k - количество их, которые вы хотите объединить. Результатом этого вычисления будет номер List , который будет включен в возвращенный список

Но, как я уже сказал, мне не удалось получить что-то разумное в коде.

Я использую c #, поэтому предпочитаю ответы на этом языке. Но всякая помощь приветствуется.

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

Ответы [ 2 ]

0 голосов
/ 03 июля 2018

Я не уверен насчет производительности, но с точки зрения читабельности это лучшее, что я придумал - с помощью пары вложенных циклов и linq Skip and Take: 

var source = new List<int>() { 1, 2, 3 };
var target = new List<List<int>>();


for(var i = 0; i < source.Count; i++)
{
    for(var j = i; j < source.Count; j++)
    {
        target.Add(new List<int>(source.Skip(i).Take(source.Count - j)));
    }
}

Вы можете увидеть живое демо на rextester

0 голосов
/ 03 июля 2018

Вы можете использовать интегральное значение для подсчета всех комбинаций.

Затем для каждого значения проверьте каждый бит в числе. Каждый бит 1 означает, что соответствующий элемент включен в комбинацию.

Если вы подумаете о том, как работают двоичные числа, вы поймете, как работает этот алгоритм. Например, для 3 элементов у вас будет 3-битное двоичное число, которое идет от 001 до 111, причем каждый из 3 битов соответствует одному из элементов, например: 

001
010
011
100
101
110
111

Вы должны увидеть, как мы можем использовать каждый бит, чтобы решить, включен ли соответствующий элемент в эту комбинацию.

Вот пример реализации - это работает, если количество элементов <= 32: </p> 

public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> items)
{
    return Combinations(items.Count).Select(comb => comb.Select(index => items[index]));
}

public static IEnumerable<IEnumerable<int>> Combinations(int n)
{
    long m = 1 << n;

    for (long i = 1; i < m; ++i)
        yield return bitIndices((uint)i);
}

static IEnumerable<int> bitIndices(uint n)
{
    uint mask = 1;

    for (int bit = 0; bit < 32; ++bit, mask <<= 1)
        if ((n & mask) != 0)
            yield return bit;
}

Вы можете проверить это, например, с помощью списка символов A..E: 

IList<char> test = "ABCDE".ToList();

foreach (var comb in Combinations(test))
    Console.WriteLine(string.Concat(comb));

Это выводит: 

A
B
AB
C
AC
BC
ABC
D
AD
BD
ABD
CD
ACD
BCD
ABCD
E
AE
BE
ABE
CE
ACE
BCE
ABCE
DE
ADE
BDE
ABDE
CDE
ACDE
BCDE
ABCDE

Если вы хотите превратить IEnumerable<IEnumerable<T>> в List<List<T>>, просто сделайте следующее: 

List<List<T>> list = Combinations(inputList).Select(x => x.ToList()).ToList();

Например, для List<char> выше: 

List<List<char>> list = Combinations(test).Select(x => x.ToList()).ToList();
...