Recursive possibilities

[lococobra]

I'm trying to find all the possibilities for every combination of 1-X

 

The code I've written currently works fine, but to make it work in more than one case, I need to make it recursive. Try as I might, I can't seem to wrap my head around this.

 

Here's the non-recursive code:

for($i=1;$i<=4;$i++){
echo $i.'<br>';
for($j=1;$j<$i;$j++){
	echo $i.','.$j.'<br>';
	for($k=1;$k<$j;$k++){
		echo $i.','.$j.','.$k.'<br>';
		for($l=1;$l<$k;$l++){
			echo $i.','.$j.','.$k.','.$l.'<br>';
		}
	}
}
}

 

As you can see, it gives every possible combination of the numbers 1-4 without having any duplicate numbers. The number of loops must be at least equal to the number given in the first loop for this to work properly. How can I model this in a recursive function?

[Psycho]

Need a little more info. There are TWO different parameters 1) The possbile values and 2) the number of places. Do they have to be the same in your situation?

[lococobra]

I'm not entirely sure I understand what you're asking. As far as I can tell..

 

1) the possible values will always be 1-X, so all that's needed is the stop value. In this case, 4

 

2) the number of places? I think you mean how many of the possible values will be used for each possible output? If that's what you mean then all possible lengths. In this case, the outputs can be of length 1 - 4

[lococobra]

Solved it myself.

 

Here's a really rough version before I started applying the concept to the code I'm working on. I also made a version that just uses a single function, which accesses global variables to save results.. but that seemed even dirtier.

 

I don't know if this will be useful for anyone, but it's a good jumping off point for more practical applications. I'm using this to find combinations of various pieces of text which, when put together, will yield a target word count. The unfortunate thing is that the results of this function are modeled by a factorial equation. So in other words, numbers over 10 or so will take a very long time and tons of memory to process. To speed things up a bit, you can limit the number of possibilities given in any combination by capping the recursion level (see the commented out line)

 

class getPermutations
{
private $nums, $save;

public function get($count){
	$this->recurse($count, 0);
	return $this->save;
}

private function recurse($count, $level){
	if($level == 0) $count++;
	//if($level >= 5) return;
	for($i=1;$i<$count;$i++){
		$this->nums[$level] = $i;
		$this->save[] = implode(',', array_slice($this->nums, 0, $level+1));
		$this->recurse($i, $level+1);
	}
}
}