Page 1 of 1

loops

Posted: Sat Dec 01, 2007 1:56 am
by SidewinderX
Lets assume I have a string of elements such that

Code: Select all

$S = "123";
I want to loop through all of the possible combinations [order matters] such that the output looks like:
1
2
3
11
12
13
21
22
23
31
32
33
111
112
113
121
122
123
...
...
...
333
Right now I have three sets of loops that accomplishes this output:

Code: Select all

#Combinations of length 1
for($i[0] = 0; $i[0] < strlen($S); $i[0]++) {
	echo $S[$i[0]] . "<br />";	
}

#Combinations of length 2
for($i[0] = 0; $i[0] < strlen($S); $i[0]++) {
	for($i[1] = 0; $i[1] < strlen($S); $i[1]++) {
		echo $S[$i[0]] . $S[$i[1]] . "<br />";	
	}
}

#Combinations of length 3
for($i[0] = 0; $i[0] < strlen($S); $i[0]++) {
	for($i[1] = 0; $i[1] < strlen($S); $i[1]++) {
		for($i[2] = 0; $i[2] < strlen($S); $i[2]++) {
			echo $S[$i[0]] . $S[$i[1]] . $S[$i[2]] . "<br />";	
		}
	}
}

#Combinations of length n
// In a single set of loops...
My question is: assume that the $S is the set of all integers [size 'n' - infinitely big], how can I accomplish what I want [the combination of all integers], without having to hard code infinitely many loops?

Posted: Sat Dec 01, 2007 8:42 am
by kaszu
My solution:

Code: Select all

$string = 123;

function all_combinations($string, $prefix = '', $lvl = 0)
{
	$len = strlen($string);

	if ($len == $lvl)
		return;
	
	for($i = 0; $i < $len; $i++)
	{
		$str = $prefix . substr($string, $i, 1);
		echo $str . '<br />';
		all_combinations($string, $str, $lvl + 1);
	}
}

all_combinations($string);

Posted: Sat Dec 01, 2007 9:16 am
by feyd

Posted: Sun Dec 23, 2007 10:58 pm
by Ollie Saunders
kaszu solution isn't complete. You could probably tack on an intelligent sort algorithm to it because all the permutations are listed, just not in the right order.

By contrast my solution generates the numbers in the desired order initially. With a bit of fiddling you could set up a permutation iterator that would feed the numbers to you as they were generated.

Code: Select all

<?php
/**
 * Essenital rubification
 */
class Ole_ArrayObject extends ArrayObject
{
    public function last() {
        return self::get($this->count() - 1);
    }
    public function first() {
        return self::get(0);
    }
    public function get($key, $default = null) {
        return isset($this[$key]) ? $this[$key] : $default;
    }
}
/**
 * Reduces requirement for null handling logic. Swallows all calls.
 */
class NullClass
{
    public function __call($name, $param) { }
}
/**
 * Observer like iterator. It iteratates over a set and when it hits the end it
 * iterates the linked
 *
 */
class Ole_WrappingRecursiveIterator implements RecursiveIterator, Countable
{
    /**
     * The array this will iterate over
     *
     * @var array
     */
    private $_array;
    /**
     * This iterator will increment it's children after each full cycle of $_array.
     *
     * @var Iterator
     */
    private $_children;
    /**
     * Current position in the array
     *
     * @var int
     */
    private $_key;
    /**
     * Whether this Iterator has been incremented yet
     *
     * @var bool
     */
    private $_fresh = true;
    /**
     * @param array $array to iterate over
     * @param Iterator $children children to increment after each full cycle of $array
     */
    public function __construct($array, RecursiveIterator $children = null) {
    	$this->_array = $array;
    	if (!$children) {
    	    $children = new NullClass();
    	}
    	$this->_children = $children;
    	$this->_key = 0;
    }
    public function getChildren() {
    	return $this->_children;
    }
    public function hasChildren() {
    	return !$this->_children instanceof NullClass;
    }
    public function count() {
    	return count($this->_array);
    }
    public function current() {
    	return $this->_array[$this->_key];
    }
    public function __tostring() {
    	return (string)$this->current();
    }
    public function key() {
    	return $this->_key;
    }
    public function next() {
        $this->_fresh = false;

    	if ($this->_key < $this->count() - 1) {
    	    ++$this->_key;
    	} else {
            $this->_children->next();
    	    $this->_key = 0; // Wrap the incrementation, impossible to overflow
    	}
    	return $this;
    }
    public function valid() {
        return $this->_key === 0 && !$this->_fresh;
    }
    public function rewind() {
    	$this->_key = 0;
    	$this->_fresh = true;
    	$this->_children->rewind();
    }
}
function permutations($set)
{
    $iteratorSet = new Ole_ArrayObject(array());
    $out = array();
    foreach ($set as $k => $v) {
        $iteratorSet->append(new Ole_WrappingRecursiveIterator($set, $iteratorSet->last()));
        while (!$iteratorSet->first()->valid()) {
            $permutation = array();
            foreach ($iteratorSet as $iterator) {
                $permutation[] = $iterator->current();
            }
            $out[] = $permutation;
            $iteratorSet->last()->next();
        }
        $iteratorSet->last()->rewind();
    }
    return $out;
}
echo '<pre>';
foreach (permutations(array(1, 2, 3)) as $permutation) {
    echo implode($permutation) . PHP_EOL;
}
Crux:

The iterators are linked. When one is created it can be given the responsibility of incrementing another iterator but only when it's completes a full cycle of iteration and has to wrap itself around to the beginning again. This is very much like a linked-list chain and could theoretically be very long indeed if required.

Example:

A iterates over array(1, 2, 3) and is responsible for increment only itself
B iterates over array(1, 2, 3) and is responsible for incrementing itself and A
C iterates over array(1, 2, 3) and is responsible for incrementing itself and B

Initially all iterators' current values are 1.
A:1, B:1, C:1
The last is incremented.
A:1, B:1, C:2
The last is incremented.
A:3, B:1, C:3
The last is incremented. C wraps around and increments B
A:1, B:2, C:1

And so on and so forth. The remainder of the functionality is delivered by adding iterators to an "iterator set" that can be dynamically changed - so this can be based upon the data set itself.

The SPL contains a RecursiveIterator interface which I have used but regrettably it uses the term "children" which I find very confusing because it leaves the direction of recursion to be completely ambiguous.

Posted: Sun Dec 23, 2007 11:11 pm
by Kieran Huggins
8O

I totally forgot about that!

Holy crap, ole. And merry x-mas-eve.

Posted: Sun Dec 23, 2007 11:59 pm
by Ollie Saunders
Hehe yeah. I'm pretty sure the problem can be solved in a more mathematical way by calculating the number of permutations in total and the various points where a new column should be begin etc. that was the tack a tried that night when you first made me aware of this but I was ready for bed so my brain wasn't working. I might have another attempt at solving it that way tomorrow.
And merry x-mas-eve.
Yeah I don't know what's going on here, it's 6am and I'm still awake, with no good reason. I'm getting hungry it must be about breakfast time almost.

Posted: Mon Dec 24, 2007 5:02 pm
by Ollie Saunders
I wrote:I'm pretty sure the problem can be solved in a more mathematical way by calculating the number of permutations in total and the various points where a new column should be begin etc.
And here it is...I spent a while making this decent, this should be a whole lot easier to understand. It also performs waaay better. Althoug, I must admit, this only produces the three digit output and not the one and two digit output leading up to it. If someone can suggest how this could be modified to include that also I'd be interested:

Code: Select all

<?php
/**
 * Find all the permutations that a data set can appear in.
 *
 * Usage:
 * $a = new Permutations(array(1, 2));
 * $a->totalNum(); // 4
 * $a->get();      // [[1,1],[1,2],[2,1],[2,2]]
 */
class Permutations
{
    private $_dataSet = array();
    private $_dataSetSize = 0;
    private $_columnIncFreq = array(0);
    public function __construct($dataSet = null)
    {
    	if ($dataSet) {
    	    return $this->dataSet($dataSet);
    	}
    }
    /**
     * An array of all the permutations is returned.
     *
     * @return array
     */
    public function get()
    {
        $this->_columnIncFreq = $this->_columnIncrementFrequency();
        $out = array();
        // $offsets is an array of integer offsets representing each column,
        // referring to the data set. They describe the current permutation.
        $offsets = array_fill(0, $this->_dataSetSize, -1);
        for ($i = 0; $i < $this->_columnIncFreq[0]; ++$i) {
            $permutation = array();
            foreach ($offsets as $column => &$offset) {
                if ($this->_columnNeedsToBeIncremented($column, $i)) {
                    // increments but wraps around if overflow
                    $offset = ($offset + 1) % $this->_dataSetSize;
                }
                $permutation[] = $this->_dataSet[$offset];
            }
            $out[] = $permutation;
        }
        return $out;
    }
    /**
     * Returns the total number of permutations available for currently assigned
     * data set
     *
     * @return int
     */
    public function totalNum()
    {
    	return pow($this->_dataSetSize, $this->_dataSetSize);
    }
    /**
     * This function returns an array that can be used to determine the frequency
     * with which each column should be incremented.
     *
     * Element 0 is $totalNumPermutations. The last element is always 1 because the
     * endmost column is incremented every time.
     *
     * @return array
     */
    private function _columnIncrementFrequency()
    {
        $out = array($columnIncFreq = $this->totalNum());
        while ($columnIncFreq > 1) {
            $out[] = $columnIncFreq/= $this->_dataSetSize;
        }
        return $out;
    }
    /**
     * Whether or not a column needs to be incremented
     *
     * @param int $columnIndex
     * @param int $iterationIndex
     * @return bool
     */
    private function _columnNeedsToBeIncremented($columnIndex, $iterationIndex)
    {
        // Does the overall iteration index, divide evenly by the frequency
        // with which the column should be incremented
        return $iterationIndex % $this->_columnIncFreq[$columnIndex + 1] === 0;
    }
    /**
     * Combined setter and getter for data set
     *
     * @param array $dataSet
     * @return Permutations | array
     */
    public function dataSet($dataSet = null)
    {
    	if ($dataSet) {
    	    $this->_dataSet = $dataSet;
    	    $this->_dataSetSize = count($dataSet);
    	    return $this;
    	}
    	return $this->_dataSet;
    }
}

$a = new Permutations(array(1, 2, 3));
echo '<pre>';
print_r($a->get());

Posted: Tue Dec 25, 2007 10:19 am
by Kieran Huggins
lol - for some reason I thought symbol re-use was prohibited!

Here's what I have so far (ugly, but fast):

Code: Select all

function permute($str){
	$branch = array();
	// for each letter in the string, build a branch
	for($i=0; $i<strlen($str); $i++){
		$branch[$str{$i}] = permute(substr_replace($str,'',$i,1));
	}
	return $branch;
}

function flatten($array,$str=null){
	static $output = array();
	foreach($array as $k=>$v){
		if(sizeof($v)==0){ 
			$output[] = $str.$k;
			return $output;
		}
		flatten($v,$str.$k);
	}
	return $output;
}

function subpermute($array){
	for($i=1;$i<=strlen($array[sizeof($array)-1]);$i++){
		foreach($array as $str){
			$output[substr($str,0,$i)] = 'booyah';
		}
	}
	return array_keys($output);
}

$tree = permute('abcdef');
$perms = flatten($tree);
$allperms = subpermute($perms);
I'll take a crack at the actual desired output in a bit :-)

Posted: Sat Dec 29, 2007 9:27 pm
by Ollie Saunders
for some reason I thought symbol re-use was prohibited!
Yes, a single permutation may contains the same piece of data more than once. Which means you've solved a completely different problem.

It looks very nice though. The recursion in permute() screws with my brain in fact the whole things is freaking wacky in a sorta insane genius way. xD

Posted: Sat Dec 29, 2007 11:04 pm
by Kieran Huggins
Couldn't sleep tonight:

Code: Select all

function stringCheese($str){
    $len = strlen($str);
    $num = sprintf("%0".$len."s",base_convert(0,10,$len));
    while(strlen($num)==$len){
        $wideset[] = strtr($num,implode(range(0,$len-1)),$str);
        $num = sprintf("%0".$len."s",base_convert(base_convert($num,$len,10)+1,10,$len));
    }
    for($i=1;$i<=strlen($wideset[sizeof($wideset)-1]);$i++){
      foreach($wideset as $str) $output[substr($str,0,$i)] = 'cheese!';
   } 
    return array_keys($output);
}
 
// usage:
$array_of_all_possibilities = stringCheese('abcde');
Look ma, no recursion!