Начните с более простой задачи. Сколько существует уникальных комбинаций ноль Y или N? Там только один: комбинация, которая не содержит элементов.
Сколько существует уникальных комбинаций один Y или N? Их два:
N Y
Сколько существует уникальных комбинаций двух Y или N? Их четыре:
NN NY YN YY
Три? Их восемь:
NNN NNY NYN NYY YNN YNY YYN YYY
0 имеет 1, 1 имеет 2, 2 имеет 4, 3 имеет 8, ... Вы уже должны были догадаться, что есть две к k комбинациям k Y Ns.
Мы формируем новые комбинации из старых комбинаций по следующему алгоритму:
- Если у нас ноль элементов, результатом будет пустой список.
- Если у нас k> 0 элементов, составьте список из k-1 элементов. «Удвойте» список и добавьте в каждую пару N или Y.
Если последний пример не ясен, давайте снова посмотрим на 3. Начнем с решения задачи за 2:
NN NY YN YY
Тогда мы удваиваем это
NN NN NY NY YN YN YY YY
Затем мы добавляем N, Y, N, Y, N, Y, N, Y, чтобы получить
NNN NNY NYN NYY YNN YNY YYN YYY
В языках данных эта операция является декартовым произведением последовательности с самим . Это также называется «перекрестным соединением», потому что оно обозначается в алгебре крестиком X. Это {N,Y} x {N,Y} x {N,Y} x {N,Y} x {N,Y}.
УПРАЖНЕНИЕ: Как бы вы сделали это для последовательности с тремя элементами, {A, B, C}? Сколько существует комбинаций k элементов?
УПРАЖНЕНИЕ: Сколько существует способов упорядочить 10 Y-или-N, чтобы их было ровно 5? Как бы вы получили эти комбинации? Опять же, начните с более простой задачи и объясните свой путь к более сложной проблеме .
ДАЛЬНЕЙШЕЕ ЧТЕНИЕ: Если вас интересует, как выполнять эти операции в C #, за эти годы я написал много статей о них:
https://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/
https://ericlippert.com/2013/04/15/producing-permutations-part-one/
https://ericlippert.com/2014/10/13/producing-combinations-part-one/