Products of Permutations

permprods.php

<?php

class Permutation
{
    private $input;
    private $raw;

    function __construct($input)
    {
        $this->input = $this->parseInput($input);
    }

    private function parseInput($input)
    {
        $this->raw = $input;

        $input = explode(')(', $input);

        $input_array = array_map(
            function ($piece)
            {
                $piece = trim($piece, '()');
                $piece = $piece . $piece[0];

                return $piece;
            },
            $input
        );

        $character_array = preg_split('//', implode('', $input_array), -1, PREG_SPLIT_NO_EMPTY);

        return $character_array;
    }

    public function asArray()
    {
        return $this->input;
    }

    public function raw()
    {
        return $this->raw;
    }
}

function multiply(Permutation $one, Permutation $two = null)
{
    $tags = array();
    $output = array();

    $character_array = $one->asArray();
    if ($two !== NULL) $character_array = array_merge($character_array, $two->asArray());

    $count = count($character_array);

    while (count($tags) < count(array_unique($character_array)))
    {
        list($position, $current, $start, $tags) = openPermutation($character_array, $tags);
        $output[] = '(';
        $output[] = $start;

        while ($position < $count)
        {
            list($position, $current) = findNextRightInstance($character_array, $current, $position);

            if ($position == false)
            {
                if ($current == $start)
                {
                    $output[] = ")";
                    break;
                }
                $output[] = $current;
                $tags[$current] = $current;

                $position = array_search($current, $character_array);
                $position++;

                $current = $character_array[$position];
            }
            else if ($position < $count)
            {
                    $position++;
                    $current = $character_array[$position];
            }
        }
    }
    return new Permutation(implode('', $output));
}


function findNextRightInstance($array, $current, $position)
{
    foreach ($array as $i => $char)
    {
        if ($current == $char && $i > $position)
        {
            return [$i, $char];
        }
    }
    return [false, $current];
}

function openPermutation($character_array, $tags)
{
    list($initial_position, $start) = getNextUntaggedElement($character_array, $tags);
    $tags[] = $start;

    list($position, $current) = [$initial_position + 1, $character_array[$initial_position + 1]];

    return [$position, $current, $start, $tags];
}

function getNextUntaggedElement($array, $tags)
{
    foreach ($array as $i => $char)
    {
        if (!(in_array($char, $tags)))
        {
            return [$i, $char];
        }
    }
}


$p1 = new Permutation("(acfg)");
$p2 = new Permutation("(bcd)");
$p3 = new Permutation("(aed)");
$p4 = new Permutation("(fade)");
$p5 = new Permutation("(bgfae)");
echo multiply(multiply(multiply(multiply($p1, $p2), $p3), $p4), $p5)->raw();


$p6 = new Permutation('(acfg)(bcd)(aed)(fade)(bgfae)');
echo multiply($p6)->raw();