recursing

[Stooney]

Before anyone mentions it, this is purely practice and more of a brain exercise than anything else. 

 

I am having trouble figuring this out.  I want this function to be recursive.  All it should do is put together all possible combinations of the given characters and of length 1 through $this->length (aka max length). 

 

I have this, and it's not quite right

<?php
//Earlier in the class....
$this->chars=array('a', 'b', 'c');  //Not actually this ugly, just simple example
$this->length=10 //Max Length of any string

public function search($length=1, $string){
	$charsetLength=count($this->chars);
	for($i=0; $i<$charsetLength; $i++){
		$string=$string.$this->chars[$i];
		if($length<$this->length){
			$this->search($length+1, $string);
		}
		echo $string.'<br>';
	}
}

 

The output I'm looking for is kinda like this: (not in any order)

a

b

c

...

aa

bb

cc

...

ab

ac

ad

...

ba

bb

bc

.......

abbbcdd

abbbcdf

abbbcdg

....

 

All combinations of string of length 1 through $this->length, using all chars from $this->chars.

 

Thanks in advance.  This is confusing

[Ken2k7]

You should have your recursive function return a value. That way, you can call it tack on more values. As it stands, it just echos it out. Not much you can do with that.

[Stooney]

You should have your recursive function return a value. That way, you can call it tack on more values. As it stands, it just echos it out. Not much you can do with that.

 

Yea, that will come once I can get the actual algorithm correct.  Right now it does not do what I am aiming for

[Ken2k7]

I don't even know what it's supposed to do. Where do d, f and g come from? ???

[Stooney]

All it's supposed to do is generate every possible combination of characters using the characters provided and generating strings of length 1 through $this->length (10 for example).

[DarkSuperHero]

shouldn't your max length be the length/amount of characters  you have?

 

eg... your array has [a,b,c]

 

your combinations will be

 

a,b,c

ab,ac,aa

ba,bc,bb

ca,cb,cc

abc,acb...so on so forth...

 

[cunoodle2]

Not sure if this helps you but wouldn't it just be easier to use a while loop and echo each item out or does it absolutley have to be recursive?

 

IF it has to be recursive I see you defining a character array but for some reason don't actually pass it into the function.  Instead you are passing some "string" variable.

[Ken2k7]

I think this is doable, but I'm a little sketchy on how to duplicate an array entry to fill up the requirement of length 10. :-\

 

Part of this is to break it down to simple bits. Write a function and perhaps some helper functions that takes an array and prints out all possible combo of that array. From there, you'll have to determine a way to add a, b, c and whatever elements into the array in some way.

 

I'm thinking of just filling up the array with 10 items and then call the function repeatedly for all possible combos, which can get heavy because there will be a large number of dupes. Hmm...

[DarkSuperHero]

how about storing the different combo's in an array, making the combo the key, and the value the number of times it has been repeated....

 

eg.

 

array['abc']  = 1;

array['ab'] = 2;

 

then you could just echo the keys to find the different cobo's.... ?

[w3evolutions]

Maybe someone can add to this:

 

function getCombinations($items, $string="", $i=0, &$return=array()) {
if ($i >= count($items)) {
	return $return[] = $string;
} else {
	if(is_array($items[$i])) {
		foreach ($items[$i] as $item) {
			 getCombinations($items, "$string $item", $i + 1, $return);
		}
	} else {
		foreach ($items as $item) {
			getCombinations($items, "$string $item", $i + 1, $return);
		}
	}
}

return $return;
}

$Arrays = array("a","b","c");

$return = getCombinations($Arrays);

print_r($return);

 

results:

 

Array

(

    [0] =>  a a a

    [1] =>  a a b

    [2] =>  a a c

    [3] =>  a b a

    [4] =>  a b b

    [5] =>  a b c

    [6] =>  a c a

    [7] =>  a c b

    [8] =>  a c c

    [9] =>  b a a

    [10] =>  b a b

    [11] =>  b a c

    [12] =>  b b a

    [13] =>  b b b

    [14] =>  b b c

    [15] =>  b c a

    [16] =>  b c b

    [17] =>  b c c

    [18] =>  c a a

    [19] =>  c a b

    [20] =>  c a c

    [21] =>  c b a

    [22] =>  c b b

    [23] =>  c b c

    [24] =>  c c a

    [25] =>  c c b

    [26] =>  c c c

)

 

 

[Stooney]

Thank you very much w3evolutions.  I have expanded on your code to more fit my needs.  There is one last hurdle I can't figure out though.  My variation of it accepts a min and max string length, and generates all char combos of length min through max (example below).  My question is how would I allow myself to decide at what length it starts (for performance)?  As of now, if I want strings of length 3 chars through 5 chars, the script will still go through and generate the combos for length 1-3, they just won't be returned.  How do I make the script skip to the defined minimum length?

 

<?php
private function getCombinations($items, $string="", $i=0, &$return=array()) {
	if (strlen($string)>=$this->min && strlen($string)<=$this->max) {
		$return[]=$string;
	}
	if (strlen($string)>=$this->max) {
		return $return[] = $string;
	} else {
		foreach ($items as $item) {
			$this->getCombinations($items, "$string$item", $i + 1, $return);
		}
	}
	return $return;
}
?>

 

Sample output of current script set with min length: 1 and max length: 3

 

a

aa

aaa

aaa

aab

aab

aac

aac

ab

aba

aba

abb

abb

abc

abc

ac

aca

aca

acb

acb

acc

acc

b

ba

baa

baa

...(omitted the rest, you should get the idea)

 

Thanks in advance