Permutation.php

<?php

/**
 * Class Permutation
 *
 * i.e.
 * input: 'abc'
 *
 * We want to enumerate all the leaves
 *
 * φ - a - ab - abc
 *       - ac - acb
 *   - b - ba - bac
 *       - bc - bca
 *   - c - ca - cab
 *       - cb - cba
 *
 * output:
 *  abc
 *  acb
 *  bac
 *  bca
 *  cab
 *  cba
 *
 */
class Permutation
{
    const WIDTH = 'width';
    const STR = 'str';

    protected $history = [];

    /**
     * This is the bottleneck of memory cost
     * To reduce memory usage, we can output permutation each time instead of keeping this list.
     *
     * @var array
     */
    protected $permutation_list = [];

    public function main()
    {
        $s = self::getInput();

        // $permutation = self::widthFirst($s);

        $this->initializeHistory($s);
        $permutation = $this->depthFirst();
        self::output($permutation);
    }

    /**
     * @param int $depth
     * @param int $width
     * @return array
     */
    protected function depthFirst($depth = 0, $width = 0)
    {
        // When returns to the root
        if ($depth <= 0 && $width === $this->getOriginalStrLength()) {
            return $this->permutation_list;
        }

        // Over width
        if ($width > $this->getMaxWidth($depth)) {
            $depth--;
            return $this->depthFirst($depth, $this->history[$depth][self::WIDTH] + 1);
        }

        // Generate $str
        $p_target = $depth + $width;
        $tmp_str = substr_replace($this->history[$depth - 1][self::STR], '', $p_target, 1);
        $str = substr($tmp_str, 0, $depth) . $this->history[$depth - 1][self::STR][$p_target] . substr($tmp_str, $depth);

        $this->history[$depth][self::WIDTH] = $width;
        $this->history[$depth][self::STR] = $str;

        // Reached deepest
        if ($depth + 1 >= strlen($str)) {
            $this->permutation_list[] = $str;
            $depth--;
            return $this->depthFirst($depth, $this->history[$depth][self::WIDTH] + 1);
        }

        // Go deeper
        return $this->depthFirst($depth + 1, 0);
    }

    protected function initializeHistory($s)
    {
        $this->history[-1][self::STR] = $s;
        $this->history[-1][self::WIDTH] = 0;
    }

    protected function getPreviousStr($depth)
    {
        if (isset($this->history[$depth])) {
            return $this->history[$depth][self::STR];
        }
        return $this->history[-1][self::STR];
    }

    protected function getOriginalStr()
    {
        return $this->history[-1][self::STR];
    }

    protected function getOriginalStrLength()
    {
        return strlen($this->getOriginalStr());
    }

    protected function getMaxWidth($depth)
    {
        return $this->getOriginalStrLength() - $depth - 1;
    }

    /**
     * This is width-first algorithm, so memory cost is higher than depth-first one.
     *
     * We will been given $str such that substr($str, 0, $n) is fixed.
     * Then create new $str such that substr($str, 0, $n + 1) is fixed, and pass that new $str to myself recursively.
     * At the end of each branches (leaf), $str is all fixed. At there, add the $str to $list
     *
     * @duprecated
     *
     * @param $str
     * @param int $fixed_length
     * @param array $list
     * @return array
     */
    protected static function widthFirst($str, $fixed_length = 0, $list = [])
    {
        // The end of the branch
        if ($fixed_length >= strlen($str)) {
            $list[] = $str;
            return $list;
        }
        for ($i = $fixed_length; $i < strlen($str); $i++) {
            $tmp_str = substr($str, 0, $i) . substr($str, $i + 1);
            $str = substr($tmp_str, 0, $fixed_length) . $str[$i] . substr($tmp_str, $fixed_length);
            $list = self::widthFirst($str, $fixed_length + 1, $list);
        }
        return $list;
    }

    protected static function getInput()
    {
        fscanf(STDIN, "%s", $s);
        return $s;
    }

    protected static function output($list)
    {
        foreach ($list as $val) {
            echo $val . PHP_EOL;
        }
    }
}

$class = new Permutation();
$class->main();