Next permutation in lexicographic order n k

Question

I'm want to write function that returns next permutation in lexicographic order n choose k.

So far I found following algorithm


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");
        }
    }

}

But it works only with n up to 13 and then gets every slow. I need to make it work for n=62 and k=6. Is it possible to do it?

Can you please share the some of inputs and expected outputs? — Ankit Gupta, May 21 '19 at 09:02
@AnkitGupta, there are no input, you can see output by running run method. — ogbofjnr, May 21 '19 at 09:08
See https://stackoverflow.com/questions/40752319/algorithm-to-list-unique-permutations-of-string-with-duplicate-letters/40756214#40756214 — Matt Timmermans, May 21 '19 at 14:50
You are talking about permutations but mention `n choose k`, so perhaps you need combinations? — MBo, May 21 '19 at 15:46
@MattTimmermans, I need n choose k where order matters, thought it is permutations or variations — ogbofjnr, May 21 '19 at 16:00
@Mark Could you show expected result for `(A,B,C), n=3,k=2` to be sure what combinatorial object is needed? — MBo, May 21 '19 at 16:19
@MattTimmermans, `0) A B 1) A C 2) B A 3) B C 4) C A 5) C B ` — ogbofjnr, May 22 '19 at 07:22

MBo · Accepted Answer · 2019-05-22T11:44:28.723

This combinatorial object has no specific name in English combinatorics, in Russian and French combinatoric terminology it is called "arrangements" A(n,k)

There are 44 261 653 680 arrangements A(62,6) - so their generation and output (~500 GB) takes too long time. In compiled languages like C/C++/Delphi generation (without ouput) perhaps should take about some hours (rough estimation 10^6-10^7 results per second), but this process ought to be slower in PHP (interpreted language).

Your code uses algorithm for usual permutations that generates n! results against needed n!/(n-k)! arrangements.

Simple recursive Python code for generation of arrangements. Works ~3 seconds for n=25,k=5. Not optimal, will check better in the book.

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]

It is not about spaces, once I increase n to 15, `nextPermutation()` is working too long, calculating single permutation. — ogbofjnr, May 22 '19 at 08:15
I understandnow . You are using algorithm to make pure permutations, **n!** of them, and use k-length beginning. Algo intended for arrangements works much faster. Will make example later. Are you capable to read Delphi or Python code? — MBo, May 22 '19 at 09:05
Yeah, exactly. And the question was is there any other algorithm that could do it faster.Yes, I can read Python. — ogbofjnr, May 22 '19 at 10:38

Next permutation in lexicographic order n k

1 Answers1

Linked