Алгоритм нахождения перестановок

[Winer]

Алгоритм нахождения перестановок

Не подскажет ли всеведущий All каким образом можно найти все перестановки N элементов ???

 

[Demiurg]

http://apollyon1986.narod.ru/docs/TViMS/NP/lekziitv/LEKZIYA1.HTM

-~{}~ 05.07.04 16:32:

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

 

[Winer]

Demiurg
вроде бы понял, попробую разобраться, спасибо.

 

[valyala]

Вообще-то можно и без рекурсии обойтись.

// возвращает массив всех перестановок из $n элементов
function get_perestanovka($n)
{
    $result = array(); // массив результатов
    if ($n <= 0) return $result;
    $a = array_fill(0, $n, -1);
    $i = 0;

    while ($i >= 0) {
        while ($i < $n) {
            // ищем первый неиспользованный еще элемент
            $j = $a[$i];
            while (in_array(++$j, $a) && $j < $n);
            if ($j == $n) break; // все перестановки перебраны
            // записываем его на текущую позицию
            $a[$i++] = $j;
        }
        if ($i == $n) {
            array_push($result, $a); // сформировалась перестановка
            $i--;
        }
        $a[$i--] = -1;
    }

    return $result;
}
/****************************************************/
// пример использования
/****************************************************/

print_r(get_perestanovka(2)); // 2 перестановки из двух элементов
print_r(get_perestanovka(5)); // 120 перестановок из пяти элементов
print_r(get_perestanovka(100)); // 100! перестановок из 100 элементов :)