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
)
)
Generate all combinations of string in PHP
Dont take this for production:
$string = implode('',array_unique(str_split('helpa')));
$i=0;
while($i++<50000){
$coll[substr(str_shuffle($string),0,mt_rand(1,strlen($string)))]=true;
}
ksort($coll);
print '<pre>';
print_r(array_keys($coll));
Here you can test what you want to get.
In 10000 iteration i was getting 325 combinations from a 5 length string
(what seems all possible combinations)
How to generate permutation of string, but without repeats and different length?
Here you go :
function pc_array_power_set($array) {
// initialize by adding the empty set
$results = array(array());
foreach ($array as $element)
foreach ($results as $combination)
array_push($results, array_merge(array($element), $combination));
return $results;
}
From PHP Cookbook
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
PHP - How to create all possibility from a string
Here there is a pair of functions that lets you calculate a permutation set
(no repetitions are taken in account)
function extends_permutation($char, $perm) {
$result = [];
$times = count($perm);
for ($i=0; $i<$times; $i++) {
$temp = $perm;
array_splice($temp, $i, 0, $char);
array_push($result, $temp);
}
array_push($result, array_merge($perm, [$char]));
return $result;
}
function extends_set_of_permutations($char, $set) {
$step = [];
foreach ($set as $perm) {
$step = array_merge($step, extends_permutation($char, $perm));
}
return $step;
}
you can use them to generate the required set of permutations. Something like this:
$seed = "XjYAKpR";
// the first set of permutations contains only the
// possible permutation of a one char string (1)
$result_set = [[$seed[0]]];
$rest = str_split(substr($seed,1));
foreach($rest as $char) {
$result_set = extends_set_of_permutations($char, $result_set);
}
$result_set = array_map('implode', $result_set);
sort($result_set);
At the end of the execution you will have the 5040 permutations generated by your string in the result_set array (sorted in alphabetical order).
Add a char and you will have more than 40000 results.
The functions are quite naive in implementation and naming, both aspects can be improved.
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"
}
*/
How to create possible combinations of strings from string in php?
Convert string characters to an array, create all possible combination by creating two loops.
example:This code works perfectly(tested).
<?PHP
function create_possible_arrays(&$set, &$results)
{
for ($i = 0; $i < count($set); $i++)
{
$results[] = $set[$i];
$tempset = $set;
array_splice($tempset, $i, 1);
$tempresults = array();
create_possible_arrays($tempset, $tempresults);
foreach ($tempresults as $res)
{
$results[] = $set[$i] . $res;
}
}
}
$results = array();
$str = 'abc'; //your string
$str = str_split($str); //converted to array
create_possible_arrays($str, $results);
print_r($results); //displaying all results
?>
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.
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"
}
Related Topics
Declaration of Methods Should Be Compatible With Parent Methods in PHP
Method="Post" Enctype="Text/Plain" Are Not Compatible
Print String With a PHP Variable in It
How to Resolve Ambiguous Column Names When Retrieving Results
How to Select and Upload Multiple Files With HTML and PHP, Using Http Post
Full Secure Image Upload Script
Change Cart Item Prices in Woocommerce 3
PHP: How to Get All Possible Combinations of 1D Array
Keeping Session Alive With Curl and PHP
Generating a Random Password in PHP
PHP Xml How to Output Nice Format
What Is the Best Method to Merge Two PHP Objects
PHP Fatal Error: Cannot Redeclare Class
What's the Best Way to Get the Last Element of an Array Without Deleting It