Следующая перестановка в лексикографическом порядке nk - PullRequest
Новая
       20

Следующая перестановка в лексикографическом порядке nk

0 голосов
/ 21 мая 2019

Я хочу написать функцию, которая возвращает следующую перестановку в лексикографическом порядке n и выберите k.

До сих пор я нашел следующий алгоритм 


class Permutation
{
    public function swap(& $a, $first, $second)
    {
        $tmp = $a[$first];
        $a[$first] = $a[$second];
        $a[$second] = $tmp;
    }


    function nextPermutation(& $a, $n, $k)
    {
        do {
            $first = $n - 2;
            while ($first != -1 && $a[$first] >= $a[$first + 1]) $first--;
            if ($first == -1)
                return false;
            $second = $n - 1;
            while ($a[$first] >= $a[$second]) $second--;
            $this->swap($a, $first, $second);
            $left = $first + 1;
            $right = $n - 1;
            while ($left < $right) {
                $this->swap($a, $left++, $right--);
            }

        } while ($first > $k - 1);
        return true;

    }

    public function run()
    {
        $n=10;
        $k=4;
        $a = array_merge(range(ord(0), ord(9)), range(ord('A'), ord('Z')), range(ord('a'), ord('z')));
        $i = 0;
        while ($this->nextPermutation($a, $n, $k)) {
            $i++;
            echo($i . ")  ");
            for ($j = 0; $j < $k; $j++) {
                echo $a[$j] . " ";
            }
            echo("\n");
        }
    }

}

Но он работает только с n до13, а затем получает каждый медленный.Мне нужно, чтобы это работало для n = 62 и k = 6.Возможно ли это сделать?

1 Ответ

1 голос
/ 21 мая 2019

Этот комбинаторный объект не имеет конкретного имени в английской комбинаторике, в русской и французской комбинаторной терминологии он называется «аранжировки» A (n, k)

Всего существует 44 261 653 680 аранжировок A(62,6) - таких генерация и вывод (~ 500 ГБ) занимает слишком много времени.В скомпилированных языках, таких как генерация C / C ++ / Delphi (без вывода), возможно, это займет около нескольких часов (приблизительная оценка 10 ^ 6-10 ^ 7 результатов в секунду), но этот процесс должен быть медленнее в PHP (интерпретируемый язык).

Ваш код использует алгоритм для обычных перестановок, который генерирует n! результаты для необходимых n!/(n-k)! соглашений.

Простой рекурсивный код Python для генерации устройств.Работает ~ 3 секунды для n = 25, k = 5.Не оптимально, проверю лучше в книге. 

n = 4
k = 2
ar = [0] * k
used = set()

def genArr(idx):
    for i in range(n):
        if not i in used:
            used.add(i)
            ar[idx] = i
            if idx == k - 1:
                print(ar) #comment for large n
            else:
                genArr(idx + 1)
            used.remove(i)

genArr(0)
print('OK')

[0, 1, 2]
[0, 1, 3]
[0, 2, 1]
[0, 2, 3]
......
[2, 3, 1]
[3, 0, 1]
[3, 0, 2]
[3, 1, 0]
[3, 1, 2]
[3, 2, 0]
[3, 2, 1]
...