About Permutations

This is not exactly a WhileDo post - I should really tag these WhileDo and not BuildInPublic - but a reflection of my work on a code kata after the fact.^[1]

Here's is the code kata:

In this kata, your task is to create all permutations of a non-empty input string and remove duplicates, if present.

Create as many "shufflings" as you can!

Examples:

With input 'a':
Your function should return: ['a']

With input 'ab':
Your function should return ['ab', 'ba']

With input 'abc':
Your function should return ['abc','acb','bac','bca','cab','cba']

With input 'aabb':
Your function should return ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

Note: The order of the permutations doesn't matter.

Good luck!

Although it is a problem - not the kata, but "make permutations" - I had probably solved before, whenever I am confronted with "make permutations" in real life, the "algorithm" goes something like this (example here is "ABC"):

1. Say "ABC" in my head
2. Say "ACB" in my head
3. Say "BAC" in my head
4. Say "BCA"
5. be stumped for a moment...
6. Come up with "BCA" again
7. Come up with "BAA"... realize that this is not valid
8. Repeat coming up with possible candidates until none come to mind anymore

This is a terrible "algorithm", because it is non-exhaustive and error prone. And not really something I wanted to implement. In such a situation I tend to just go to Wikipedia (if possible) and look for a standard algorithm. I remember having done so in a coding interview as well.

If you look up permutation and scroll down a little, you'll find:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is zero-based, the steps are as follows:

1. Index k = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 4.
2. Index l = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition a[k] < a[l].
3. The values of a[2] and a[3] are swapped to form the new sequence [1, 2, 4, 3].
4. The sequence after k-index a[2] to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1, 2, 4, 3].

Following this algorithm, the next lexicographic permutation will be [1, 3, 2, 4], and the 24th permutation will be [4, 3, 2, 1] at which point a[k] < a[k + 1] does not exist, indicating that this is the last permutation.

On the first look, this didn't seem so hard to implement. A few problems I encountered:

• I had somehow problems figuring out how to find "the largest index such that <condition>". The largest index is clear, but how exactly do you look for an index like this? The solution I landed on to solve this initially was to just collect candidate indexes that satisfied condition and then just keep the highest one.
• I was not reading carefully enough and only later caught the difference between the k condition and the l condition: F.x.: [1,2,3,1,3]. Index 1 (value 2) would be what k is. The only value that is bigger than 2 is 3, but the biggest index with value 3 is of course not 2 (which happens to be k+1), but 4!
• I somehow completely skipped step 4 initially and ended up with less permutations than the tests. Doh!
• I missed in the paragraph before the one I just quoted that you have to sort the array, before you can start doing things!

Implementing the algorithm took me about 4.5 hours. Here's the super-janky first version that passed the tests:

<?php

//see https://en.wikipedia.org/wiki/Permutation - Generation in lexicographic order
function permutations(string $s): array
{
    if (empty($s)) {
        return [''];
    }
    if (strlen($s) === 1) {
        return [$s];
    }
    /*if (strlen($s) === 2) {
        return [$s, strrev($s)];
    }*/
    //convert to numbers - AABB - 97,97,98,98
    $numArr = getNumArr($s);
    // sort! (doesn't do anything with aabb, but would be needed for bbaa)
    sort($numArr);
    $result = getAll($numArr);
    return array_unique($result);
}

function getAll(array $numArr): array
{
    $initial = $numArr;
    $pms = [$initial];
    while ($next = newSwap($initial)) {
        $pms[] = $next;
        $initial = $next;
    }
    $pmsChar = array_map(fn($p) => getImplodeCharString($p), $pms);
    return $pmsChar;
    $swap1 = swap($numArr);
    $swap2 = swap($swap1);
    $swap3 = swap($swap2);
    $swap4 = swap($swap3);
    $swap5 = swap($swap4);
    $perms = [$numArr, $swap1, $swap2, $swap3, $swap4, $swap5];
    echo "LOL\n";
    print_r($pms);
    print_r($perms);
    print_r($pmsChar);
    echo "LOL\n";
    $permsChar = [
        getImplodeCharString($numArr),
        getImplodeCharString($swap1),
        getImplodeCharString($swap2),
        getImplodeCharString($swap3),
        getImplodeCharString($swap4),
        getImplodeCharString($swap5),
    ];
    print_r($permsChar);
    return $permsChar;
}

function getNumArr(string $s): array
{
    $arr = str_split($s);
    $numArr = array_map(fn(string $char) => ord($char), $arr);
    return $numArr;
}

function getImplodeCharString(array $numArr): string
{
    return implode(array_map(fn(int $num) => chr($num), $numArr));
}

function newSwap(array $numArr): bool|array
{
    // Iterate over all elements to have candidates for k, pick largest one
    $kCandidates = [];
    for ($i = 0; $i < count($numArr); $i++) {
        if ($i === count($numArr) - 1) {
            //can't be the last one
            continue;
        }
        if ($numArr[$i] < $numArr[$i + 1]) {
            $kCandidates[] = $i;
        }
    }
    if (empty($kCandidates)) {
        return false;
    }
    $k = $kCandidates[count($kCandidates)-1];
    // Iterate over all elements to have candidates for l
    // Important we compare values this time.
    // a[k] < a[l]
    // let's say the arr is 97,98,97,98
    // k is 2
    // a[k] = 97
    // largest index pointing to a value bigger than 97 is 3
    // l is 3
    // a[l] = 98
    // new situation: 97,98,98,97
    $lCandidates = [];
    for ($i = 0; $i < count($numArr); $i++) {
        if ($numArr[$i] > $numArr[$k]) {
            $lCandidates[] = $i;
        }
    }
    $l = $lCandidates[count($lCandidates)-1];
    // Swap values of k and l
    $swappedArr = $numArr;
    $temp = $swappedArr[$k];
    $swappedArr[$k] = $swappedArr[$l];
    $swappedArr[$l] = $temp;
    // Reverse array from k onwards
    $reverseAfterK = $swappedArr;
    $toReverse = array_slice($reverseAfterK, $k + 1);
    $reversed = array_reverse($toReverse);
    array_splice(
        array: $reverseAfterK,
        offset: $k + 1,
        replacement: $reversed
    );
    /**
    echo "---\n";
    echo "Orginal Array: ".getImplodeCharString($numArr)."\n";
    // print_r($lCandidates);
    echo "K from Candidates: ".$k." Value: ".$numArr[$k]." Char: ".chr($numArr[$k])."\n";
    echo "L from Candidates: ".$l." Value: ".$numArr[$l]." Char: ".chr($numArr[$l])."\n";
    echo "Swapped Array: ".getImplodeCharString($swappedArr)."\n";
    echo "Reversed After K Array: ".getImplodeCharString($reverseAfterK)."\n";
     **/
    return $reverseAfterK;
}

function swap(array $numArr): bool|array
{
    // call newswap
    return swap($numArr);

    // Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
    // idea: take second last index compare to last index and so forth
    $k = -1;
    $l = -2;
    for ($i = count($numArr) - 1; $i >= 0; $i--) {
        if ($i === count($numArr) - 1) {
            //can't be the last one
            continue;
        }
        if ($numArr[$i] < $numArr[$i + 1]) {
            $k = $i;
            //all infices bigger than


            // ---
            $l = $i + 1; //WRONG
            break;
        }
    }
    // echo "###\n";
    // echo "Orginal Array: ".getImplodeCharString($numArr)."\n";
    // echo "K-Index: ".$k." Value: ".$numArr[$k]." Char: ".chr($numArr[$k])."\n";
    // echo "L-Index: ".$l." Value: ".$numArr[$l]." Char: ".chr($numArr[$l])."\n";
    // swap $k and $l
    $temp = $numArr[$k];
    $numArr[$k] = $numArr[$l];
    $numArr[$l] = $temp;
    // echo "Converted swapped Array: ".getImplodeCharString($numArr)."\n";
    return $numArr;
}

I think we can all agree that this thing is an absolute mess, but I wanted to put it here to show that this is how I worked on the problem. This is why there is a swap function and a newSwap function and getAll returns before some other code would've run and you can see my echo and print_r debugging statements that are commented out. Even my misunderstanding between the conditions for k/l was immortalized.

In non-code form, my way of solving this one goes as follows:

• convert the incoming string into an array of characters
• convert those characters into numbers
• use this array of numbers to use the lexicographic algorithm to find all permutations
• convert all found permutation arrays back to chars and finally join them to strings
• return the array containing these permutations

I turned this messy but working version into a slightly less messy but pretty baroque version, which I then submitted as my solution:

<?php

//see https://en.wikipedia.org/wiki/Permutation - Generation in lexicographic order
function permutations(string $s): array
{
  $solution = new Permutations();
  return $solution->permutations($s);
}

class Permutations
{
    //see https://en.wikipedia.org/wiki/Permutation - Generation in lexicographic order
    public function permutations(string $s): array
    {
        if (empty($s)) {
            return [''];
        }
        if (strlen($s) === 1) {
            return [$s];
        }
        $result = $this->getAllPerms($s);
        return $result;
    }

    private function getAllPerms(string $s): array
    {
        //convert to numbers - AABB - 97,97,98,98
        $numArr = $this->getNumArr($s);
        // sort! (doesn't do anything with aabb, but would be needed for bbaa)
        sort($numArr);

        $initial = $numArr;
        $pms = [$initial];
        while ($next = $this->swap($initial)) {
            $pms[] = $next;
            $initial = $next;
        }

        $result = array_map(fn($p) => $this->getImplodeCharString($p), $pms);
        return array_unique($result);
    }

    private function getNumArr(string $s): array
    {
        $arr = str_split($s);
        $numArr = array_map(static fn(string $char) => ord($char), $arr);
        return $numArr;
    }

    private function getImplodeCharString(array $numArr): string
    {
        return implode(array_map(static fn(int $num) => chr($num), $numArr));
    }

    private function swap(array $numArr): bool|array
    {
        // Get the largest index k where a[k] < a[k+1]
        $k = $this->getK($numArr);
        if ($k === false) {
            return false;
        }
        // Get the largest index l where a[k] < a[l]
        $l = $this->getL($numArr, $k);
        // Swap values of k and l
        $swappedArr = $this->swapKL($numArr, $k, $l);
        // Reverse array from after k onwards
        $reverseAfterK = $this->reverseAfterK($swappedArr, $k);
        return $reverseAfterK;
    }

    private function getK(array $numArr): false|int
    {
        // Iterate over all elements to have candidates for k, pick the largest one
        $kCandidates = [];
        $lengthNumArr = count($numArr);
        foreach ($numArr as $i => $iValue) {
            if ($i === $lengthNumArr - 1) {
                //can't be the last one
                continue;
            }
            if ($iValue < $numArr[$i + 1]) {
                $kCandidates[] = $i;
            }
        }
        if (empty($kCandidates)) {
            return false;
        }
        $k = $kCandidates[count($kCandidates)-1];
        return $k;
    }

    private function getL(array $numArr, int $k): int
    {
        // Iterate over all elements to have candidates for l
        // Important we compare values this time.
        // a[k] < a[l]
        // let's say the arr is 97,98,97,98
        // k is 2
        // a[k] = 97
        // largest index pointing to a value bigger than 97 is 3
        // l is 3
        // a[l] = 98
        // new situation: 97,98,98,97
        $lCandidates = [];
        $lengthNumArr = count($numArr);
        for ($i = 0; $i < $lengthNumArr; $i++) {
            if ($numArr[$i] > $numArr[$k]) {
                $lCandidates[] = $i;
            }
        }
        $l = $lCandidates[count($lCandidates)-1];
        return $l;
    }

    private function swapKL(array $numArr, int $k, int $l): array
    {
        $swappedArr = $numArr;
        $temp = $swappedArr[$k];
        $swappedArr[$k] = $swappedArr[$l];
        $swappedArr[$l] = $temp;
        return $swappedArr;
    }

    private function reverseAfterK(array $swappedArr, int $k): array
    {
        $reverseAfterK = $swappedArr;
        $toReverse = array_slice($reverseAfterK, $k + 1);
        $reversed = array_reverse($toReverse);
        array_splice(
            array: $reverseAfterK,
            offset: $k + 1,
            replacement: $reversed
        );
        return $reverseAfterK;
    }
}

This is in many ways certainly a flawed version in itself:

• array_unique does nothing, as not duplicate permutations are generated
• getK and getL should have searched from right to left, since the first candidate would've been the right candidate by definition
• there is some trickery you can do to condense some of these steps (like swaping k and l without using a temp variable)
• probably a million other small and big things

But as a refactoring "starting point", I feel like it's okay: All the main steps of my solution reside in their own methods, making changing these steps independently of each other easier. I like organizing things into Classes (this is what I do at work all-day after all...) and methods, although I concede that it is not exactly necessary. Still, in this way my "all-permutations-of-a- string" generator class can just be dropped into another application, it plays nicely with my IDE^[2] and is easy to test as PHPUnit (the test suite codewars uses to test your solution) generally assumes Classes.^[3]

The fun part of submitting a kata is seeing other people's solutions, of course. Very often, these are code golf-esque solutions that solve something I would've solved in 50-150 lines in 10-20 (or sometimes 2). But because these programming puzzles are often solved in this way, it's hard to see how a normal person's solution (like mine) compares to these solutions. Here's the highest rated (by "best practices") solution for the same kata:

function permutations(string $str): array
{
    if (strlen($str) < 2) {
        return [$str];
    }

    $result = [];
    $stop = strlen($str) - 1;
    for ($i = 0; $i <= $stop; $i++) {
        $substr = substr($str, 0, $i) . substr($str, $i + 1);
        foreach (permutations($substr) as $per) {
            $result[] = $str[$i] . $per;
        }
    }
    return array_unique($result);
}

When I first saw this, I was thinking that this solution somehow had implemented the same algorithm as I had just recursively, but that is actually not the case. At the core this loops through the string and removes the char at index i, then recursively permutes the rest of the string and adds that removed char back to the front. For the relatively easy case of ABC, you get:

• A gets removed, the $substr is now BC
• permutations() is called with BC
• the following is the basic case (which is where the AHA moment happened for me):
• inside the permutations(BC) call, first B is removed and permutations(C) returns C, then C is removed and permutations(B) returns B
• in both cases the removed letter and the single result from the recursive call are concatenated and added to the result, so BC and CB
• BC AND CB are the result of calling permutations() with BC: [BC, CB]
• Back in the main permutations(ABC) call A is added to the results of permutations(BC): ABC, ACB
• Then the next loop starts: Instead of A, B is removed
• permutations(AC) is called, result is AC, CA
• in the main call the result is BAC, BCA
• Finally: C is removed
• permutations(AB), result: AB, BA
• CAB, CBA
• in the main permutations call we have now finished the for loop
• the result is: ABC, ACB, BAC, BCA, CAB, CBA

Very clever!

For longer strings the recursive solution might run into trouble (stack depth) and my iterative solution seems to me (a person who didn't solve it recursively, to be fair) easier to understand, easier to maintain and easier to build upon, but this is very clever. In "production" I would probably still prefer my iterative solution, tbh.

What I find so interesting about this highly praised "best practice" solution: I don't think I would've come up with this. Ever! I can think of two reasons:

1. My computer science education was a while ago and my grasp on basic algorithms is not super strong: I can figure them out, but I don't think in algorithms.
2. Because my intuitive "algorithm" for finding permutations is bad, I do not have (or hopefully didn't have but now do) a way to think about finding permutations more systematically. I could imagine that if you actually do have an intuitive way to find all permutations that maps somewhat to the recursive approach that you could maybe implement it from thinking about how "you'd do it" naturally.

Why this is so weird to me: Many similar solutions exist to the recursive one presented above. Some of them put the removed letter to the end instead of the front or whathaveyou - I do not claim having understood all of the solutions - but none as far as I saw in my skimming the other solutions did what I did! Nobody implemented the lexicographic permutation algorithm and especially not in this "enterprise ready" form. Nobody as far as I saw came up with the idea to convert letters to numbers using ord/chr either. Not gonna lie: I feel weirdly unique.

• ← Previous
  DailyDogo 1415 🐶
• Next →
  DailyDogo 1416 🐶