Recursive Help

PHP
1

what i need is a recursive number generator i cannot have the function pick random numbers. i need it to go in order until all possibilities are taken into account

for example i would like the output to be something like this

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 4
1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1 2 3
1 1 1 1 1 1 1 2 4

basically i would like it to work something like that so the code recursively changed all the numbers so that every possible number combination is generated

9 total numbers for this example.
each number can be a range from 1-115 but for this example i used 1-4

here is some code that i made but it does not work how i would like it too

donumbers(3,1,3,$sofar);
function donumbers($howmany, $low, $high, $sofar){
$n=0;
for($i=0;$i>=$low,$i<=$high;$i++){
$sofar_copy = $sofar;
$sofar_copy[$n] = $i;
$n++;
if ($howmany == 0){
$count = count($sofar_copy);
if($count == 3){
print_r($sofar_copy);
echo "<br>";
}// end if count statment
}else{
donumbers($howmany - 1, $low, $high , $sofar_copy);
}// end if howmany == 0 including else statment

}// end for statment
}// end function

here is some output from the script and as you can see its not hitting every possible number combination as you can see it fails right from the start and never generates the sequence

1 1 1
Array ( [0] => 0 [1] => 1 [2] => 2 )
Array ( [0] => 0 [1] => 1 [3] => 3 )
Array ( [0] => 0 [2] => 2 [1] => 1 )
Array ( [0] => 0 [2] => 2 [3] => 3 )
Array ( [0] => 0 [3] => 3 [1] => 1 )
Array ( [0] => 0 [3] => 3 [2] => 2 )
Array ( [0] => 0 [1] => 1 [2] => 2 )
Array ( [0] => 0 [1] => 1 [3] => 3 )
Array ( [0] => 0 [1] => 1 [2] => 2 )
Array ( [0] => 0 [1] => 1 [3] => 3 )
Array ( [0] => 0 [1] => 1 [2] => 2 )
Array ( [0] => 0 [1] => 1 [2] => 2 )
Array ( [0] => 0 [1] => 1 [2] => 2 )
Array ( [0] => 0 [1] => 1 [3] => 3 )
Array ( [0] => 0 [1] => 1 [3] => 3 )
Array ( [0] => 0 [1] => 1 [3] => 3 )
Array ( [0] => 0 [2] => 2 [1] => 1 )
Array ( [0] => 0 [2] => 2 [3] => 3 )
Array ( [0] => 0 [2] => 2 [1] => 1 )
Array ( [0] => 0 [2] => 2 [1] => 1 )
Array ( [0] => 0 [2] => 2 [1] => 1 )
Array ( [0] => 0 [2] => 2 [1] => 1 )
Array ( [0] => 0 [2] => 2 [3] => 3 )
Array ( [0] => 0 [2] => 2 [3] => 3 )
Array ( [0] => 0 [2] => 2 [3] => 3 )
Array ( [0] => 0 [2] => 2 [3] => 3 )
Array ( [0] => 0 [3] => 3 [1] => 1 )
Array ( [0] => 0 [3] => 3 [2] => 2 )
Array ( [0] => 0 [3] => 3 [1] => 1 )
Array ( [0] => 0 [3] => 3 [1] => 1 )
Array ( [0] => 0 [3] => 3 [1] => 1 )
Array ( [0] => 0 [3] => 3 [2] => 2 )
Array ( [0] => 0 [3] => 3 [2] => 2 )
Array ( [0] => 0 [3] => 3 [2] => 2 )
Array ( [0] => 0 [3] => 3 [1] => 1 )
Array ( [0] => 0 [3] => 3 [2] => 2 )
Array ( [1] => 1 [0] => 0 [2] => 2 )
Array ( [1] => 1 [0] => 0 [3] => 3 )
Array ( [1] => 1 [0] => 0 [2] => 2 )
Array ( [1] => 1 [0] => 0 [3] => 3 )
Array ( [1] => 1 [0] => 0 [2] => 2 )
Array ( [1] => 1 [0] => 0 [2] => 2 )
Array ( [1] => 1 [0] => 0 [2] => 2 )
Array ( [1] => 1 [0] => 0 [3] => 3 )
Array ( [1] => 1 [0] => 0 [3] => 3 )
Array ( [1] => 1 [0] => 0 [3] => 3 )
Array ( [1] => 1 [0] => 0 [2] => 2 )
Array ( [1] => 1 [0] => 0 [3] => 3 )
Array ( [1] => 1 [2] => 2 [0] => 0 )
Array ( [1] => 1 [2] => 2 [3] => 3 )
Array ( [1] => 1 [3] => 3 [0] => 0 )
Array ( [1] => 1 [3] => 3 [2] => 2 )
Array ( [1] => 1 [2] => 2 [0] => 0 )
Array ( [1] => 1 [2] => 2 [0] => 0 )
Array ( [1] => 1 [2] => 2 [0] => 0 )
Array ( [1] => 1 [2] => 2 [0] => 0 )
Array ( [1] => 1 [2] => 2 [3] => 3 )
Array ( [1] => 1 [2] => 2 [0] => 0 )
Array ( [1] => 1 [2] => 2 [3] => 3 )
Array ( [1] => 1 [2] => 2 [3] => 3 )
Array ( [1] => 1 [2] => 2 [3] => 3 )
Array ( [1] => 1 [2] => 2 [3] => 3 )
Array ( [1] => 1 [3] => 3 [0] => 0 )
Array ( [1] => 1 [3] => 3 [0] => 0 )
Array ( [1] => 1 [3] => 3 [0] => 0 )
Array ( [1] => 1 [3] => 3 [0] => 0 )
Array ( [1] => 1 [3] => 3 [2] => 2 )
Array ( [1] => 1 [3] => 3 [2] => 2 )
Array ( [1] => 1 [3] => 3 [2] => 2 )
Array ( [1] => 1 [3] => 3 [2] => 2 )
Array ( [1] => 1 [3] => 3 [0] => 0 )
Array ( [1] => 1 [3] => 3 [2] => 2 )
Array ( [2] => 2 [0] => 0 [1] => 1 )
Array ( [2] => 2 [0] => 0 [3] => 3 )
Array ( [2] => 2 [0] => 0 [1] => 1 )
Array ( [2] => 2 [0] => 0 [1] => 1 )
Array ( [2] => 2 [0] => 0 [1] => 1 )
Array ( [2] => 2 [0] => 0 [1] => 1 )
Array ( [2] => 2 [0] => 0 [3] => 3 )
Array ( [2] => 2 [0] => 0 [3] => 3 )
Array ( [2] => 2 [0] => 0 [3] => 3 )
Array ( [2] => 2 [0] => 0 [3] => 3 )
Array ( [2] => 2 [1] => 1 [0] => 0 )
Array ( [2] => 2 [1] => 1 [0] => 0 )
Array ( [2] => 2 [1] => 1 [0] => 0 )
Array ( [2] => 2 [1] => 1 [0] => 0 )
Array ( [2] => 2 [1] => 1 [3] => 3 )
Array ( [2] => 2 [1] => 1 [0] => 0 )
Array ( [2] => 2 [1] => 1 [3] => 3 )
Array ( [2] => 2 [1] => 1 [3] => 3 )
Array ( [2] => 2 [1] => 1 [3] => 3 )
Array ( [2] => 2 [1] => 1 [3] => 3 )
Array ( [2] => 2 [0] => 0 [1] => 1 )
Array ( [2] => 2 [0] => 0 [3] => 3 )
Array ( [2] => 2 [1] => 1 [0] => 0 )
Array ( [2] => 2 [1] => 1 [3] => 3 )
Array ( [2] => 2 [3] => 3 [0] => 0 )
Array ( [2] => 2 [3] => 3 [1] => 1 )
Array ( [2] => 2 [3] => 3 [0] => 0 )
Array ( [2] => 2 [3] => 3 [0] => 0 )
Array ( [2] => 2 [3] => 3 [0] => 0 )
Array ( [2] => 2 [3] => 3 [1] => 1 )
Array ( [2] => 2 [3] => 3 [1] => 1 )
Array ( [2] => 2 [3] => 3 [1] => 1 )
Array ( [2] => 2 [3] => 3 [0] => 0 )
Array ( [2] => 2 [3] => 3 [1] => 1 )
Array ( [2] => 2 [3] => 3 [0] => 0 )
Array ( [2] => 2 [3] => 3 [1] => 1 )
Array ( [3] => 3 [0] => 0 [1] => 1 )
Array ( [3] => 3 [0] => 0 [2] => 2 )
Array ( [3] => 3 [0] => 0 [1] => 1 )
Array ( [3] => 3 [0] => 0 [1] => 1 )
Array ( [3] => 3 [0] => 0 [1] => 1 )
Array ( [3] => 3 [0] => 0 [2] => 2 )
Array ( [3] => 3 [0] => 0 [2] => 2 )
Array ( [3] => 3 [0] => 0 [2] => 2 )
Array ( [3] => 3 [0] => 0 [1] => 1 )
Array ( [3] => 3 [0] => 0 [2] => 2 )
Array ( [3] => 3 [1] => 1 [0] => 0 )
Array ( [3] => 3 [1] => 1 [0] => 0 )
Array ( [3] => 3 [1] => 1 [0] => 0 )
Array ( [3] => 3 [1] => 1 [0] => 0 )
Array ( [3] => 3 [1] => 1 [2] => 2 )
Array ( [3] => 3 [1] => 1 [2] => 2 )
Array ( [3] => 3 [1] => 1 [2] => 2 )
Array ( [3] => 3 [1] => 1 [2] => 2 )
Array ( [3] => 3 [1] => 1 [0] => 0 )
Array ( [3] => 3 [1] => 1 [2] => 2 )
Array ( [3] => 3 [2] => 2 [0] => 0 )
Array ( [3] => 3 [2] => 2 [0] => 0 )
Array ( [3] => 3 [2] => 2 [0] => 0 )
Array ( [3] => 3 [2] => 2 [1] => 1 )
Array ( [3] => 3 [2] => 2 [1] => 1 )
Array ( [3] => 3 [2] => 2 [1] => 1 )
Array ( [3] => 3 [2] => 2 [0] => 0 )
Array ( [3] => 3 [2] => 2 [1] => 1 )
Array ( [3] => 3 [2] => 2 [0] => 0 )
Array ( [3] => 3 [2] => 2 [1] => 1 )
Array ( [3] => 3 [0] => 0 [1] => 1 )
Array ( [3] => 3 [0] => 0 [2] => 2 )
Array ( [3] => 3 [1] => 1 [0] => 0 )
Array ( [3] => 3 [1] => 1 [2] => 2 )
Array ( [3] => 3 [2] => 2 [0] => 0 )
Array ( [3] => 3 [2] => 2 [1] => 1 )

2

hey Marcus.

I just got done with work for the day and i am getting called out of town for a few days, i looked over the code and it appears to be masterful as always.

i will make a script out of it and play with it a bit before i leave. i will mess with it more when i return. i just wanted to say thank you and again thank you.

thanks for all your help and i will get back to you when i return.

take care and have a great weekend. and again thank you.

X

3

ok like right now the output goes like this

1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 1 3

could the output be easily changed to go like this

2 2 2 2 2 2
2 2 2 2 2 4
2 2 2 2 2 6

essentially each number that is outputted is an even number that way when i process data i only have to go over 50% of the results to get a base line figure. so if there is 1mil output of the +1 i will only have to process 500k of the even results.

so the question is can the numbers outputted be easily converted to only even numbers being the output or should i just essentially filter out all the odd numbered results on the fly before processing happens.

4

Hi…

Well, with a response like that, how can I not help? :slight_smile:

What do you want the first few lines of output to be? I am not sure what you mean by incrementing by 2.

yours, Marcus

5

Hi…

I really need the next few lines so that I can see the rollover behaviour.

Also you will be processing a lot less than half the numbers if you do this. Your original problem will output 387420489 9 digit numbers, but if you only allow the digits 2, 4, 6, 8 then you will only generate 262144 such numbers.

I’ll take a punt that this is what you want…


<?php
function indexes($n, $base) {
    return str_pad(base_convert($n - 1, 10, $base), 9, '0', STR_PAD_LEFT);
}

function digits($n, $symbols) {
    return strtr(indexes($n, strlen($symbols)), '0123456789', $symbols);
}

function show_number($digits) {
    print implode(' ', str_split($digits)) . "\
";
}

for ($i = 1; $i < 100; $i++) {
    show_number(digits($i, '2468'));
}
?>

This gives rolling even digits only. Changing the second from last line to…


    show_number(digits($i, '123456789'));

…gives the previous solution.

Basically I convert the number base to base 9 or base 4 respectively, then use the digits to look up the actual printed values. If you use ‘abcde’ for the symbols, you’ll see what I mean. The string ‘01’ prints binary, ‘01234567’ octal, and ‘0123456789abcdef’ is hexadecimal.

yours, Marcus.

6

Marcus.

I have to say there is no need for you to look smart or attempt to look clever. you are a very bright person who I am sure shines even in the brightest of days.

i plugged in that little line of code. i tried to fix it myself but again i failed. you have already taught me another lesson and it shows. You said that its easier to stay away from nested loops when dealing with larger problems like this due to the fact of all the +1 errors that can occur when dealing with count(). so i took that right out of my head. so i was not using that to get the job done. i kept telling myself this has to all be accomplished in 1-3 lines of code because that is how Marcus would have done it.

so i read about all the built in functions that you had told me to read. and tried that in my creation to work with your code. and i could not get it to work.

so i woke up this morning and i went and checked the forum here which has become a daily activity which i enjoy. and here is your post. and here i am humbled yet again. :lol:

i got some python code that does the same exact thing. but yours is super super super super fast. i even ported the code to php and it was exponentially slower then your code

def generate(prefix, max, length):
    if length == 0:
        yield prefix
    else:
        for x in range(1, max+1):
            for s in generate(prefix + [x], max, length-1):
                yield s

for s in generate([], 115, 9):
    print s

now with the output from a python shell compared to a PHP shell is amazingly different. it does the same exact thing but the php is soo fast i can hardly see the output. where with the python script i can see the numbers go past at a much more legible rate. so again Marcus you are the man.

now here is my question for now. i have attempted to change the code that you gave me in a few different ways. and the ways have been to attempt to raise the increment by 2 instead of 1. there for eliminating 50% of all possibilities to be processed in the end. so there is that way to attempt it or there is checking all of the numbers that are produced at the end.

again thank you for your time you are a super cool person. the world needs more people like you that is forsure

7

Thank you for taking the time to respond to my post. its really cool that you took the time to do that. i want to thank you for that. i tested out your code that you constructed and the code only produces numbers that keep on going until 115. which is what was desired. but the numbers do not shift as required.

this problem is rather complex far more then i could have imagined. if you have any additions or edits that you could make that would be great. any help i can get is very much appreciated

8

Hi…


for ($i = 1; $i <= 20000; $i++) {
    show_number(digits($i, 9));
}

There is no need to load everything into an array for printing. That was just me trying to look clever ;).

yours, Marcus

9

Hey Marcus,

you are a truly brilliant person. i have read over your explanation like 5x and i think i am starting to get it. and after playing with the code that you made i think i am starting to understand it.

I will definitely pick up some reading material on the subjects which you suggested.

Now my final question is this. there is a specific limit of how many 9’s are being generated and this is very clear and straightforward i could see this from just changing things in the code and i could see the changes. I changed numbers in a specific way and it generated output which was similar to what your script outputted with an unbalanced equation.

This code is actually surprisingly complex. way more then i thought it would have ever been when i first started out with this problem. and its very clear that this is way way over my head but thanks to you i am starting to understand it. not really but i have a gun to take a shot in the dark with now thanks to you.

But after your explanation of how this works and the laws/theory behind it the code generates and creates an array of all possibilities. that is why if you turn this thing up to around 20k outputted results you get an out of memory error. which would be expected and is something that i was going to try and tackle. So i learned this early this morning before you even replied that i could not destroy the array because the array is what is generating the number combinations. without being able to kill the array memory is quickly filled up and an error is returned. and this is exactly the opposite of how i was thinking about this problem. I was thinking about using an array generating 1 combination at a time and destroying the array to effectively keep memory clear. Is taking an approach like that even possible with a code structure such as this? Because even outputting all results to say a text file is even out of the question with this. or am i wrong with this. even if the file was 100’s of gigs large or even a database of all outputted results might be logical in this situation. but is something like that even possible. or what approach would you recommend?

again Marcus thank you so much for your time effort and energy. it means a great deal to me.

thanks again and have a great day/night

10

Hi…

Shorter version:


<?php
function digit($n, $place) {
    return ($n - 1)/pow(9, $place - 1) &#37; 9 + 1;
}

function digits($n, $places) {
    return array_map('digit', array_fill(1, $places, $n), array_reverse(range(1, $places)));
}

function show_number($digits) {
    print implode(' ', $digits) . "\
";
}

array_map('show_number', array_map('digits', range(1, 100), array_fill(1, 100, 9)));
?>

The array_map() function takes a little getting used to, but once you get it it’s actually much easier to work with than nested loops or recursion. It relies on there being a mapping function, here called digit(), to calculate the digit for each position.

I was going to use base_convert($n, 10, 9) in digit(), but it didn’t seem to make the code shorter. You need a lookup table to get the actual digit ($table = range(1, 9)), but that was an extra line of code. I know enough maths to do it by hand, but you might want that extra line.

yours, Marcus

11

Hi…


<?php
function digit($n, $place) {
    return ($n - 1)/pow(9, $place - 1) &#37; 9 + 1;
}

function digits($n, $places) {
    return array_map('digit', array_fill(1, $places, $n), array_reverse(range(1, $places)));
}

function show_number($digits) {
    print implode(' ', $digits) . "\
";
}

array_map('show_number', array_map('digits', range(1, 100), array_fill(1, 100, 9)));
?>?>

yours, Marcus

12

Given what you state here your code is pretty complicated. It sounds like what your basically looking for is something like this


$numberOfColumns = 9;

// Generate a number set with 9 columns
for ( $column = 0; $column < $numberOfColumns; $column += 1)
{
     for ($numberInColumn = 1; $numberInColumn <= 115; $numberInColumn += 1)
     {
          // Write out the number for this position in the column
          // Or stick it in your array
          // Or whatever....
     }

}

I think that’s the guts of it.

13

thank you so much for your help.

it is greatly appreciated more then you know. the script that you created works very well. and i cannot thank you enough for it.

Now this is something that i was anticipating since i decided on the approach to take this. and that was all these number combinations will very quickly fill up memory. and they do.

There must be some form of error handling in one of the Pre-built php functions which you used for this script that works PERFECTLY!!! THANK YOU! From the start I was going to generate the array or string or whatever was generated process the data save the best results destroy the Array / String repeat until all possibilities are complete.

By doing as such the theory is generate 1 string at a time and storing only the best results i am now able to go through 1000000085248908599034589^99 possibilities and still not fill up the memory. leave resources available to possibly have a chance of getting through all this in a semi reasonable amount of time.

Another thing that i thought would be as simple as changing one or 2 numbers within the function would be incrementing the numbers by 2. this will keep all final strings even so it will be like

2 2 2 2 2
2 2 2 2 4
2 2 2 2 6
2 2 2 2 8

i figured it would be as simple as changing a “1” to “2” when i started out on this problem. but it does not seem to work like that.

the reason i am having so many problems with this is i just do not get it. for some reason recursion is a very simple thing that has been around FOREVER and i still cannot wrap my head around it. i guess i am just not aware of my own “recursive thinking” and this is where the problem just escapes me. i have looked at this problem as a math problem, i have looked up the rules of it from a strictly math perspective and it still escapes my known thinking patterns.

I guess i am one of those kinda people that i cannot do something until i fully understand it. and by looking at your code and what you created its a double recursion and that is very far beyond even the track i was going on.

again thank you. thank you thank you.

and i do understand within the example any processing that you desire to do that happens where the array is printed. but as far as the rules go i could tell you. but with how it works down to the nitty gritty with a step by step follow through i have no f****ing idea how to recreate recursion.

thanks again for your time

14

Hi…

I’m not using recursion :).

array_map() takes a function and applies it to each member of the array to give a new array. e.g…


function plus_one($n) { return $n + 1; }
print_r(array_map('plus_one', range(1, 10)));

This gives a list of numbers from 2 to 11 (range is a PHP function, check out the docs).

The actual trick I used is to come up with a formula to convert a number and digit position into the result. I figured you were counting in base 9, so the last digit is just modulo 9 for the nth number, the “tens” position (really the nines) is just n/9 modulo 9, the “hundreds” is n/81 modulo 9 and so on.

To generate a nine digit number I need digit($n, 9), digit($n, 8), …, digit($n, 1). So I create a list of nine digits with range(1, 9) and reverse it (I realised later I could just have gone range(9, 1, -1)) and also create $n nine times ver with array_fill($n, 9). These two lists fill the parameters to digit() when using array_map().

For the printing I use the same trick, generating a list of 100 numbers and a list of 100 nines (nine digits apiece). If you think of it as list operations it becomes quite straight forward. Much easier to track than loops, because of fewer off by one errors.

If you want to learn this stuff, then spend a couple of days with an introductory Scheme or LisP book. You’ll learn a lot about recursion as well :).

yours, Marcus