Get all permutations of a PHP array?
function pc_permute($items, $perms = array()) {
if (empty($items)) {
echo join(' ', $perms) . "<br />";
} else {
for ($i = count($items) - 1; $i >= 0; --$i) {
$newitems = $items;
$newperms = $perms;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
pc_permute($newitems, $newperms);
}
}
}
$arr = array('peter', 'paul', 'mary');
pc_permute($arr);
or
function pc_next_permutation($p, $size) {
// slide down the array looking for where we're smaller than the next guy
for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }
// if this doesn't occur, we've finished our permutations
// the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
if ($i == -1) { return false; }
// slide down the array looking for a bigger number than what we found before
for ($j = $size; $p[$j] <= $p[$i]; --$j) { }
// swap them
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
// now reverse the elements in between by swapping the ends
for (++$i, $j = $size; $i < $j; ++$i, --$j) {
$tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
}
return $p;
}
$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;
do {
foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);
foreach ($perms as $p) {
print join(' ', $p) . "\n";
}
http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm
Get all permutations from multiple arrays PHP
I've taken the cartesian function from this answer, and given the output you've wanted.
(Credit to sergiy for creating the function)
https://eval.in/199787
<?php
$array = Array
(
'colour' => Array
(
1130,
1131,
1132,
1133
),
'size' => Array
(
1069,
1070
)
);
echo "<pre>";
$arrFinalArray = cartesian($array);
foreach( $arrFinalArray as $arrIndie) {
//We know each as 2 keys
$arrKeys = array_keys($arrIndie);
$arrValues = array_values($arrIndie);
echo $arrKeys[0] ." ". $arrValues[0] ." - ". $arrKeys[1] ." ". $arrValues[1] ."<br />";
}
echo "</pre>";
function cartesian($input) {
// filter out empty values
$input = array_filter($input);
$result = array(array());
foreach ($input as $key => $values) {
$append = array();
foreach($result as $product) {
foreach($values as $item) {
$product[$key] = $item;
$append[] = $product;
}
}
$result = $append;
}
return $result;
}
How can I build an array of all possible permutations in PHP from 4 distinct 'scenarios'?
You will require 3 nested loops for this.
- First outer loop to loop over all cats.
- Second outer loop to loop over all previously collected combination results for previous cats.
- Third inner loop to add current cat and collar combination to previously collected result.
The code below I believe is readable accordingly.
<?php
$collars = array('yellow','blue','green','pink');
$cats = array('bob','frank');
$result = [[]];
foreach($cats as $cat){
$temp = [];
foreach($result as $r){
foreach($collars as $collar){
$temp[] = array_merge($r, [ $cat => $collar]);
}
}
$result = $temp;
}
print_r($result);
Total combinations possible is not 4n all the time.
Say, size of cats is m and size of collars is n.
So, total combinations possible is nm.
Permutations - all possible sets of numbers
You're looking for the permutations formula:
nPk = n!/(n-k)!
In your case, you have 9 entries and you want to choose all of them, that's 9P9 = 9! = 362880
You can find a PHP algorithm to permutate in recipe 4.26 of O'Reilly's "PHP Cookbook".
pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8));
Copied in from O'Reilly:
function pc_permute($items, $perms = array( )) {
if (empty($items)) {
print join(' ', $perms) . "\n";
} else {
for ($i = count($items) - 1; $i >= 0; --$i) {
$newitems = $items;
$newperms = $perms;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
pc_permute($newitems, $newperms);
}
}
}
PHP - All permutations in a 2D array - Unique and ordered values
Since any candidate can't be smaller than his previous, then any position can't be repeated in the chain. The following code does the trick, check if it works for you.
<?php
function permute()
{
$result = array();
if (func_num_args() == 0)
return $result; // empty array
foreach (func_get_arg(0) as $value)
nextPermute($result, $value, $value, 1, func_get_args());
return $result;
}
function nextPermute(&$result_array, $permute_value,
$last_value, $next_arg, $all_args)
{
if ($next_arg < count($all_args))
{
foreach ($all_args[$next_arg] as $value)
if ($value > $last_value)
nextPermute($result_array, $permute_value . '-' . $value, $value, $next_arg + 1, $all_args);
}
else
array_push($result_array, $permute_value);
}
$cross = permute(
array('1', '2', '3'),
array('3', '4', '5'),
array('4', '5')
);
print_r($cross);
?>
how to find multidimensional array permutation in php
TL;DR: Square the matrix, then use brute force to generate every possible column rotation. When one rotation has no duplicate column values, stop. See it live on 3v4l.org.
My other answer provides a compact solution if and only if all rows contain all possible values (in any order). Here's an example. My previous answer guarantees a solution to the matrix on the left, but not the one on the right:
Satisfies Does not satisfy
[ [
[ 'X', 'Y' ], [ 'X', 'Y' ],
[ 'Y', 'X' ], [ 'Y' ],
] ]
To handle the general case where any row may contain any arbitrary sub-set of all possible values, we can brute force a solution. Our brute needs to know how to:
- Check if the matrix is solved.
- Systematically evolve the matrix toward a solution.
The first one is easy to write. For every column in a given a square matrix, check if the number of unique, non-wildcard values differs from the number of values. If so, then at least one non-wildcard value is duplicated in that column:
function matrix_is_solved(array $matrix) {
foreach (array_keys(current($matrix)) as $offset) {
$column = array_filter($raw = array_column($matrix, $offset));
if (count($column) != count(array_unique($column))) return false;
}
return true;
}
The second part requires a trick. Observe that one can apply a vector to any square matrix to rotate values in the matrix. I'll skip the math and just show some examples:
original = [
[ 'X', 'Y' ],
[ 'Y', 'X' ],
]
vector = [ 0, 0 ] // rotate 1st row 0 places, 2nd row 0 places
result = [
[ 'X', 'Y' ],
[ 'Y', 'X' ],
]
vector = [ 1, 0 ] // rotate 1st row 1 place, 2nd row 0 places
result = [
[ 'Y', 'X' ],
[ 'Y', 'X' ],
]
vector = [ 0, 1 ] // rotate 1st row 0 places, 2nd row 1 place
result = [
[ 'X', 'Y' ],
[ 'X', 'Y' ],
]
vector = [ 1, 1 ] // rotate 1st row 1 place, 2nd row 1 place
result = [
[ 'Y', 'X' ],
[ 'X', 'Y' ],
]
Since there are 2 rows of 2 columns each, there are exactly 4 combinations of rotation vectors (all listed above). Of these four vectors, two - [ 0, 0 ] and [ 1, 1 ] - produce a solution. Since we only need one solution, it's sufficient to stop on the first vector that produces a solved matrix.
Knowing this, here's how we'll write our brute: generate all possible rotation vectors, try each one against our puzzle, and return if the transformed matrix is in a solved state:
function matrix_generate_vectors(array $matrix) {
$vectors = [];
$columns = count(current($matrix));
$gen = function ($depth=0, $combo='') use (&$gen, &$vectors, $columns) {
if ($depth < $columns)
for ($i = 0; $i < $columns; $i++)
$gen($depth + 1, $i . $combo);
else
$vectors[] = array_map('intval', str_split($combo));
};
$gen();
return $vectors;
}
function matrix_rotate(array $matrix, array $vector) {
foreach ($matrix as $row => &$values) {
array_rotate($values, $vector[$row]);
}
return $matrix;
}
function matrix_brute_solve(array $matrix) {
matrix_make_square($matrix);
foreach (matrix_generate_vectors($matrix) as $vector) {
$attempt = matrix_rotate($matrix, $vector);
if (matrix_is_solved($attempt))
return matrix_display($attempt);
}
echo 'No solution';
}
We'll also need some helpers, a test harness, and some tests:
function array_rotate(array &$array, $offset) {
foreach (array_slice($array, 0, $offset) as $key => $val) {
unset($array[$key]);
$array[$key] = $val;
}
$array = array_values($array);
}
function matrix_display(array $matrix = null) {
echo "[\n";
foreach ($matrix as $row => $inner) {
echo " $row => ['" . implode("', '", $inner) . "']\n";
}
echo "]\n";
}
function matrix_make_square(array &$matrix) {
$pad = count(array_keys($matrix));
foreach ($matrix as &$row)
$row = array_pad($row, $pad, '');
}
$tests = [
[ ['X'], ['X'] ],
[ ['X'], ['X'], ['X'] ],
[ [ 'X', '' ], [ '', 'X' ] ],
[ ['X', 'Y', 'Z'], ['X', 'Y'], ['X']],
[ ['X', 'Y'], ['X', 'Y'], ['X', 'Y'] ],
[ ['X', 'Y', 'Z'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'] ],
[ ['X', 'Y', 'Z', 'I', 'J'], ['X', 'Y', 'Z', 'I'], ['X', 'Y', 'Z', 'I'], ['X', 'Y', 'Z', 'I'], ['X', 'Y', 'Z'], ['X', 'Y', 'Z'] ],
];
array_map(function ($matrix) {
matrix_display($matrix);
echo "solved by:" . PHP_EOL;
matrix_brute_solve($matrix);
echo PHP_EOL;
}, $tests);
Which produces for those tests (just a few examples):
[
0 => ['X', 'Y', 'Z']
1 => ['X', 'Y', 'Z']
2 => ['X', 'Y', 'Z']
]
solved by:
[
0 => ['Z', 'X', 'Y']
1 => ['Y', 'Z', 'X']
2 => ['X', 'Y', 'Z']
]
[
0 => ['X', 'Y', 'Z', 'I', 'J']
1 => ['X', 'Y', 'Z', 'I']
2 => ['X', 'Y', 'Z', 'I']
3 => ['X', 'Y', 'Z', 'I']
4 => ['X', 'Y', 'Z']
5 => ['X', 'Y', 'Z']
]
solved by:
[
0 => ['', 'X', 'Y', 'Z', 'I', 'J']
1 => ['', '', 'X', 'Y', 'Z', 'I']
2 => ['I', '', '', 'X', 'Y', 'Z']
3 => ['Z', 'I', '', '', 'X', 'Y']
4 => ['Y', 'Z', '', '', '', 'X']
5 => ['X', 'Y', 'Z', '', '', '']
See it live at 3v4l.org.
The vector generator is O(nn) in both time and space. So, if you had a 3x3 square matrix, there would be 33 = 27 iterations and stored array elements. For 4x4, you'd have 44 = 256. You get the idea. The generator can be improved to be O(1) in space, but being that it's a depth-first algorithm, it'll always be O(nn) in time.
Also, as implemented, the algorithm stops when it finds the first solution. A trivial modification would allow you to find all solutions. An interesting addition to this puzzle would be to find the solution with the fewest rotations.
How to return permutations of an array in PHP?
Because you are using static $permuted_array;
you must use
static $permuted_array; // declare static var, if you don't want to use static property of variable, then why are you using this
$permuted_array = array(); // set its value to array()
using static $permuted_array = array(); will not set its value to array() after first iteration
function array_2D_permute($items, $perms = array(), $isNew = false) {
static $permuted_array = array();
if($isNew)
$permuted_array = array();
if (empty($items)) {
$permuted_array[]=$perms;
#print_r($new);
#print join(' ', $perms) . "\n";
} else {
for ($i = count($items) - 1; $i >= 0; --$i) {
$newitems = $items;
$newperms = $perms;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
array_2D_permute($newitems, $newperms);
}
return $permuted_array;
}
}
$arr1=array("Architecture","Mexico","Periodicals");
$result1=array_2D_permute($arr1, array(), true); //
print_r($result1);
$arr2=array("Apple","Boat","Cat");
$result2=array_2D_permute($arr2, array(), true); ///
print_r($result2);
one more parameter is added $isNew. Send true if you want to get result for new array.
How to get all permutations with a desired length out of a string?
This should work for you and even without evil().
So what does this code do?
1. How many permutations are there?
Pretty simple:
nl = amount of permutations
Where n is the amount of words and l the desired length of each combination.
So for this specific example there are 3 words (apple, patatoes and orange) and we want each permutation with a length of 3. Means:
33 = 27 permutations
2. Getting all permutations together
We loop through all our permutations, which we already have(Starting off with one permutation, an "empty permutation" ($permutations = [[]];)), and for each permutation we go through our data array and combine each permutation with each input data to a new permutation.
Now we do this until we get the desired length for each permutation.
2.1 Example
Input data:
[1, 2] //Input array with the data
length = 2 //Desired length for each permutation
//↓ new permutations for the next iteration
│
iteration 0:
Permutations:
- [] │ -> []
│
iteration 1: ┌─────────────┤
│ │
Permutations: v v
- [] + 1 │ -> [1]
- [] + 2 │ -> [2]
│
iteration 2: ┌─────────────┤
│ │
Permutations: v v
- [] + 1 │ -> [1]
- [] + 2 │ -> [2]
- [1] + 1 │ -> [1,1] //desired length 2
- [1] + 2 │ -> [1,2] //desired length 2
- [2] + 1 │ -> [2,1] //desired length 2
- [2] + 2 │ -> [2,2] //desired length 2
//↑ All permutations here
So as you can see in the above example we now have all permutations with the desired length which we want, here 2.
But to get only the permutations with the desired length we are overwriting the result array each iteration, so that at the end only the permutations with the expected length are in the results array.
3. Code:
<?php
function getPermutations($input = [], $length = 2, $delimiter = ",") {
$permutations = [[]];
$data = is_array($input) ? $input : explode($delimiter, $input);
for ($count = 0; $count < $length; $count++) {
$tmp = [];
foreach ($permutations as $permutation) {
foreach ($data as $inputValue)
$tmp[] = array_merge($permutation, [$inputValue]);
}
$permutations = $tmp;
}
return $permutations;
}
$result = getPermutations("apple,patatoes,orange", 3);
print_r($result);
?>
output:
Array
(
[0] => Array
(
[0] => apple
[1] => apple
[2] => apple
)
//...
[26] => Array
(
[0] => orange
[1] => orange
[2] => orange
)
)
Related Topics
Why Does MySQLi Num_Rows Always Return 0
Why Is the Hash Part of the Url Not Available on the Server Side
Set Up the Base Url in Codeigniter
Warning: MySQLi_Query() Expects Parameter 1 to Be MySQLi, Null Given In
Simple Jquery, PHP and Jsonp Example
"Cannot Send Session Cache Limiter - Headers Already Sent"
Send File Attachment from Form Using PHPmailer and PHP
Insert Array into MySQL Database With PHP
Curl and PHP - How to Pass a Json Through Curl by Put,Post,Get
Post an Array from an HTML Form Without JavaScript
How to Get Directory Size in PHP
What Is the "-≫" PHP Operator Called
Loading .SQL Files from Within PHP
Selecting Unique Values from a Column
PHP Json_Encode Encoding Numbers as Strings
Url Rewriting: Css, Js, and Images Not Loading