Php recursion to get all possibilities of strings
Here's a simple algo. Iterate from 1 to 2count(array)-1. On each iteration, if j-th bit in a binary representation of the loop counter is equal to 1, include j-th element in a combination.
As PHP needs to be able to calculate 2count(array) as an integer, this may never exceed PHP_INT_MAX. On a 64-bit PHP installation your array cannot have more than 62 elements, as 262 stays below PHP_INT_MAX while 263 exceeds it.
EDIT: This computes all possible combinations, not permutations (ie, 'abc' = 'cba'). It does so by representing the original array in binary and "counting up" from 0 to the binary representation of the full array, effectively building a list of every possible unique combination.
$a = array('a', 'b', 'c', 'd');
$len = count($a);
$list = array();
for($i = 1; $i < (1 << $len); $i++) {
$c = '';
for($j = 0; $j < $len; $j++)
if($i & (1 << $j))
$c .= $a[$j];
$list[] = $c;
}
print_r($list);
PHP: How do you generate all possible combinations of values in an array?
Here's another way.
This function increments in base( [number of elements in array] )
and uses the strtr function to swap out the characters for strings.
function everyCombination($array) {
$arrayCount = count($array);
$maxCombinations = pow($arrayCount, $arrayCount);
$returnArray = array();
$conversionArray = array();
if ($arrayCount >= 2 && $arrayCount <= 36)
{
foreach ($array as $key => $value) {
$conversionArray[base_convert($key, 10, $arrayCount)] = $value;
}
for ($i = 0; $i < $maxCombinations; $i++) {
$combination = base_convert($i, 10, $arrayCount);
$combination = str_pad($combination, $arrayCount, "0", STR_PAD_LEFT);
$returnArray[] = strtr($combination, $conversionArray);
}
return $returnArray;
}
echo 'Input array must have between 2 and 36 elements';
}
Then ...
print_r(everyCombination(array('a', 'b', 'c', 'd')));
This also seems to be significantly faster than the recursive example below.
Using microtime() on my server this code runs in 0.072862863540649 seconds
The recursive example below takes 0.39673089981079 seconds.
138% faster!
All possible combinations in array - recursion?
A recursive solution.
<?php
function combination($remaining, $current, $combinations) {
$e = array_shift($remaining);
$combinations[$current][] = $e;
if(empty($remaining)) {
print_r($combinations);
return;
}
combination($remaining, $current, $combinations);
// 6 Limit remove for all solutions
if ($current < 6) {
combination($remaining, $current + 1, $combinations);
}
}
$remaining = range(0, 23);
combination($remaining, 0, array());
If you want to store all solutions for [0,23] you're gonna have a bad time.
Printing all permutations of strings that can be formed from phone number
The following code should do it. Fairly straight forward: it uses recursion, each level processes one character of input, a copy of current combination is built/passed at each recursive call, recursion stops at the level where last character of input is processed.
function alphaGenerator($input, &$output, $current = "") {
static $lookup = array(
1 => "1", 2 => "abc", 3 => "def",
4 => "ghi", 5 => "jkl", 6 => "mno",
7 => "pqrs", 8 => "tuv", 9 => "wxyz",
0 => "0"
);
$digit = substr($input, 0, 1); // e.g. "4"
$other = substr($input, 1); // e.g. "3556"
$chars = str_split($lookup[$digit], 1); // e.g. "ghi"
foreach ($chars as $char) { // e.g. g, h, i
if ($other === false) { // base case
$output[] = $current . $char;
} else { // recursive case
alphaGenerator($other, $output, $current . $char);
}
}
}
$output = array();
alphaGenerator("43556", $output);
var_dump($output);
Output:
array(243) {
[0]=>string(5) "gdjjm"
[1]=>string(5) "gdjjn"
...
[133]=>string(5) "helln"
[134]=>string(5) "hello"
[135]=>string(5) "hfjjm"
...
[241]=>string(5) "iflln"
[242]=>string(5) "ifllo"
}
PHP algorithm to generate all combinations of a specific size from a single set
I would use a recursive function. Here's a (working) example with comments. Hope this works for you!
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('a', 'b', 'c');
$output = sampling($chars, 2);
var_dump($output);
/*
array(9) {
[0]=>
string(2) "aa"
[1]=>
string(2) "ab"
[2]=>
string(2) "ac"
[3]=>
string(2) "ba"
[4]=>
string(2) "bb"
[5]=>
string(2) "bc"
[6]=>
string(2) "ca"
[7]=>
string(2) "cb"
[8]=>
string(2) "cc"
}
*/
Getting All combinations from an array PHP
try this:
$courses=array('English','Math','Algebra','History','Computer(lec)');
$sizes = array('1','3','3','3','2');
//maximum 6 hours
$limit=9;
//minimum number of 3 courses
$minimum=3;
$possible= array();
function get_comb($previous, $depth){
global $courses;
$count=count($courses);
global $possible;
global $sizes;
global $limit;
global $minimum;
if ($depth>$count){
$size_of_course=0;
foreach($previous as $nr=>$course){
if($course !== 0){
$size_of_course+=$sizes[$nr];
}
else{
//remove zeros
unset($previous[$nr]);
}
}
if ($size_of_course<=$limit&&count($previous)>=$minimum){
$possible[]=$previous;
}
return;
}
//either you have this course...
get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
//or you dont..
get_comb(array_merge($previous,array(0)),$depth+1);
}
get_comb(array(),1);
//output
echo '<pre>';
var_dump($possible);
in the variable previous the courses add up while the function does recursion.
Explanation:
first, i calculate all the possible combinations.
To do this, I thought of the courses as slots:
whether you take the course or not, possibilities:
course a course b
yes yes
yes no
no yes
no no
this is done with this part of the function. It is a recursive function, so it calls itself within the function:
function get_comb($previous, $depth){
//either you have this course...
get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
//or you dont..
get_comb(array_merge($previous,array(0)),$depth+1);
}
get_comb(array(),1);
assuming this:
$courses=array('course a','course b');
the recursive function calls would look like this (0 means, you dont take that course):
http://img43.imageshack.us/img43/5688/flowdiagram.png
after that, if they fit the requirements I save the possibility in $possible:
because depth=3 and count=2, $depth>$count so this part of the code comes into play:
if ($depth>$count){
$size_of_course=0;
foreach($previous as $nr=>$course){
if($course !== 0){
//the index of $previous is the same as in $courses and $sizes, so
//$previous[1],$courses[1],$sizes[1] is logicaly referring to the same course
//add up all sizes of the courses that are used in this possibility
$size_of_course+=$sizes[$nr];
}
else{
//remove zeros
unset($previous[$nr]);
}
}
//the size of the course has to be lower or same as the size limit
//now without the zeros, count($previous) gives you the amount of courses taken in this possibility
if ($size_of_course<=$limit&&count($previous)>=$minimum){
//if it fits, save this possibility in the $possible array
$possible[]=$previous;
}
return;
}
hope i could help you.
---------------------------------------------edit--------------------------------------
to archieve this: 'if there is computer(lec) it would only accept it as a possible combination if computer(lab) is also present':
replace $possible[]=$previous; with:
//further conditions are placed here
//IMPORTANT: the name of the courses down here (in_array('Computer(lec)') have to be EXACTLY the same as in the array $courses.
//e.g. if in $courses array the name is 'computer(lec)' and down here it's 'Computer(lec)' (uppercase) or 'computer (lec)' (space) it DOES NOT WORK!
//if Computer(lec) is present...
if(in_array('Computer(lec)',$previous)){
//Computer(lab) has to be present too
if(in_array('Computer(lab)',$previous)){
$possible[]=$previous;
}
else {
//if its not present dont save
//do nothing
}
}
else{
//if computer(lec) is not present, no problem, just save
$possible[]=$previous;
}
so the finished code would be
$courses=array('English','Math','Computer(lec)','Computer(lab)');
$sizes = array('1','1','2','2');
//maximum 6 hours
$limit=9;
//minimum 3 courses
$minimum=0;
$possible= array();
function get_comb($previous, $depth){
global $courses;
$count=count($courses);
global $possible;
global $sizes;
global $limit;
global $minimum;
//the end of the $courses array is reached
if ($depth>$count){
$size_of_course=0;
foreach($previous as $nr=>$course){
if($course !== 0){
//the index of $previous is the same as in $courses and $sizes, so
//$previous[1],$courses[1],$sizes[1] is logicaly referring to the same course
//add up all sizes of the courses that are used in this possibility
$size_of_course+=$sizes[$nr];
}
else{
//remove zeros
unset($previous[$nr]);
}
}
//the size of the course has to be lower or same as the size limit
//now without the zeros, count($previous) gives you the amount of courses taken in this possibility
if ($size_of_course<=$limit&&count($previous)>=$minimum){
//further conditions are placed here
//IMPORTANT: the name of the courses down here (in_array('Computer(lec)') have to be EXACTLY the same as in the array $courses.
//e.g. if in $courses array the name is 'computer(lec)' and down here it's 'Computer(lec)' (uppercase) or 'computer (lec)' (space) it DOES NOT WORK!
//if Computer(lec) is present...
if(in_array('Computer(lec)',$previous)){
//Computer(lab) has to be present too
if(in_array('Computer(lab)',$previous)){
$possible[]=$previous;
}
else {
//if its not present dont save
//do nothing
}
}
else{
//if computer(lec) is not present, no problem, just save
$possible[]=$previous;
}
}
return;
}
//either you have this course...
get_comb(array_merge($previous,array($courses[$depth-1])),$depth+1);
//or you dont..
get_comb(array_merge($previous,array(0)),$depth+1);
}
get_comb(array(),1);
//output
echo '<pre>';
var_dump($possible);
How to get all possible string permutations with PHP?
Here is an altered version of the code of Dmitry Tarasov (all credits to him please) which seems to be working properly.
class Combine {
private static $_result = array();
public static function run($str, $replacements){
self::_run($str, $replacements, 0);
return array_values(array_unique(self::$_result));
}
private static function _run($str, $replacements, $start){
self::$_result[] = $str;
for($i = $start, $l = strlen($str); $i < $l; $i++){
self::_run($str, $replacements, $i+1);
if(isset($replacements[$str[$i]])){
foreach($replacements[$str[$i]] as $key => $val){
$str[$i] = $val;
// call recursion
self::_run($str, $replacements, $i+1);
}
}
}
}
}
print_r( Combine::run($str, $replacements) );
The private function was introduced to avoid those heavy array operations to be executed multiple times, while they're not used anywhere but from the root-call.
Related Topics
PHP Link to Image File Outside Default Web Directory
Jquery Mobile: How to Correctly Submit Form Data
MySQL No Connection Could Be Made Because the Target MAChine Actively Refused It
Regex Backreference to Match Different Values
PHP Technique to Query the Apns Feedback Server
Expected Response Code 220 But Got Code "", with Message "" in Laravel
PHP Get Highest Value from Array
Is Making Asynchronous Http Requests Possible with PHP
How to Write Cdata Using Simplexmlelement
Create a Dynamic MySQL Query Using PHP Variables
How to Call a PHP Script/Function on a HTML Button Click
PHP Recursion to Get All Possibilities of Strings
Array_Multisort and Dynamic Variable Options
Post Content-Length Exceeds the Limit