Я пытаюсь написать метод, который будет вычислять все перестановки набора мощности, где порядок имеет значение. Я считаю, что это называется "аранжировки". Под этим я подразумеваю следующее:
{a} -> {{a}, {}}
{a,b} -> {{a,b}, {b,a}, {a}, {b}, {}}
{a,b,c} -> {{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}, {a,b}, {a,c}, {b,a}, {b,c}, {c,a}, {c,b}, {a}, {b}, {c}, {}}
и т. д. У меня сложилось впечатление, что для заданного набора S я должен сгенерировать каждую перестановку каждого подмножества набора мощности S. Итак, сначала сгенерируйте набор мощности, а затем сопоставьте функцию перестановки с каждым набором. .
Проблема в том, что это чрезвычайно сложно — что-то вроде O(∑n!/k!) при k=0..n.
Мне интересно, существуют ли какие-либо существующие алгоритмы, которые делают подобные вещи очень эффективно (возможно, параллельная реализация). Или, возможно, даже если существует параллельный алгоритм набора мощности и существует параллельный алгоритм перестановки, я могу объединить их.
Мысли?