Permute multi-dimensional array

[ignace]

Hi,

 

Does someone know of a recursive way to permute $data? Currently I am using iteration and that sucks.. I tried without luck, online examples were only about 1-dimensional array's.

 

$data = [
  [1,3,4],
  [11,15,16],
  [22,24,25,28],
  [36,38],
  [44,48,50],
  [1,2,3],
  [9,10,11],
];

So that it permutates to:

 

[] = [1,11,22,36,44,1,9]
[] = [1,11,22,36,44,1,10]
[] = [1,11,22,36,44,1,11]
[] = [1,11,22,36,44,2,9]
[] = [1,11,22,36,44,2,10]
[] = [1,11,22,36,44,2,11]
[] = [1,11,22,36,48,1,9]
[] = [1,11,22,36,48,1,10]
[] = [1,11,22,36,48,1,11]
..

[Barand]

I'm pretty sure I posted a solution to a similar question posted by Jessica some time ago. I'll see if search turns it up.

 

edit: success http://forums.phpfreaks.com/topic/266415-permutations-of-setscombinations/?do=findComment&comment=1365289

[ignace]

Thx Barand. So simple, I really need to quit pulling an all-nighter and head off to bed before I am completely embarrassing myself.

 

EDIT: Awesome, with a few tweaks, running a gazillion permutations (don't need to store all of them just specific ones) on a 128M system

[ignace]

Ok so I had to make too much tweaks to the above function to make it re-usable across multiple scenario's. I also dropped the multi-dimensional array and made it single-dimensional.

 

And I was looking for a Iterator-like solution because storing them meant possible memory issues. Also using an Iterator-like solution allows me to 'page' through them. This is what I ended up with:

 

/**
 * Original author:
 * @author http://stereofrog.com/blok/on/070910
 * 
 * Preserved by:
 * @author http://stackoverflow.com/a/3742837
 */
class Combinations implements Iterator
{
    /**
     * @var array
     */
    private $offsets = null;

    /**
     * @var array|string
     */
    private $set = null;

    /**
     * @var integer
     */
    private $length = 0;

    /**
     * @var integer
     */
    private $width = 0;

    /**
     * @var integer
     */
    private $key = 0;

    /**
     * @param array|string $set
     * @param integer $width
     */
    public function __construct($set, $width)
    {
        if (is_array($set)) {
            $this->set = array_values($set);
            $this->length = count($this->set);
        } else {
            $this->set = (string)$set;
            $this->length = strlen($this->set);
        }

        $this->width = $width;
        $this->rewind();
    }

    /**
     * @return CombinationsMemento
     */
    public function getMemento()
    {
        return new CombinationsMemento($this->set, $this->length, $this->key, $this->offsets, $this->width);
    }

    /**
     * @param CombinationsMemento $memento
     */
    public function setMemento(CombinationsMemento $memento)
    {
        $this->set = $memento->getSet();
        $this->length = $memento->getLength();
        $this->key = $memento->getKey();
        $this->offsets = $memento->getOffsets();
        $this->width = $memento->getWidth();
    }

    /**
     * @return integer
     */
    public function key()
    {
        return $this->key;
    }

    /**
     * @return array|string
     */
    public function current()
    {
        $result = array();

        for ($i = 0; $i < $this->width; $i++) {
            $result[] = $this->set[$this->offsets[$i]];
        }

        return is_array($this->set) ? $result : implode('', $result);
    }

    /**
     *
     */
    public function next()
    {
        if ($this->_next()) {
            $this->key++;
        } else {
            $this->key = -1;
        }
    }

    /**
     *
     */
    public function rewind()
    {
        $this->offsets = range(0, $this->width);
        $this->key = 0;
    }

    /**
     * @return boolean
     */
    public function valid()
    {
        return $this->key >= 0;
    }

    /**
     * @see http://mysite.verizon.net/res148h4j/javascript/script_combinations.html#the%20source%20code
     * @return boolean
     */
    protected function _next()
    {
        $i = $this->width - 1;

        while ($i >= 0 && $this->offsets[$i] == $this->length - $this->width + $i) {
            $i--;
        }

        if ($i < 0) {
            return false;
        }

        $this->offsets[$i]++;

        while ($i++ < $this->width - 1) {
            $this->offsets[$i] = $this->offsets[$i - 1] + 1;
        }

        return true;
    }
}

What I am doing here is as a combination is generated, I inspect it and if it's valid I store it in a fixed array. Once the array is filled, it retrieves the memento and stores the fixed array and memento in the database. At a later time the last memento is retrieved and the process proceeds.