Алгоритм вычисления перестановок

Question

Я знаю алгоритм Кучи для вычисления перестановок заданной последовательности, но что, если бы я хотел рассчитать перестановки подмножества k-элементов для данной последовательности N?

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

Answer 1

1. Используйте алгоритм для генерации комбинаций размера K из множества N. (Выберите любой из SO вопроса: Algorithm to return all combinations of k elements from n).
2. Используя результат, примените Heap's Algorithm для создания всех перестановок этого подмножества k-элементов (или другого Algorithm to generate all possible permutations of a list).
3. Создайте следующее подмножество размера K и повторите (шаги 1 и 2) до тех пор, пока не будут перечислены все подмножества размера K.