Алгоритм определения вариаций разной длины

Question

У меня есть четыре объекта - ради аргументов, скажем, что это следующие буквы: A B C D

Мне нужно рассчитать количество вариантов, которые могут быть сделаны для них при следующих двух условиях:

1. Нет повторений
2. Объекты позиционно независимы

Принимая выше, это означает, что с четырьмя объектными последовательностями у меня может быть только одна последовательность, которая соответствует критериям (поскольку порядок не считается уникальным):

• ABCD

Существует четыре варианта комбинации трех объектов из пула четырех объектов:

• ABC, ABD, ACD и BCD

Существует шесть вариантов комбинации двух объектов из пула четырех объектов:

• AB, AC, AD, BC, BD и CD

И самый простой, если он применяется одновременно:

• A, B, C и D

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

Любой совет будет принят.

Answer 1

Существует 2 ^ n комбинаций из n объектов, где каждый объект может быть (в наборе) или (не в наборе).Таким образом, вы можете рассматривать каждую комбинацию в наборе комбинаций как одно целое число в диапазоне (0, (2^n-1)).

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

В сторону: это называется power set .

Answer 2

То, о чем вы думаете, называется комбинацией, а количество комбинаций k в группе из n элементов равно

n!/((n-k)!k!)

При обращении к числу комбинаций принято говорить "n выбирают k", поскольку вы по сути "выбираете" k элементов из n.

РЕДАКТИРОВАТЬ: Ах, я неправильно прочитал. Вы хотите подсчет всех возможных комбинаций, по сути, сумма (nCk, k = 0 до n). Это набор мощности, равный 2 ^ n (или 2 ^ n - 1, если вы не хотите считать пустой набор).