Генерация перестановок, которые не являются зеркалами друг друга
Я хочу генерировать перестановки из n чисел, где нет двух перестановок, которые являются реверсиями друг друга (первая, считанная с последнего символа на первый, такая же, как и вторая). Например, n = 3, я хочу сгенерировать:
1 2 3 //but not 3 2 1
1 3 2 //but not 2 3 1
2 1 3 //but not 3 1 2
Мне все равно, какой из двух будет сгенерирован. Алгоритм должен быть применим для больших n (> 20). Есть ли такой алгоритм или способ проверить, является ли сгенерированная перестановка зеркалом ранее сгенерированной?
Решение
использование std::next_permutation и игнорировать перестановки, первый элемент которых больше, чем его последний.
Другие решения
Нет, обычным аппаратным и программным обеспечением до сегодняшнего дня вы не можете этого сделать, потому что число таких перестановок равно 20! / 2> 10 ^ 10 * 2 ^ 20, что означает, что вам нужно много лет для их генерации.
detector