Нахождение n-й перестановки без вычисления других

Для массива из N элементов, представляющих атомы перестановки, существует ли такой алгоритм:

function getNthPermutation( $atoms, $permutation_index, $size )

где $ atom - это массив элементов, $ permutation_index - это индекс перестановки, а $ size - размер перестановки.

Например:

$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );

echo implode( ', ', $perm )."\n";

Напечатает:

B, A

Без вычисления каждой перестановки до $ permutation_index?

Я слышал кое-что о факторадических перестановках, но каждая найденная мной реализация дает в результате перестановку с тем же размером V, что не в моем случае.

Спасибо.

39
задан Alix Axel 21 June 2012 в 08:40
поделиться