Combination Generator running out of memory

[johnbb]

<?php
function sampling($chars, $size, $combinations = array()) {

    # if it's the first iteration, the first set
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);

}

// example
$chars = array('q', 'a', 'z', 'w', 's', 'x', 'e', 'd', 'c', 'r', 'f', 'v', 't', 'g', 'b', 'y', 'h', 'n', 'u', 'j', 'm', 'i', 'k', 'o', 'l', 'p', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0');
$output = sampling($chars, 5);

print_r($output);
?>

Hello,

 

I'm using the above function and I'm running out of memory (8 GB). Can someone please enhance this function. This function generates all possible 5 character combinations.

Edited November 7, 2016 by johnbb

[requinix]

There will be more than 60 million strings of that length. As you generate them, multiple copies of arrays are being held in memory: $combinations and $new_combinations. Add to that PHP's own overhead and I could see you running out of memory... though 8GB seems a bit too much.

 

What are you going to do with this array? Do you actually need all 60M combinations at once or will you work with them one at a time?

[johnbb]

There will be more than 60 million strings of that length. As you generate them, multiple copies of arrays are being held in memory: $combinations and $new_combinations. Add to that PHP's own overhead and I could see you running out of memory... though 8GB seems a bit too much.

 

What are you going to do with this array? Do you actually need all 60M combinations at once or will you work with them one at a time?

 

I actually don't need them. I'm supposed to put 60466176 entries into a database and check db's size. I think, if I put 1 entry at a time into the db, the function won't run out of memory. However I felt that 8 GB should have sufficed 

VirtualAlloc() failed: [0x00000008] Not enough storage is available to process this command.


VirtualAlloc() failed: [0x00000008] Not enough storage is available to process this command.

PHP Fatal error:  Out of memory (allocated 908066816) (tried to allocate 805306376 bytes) in C:\Users\***\PhpstormProjects\ty\functions.php on line 21

Fatal error: Out of memory (allocated 908066816) (tried to allocate 805306376 bytes) in C:\Users\***\PhpstormProjects\ty\functions.php on line 21

Edited November 8, 2016 by johnbb

[requinix]

By my math that's 1.6GB, not 8GB.

 

If you don't need them all at once then generate them one at a time.

function sampling($chars, $size) {
	$base = count($chars);
	$limit = pow($base, $size);
	for ($i = 0; $i < $limit; $i++) {
		$combination = "";
		$n = $i;
		for ($j = 0; $j < $size; $j++) {
			$combination = $chars[fmod($n, $base)] . $combination;
			$n = floor($n / $base);
		}
		yield $combination;
	}
}

$chars = str_split('qwertyuiopasdfghjklzxcvbnm1234567890');
$generator = sampling($chars, 5);

foreach ($generator as $combination) {
	// ...
}

You have to use a foreach on $generator because it will generate each combination as you need it. Not all at once.