Permutate at string in PHP using external array of letters

Question

UPDATE: Let me rephrase my question:

Take a string: (x)ello (y)orld

I want to find all possible combinations where i put in the letters w,z and c in place of (x) and (y) using PHP. My approach below was clearly wrong...

OLD QUESTION

I'm working on a PHP-function to find all possible combinations of a string replacing certain characters with a list of characters.

Say the string is "Hello World" and I want to find all possible combinations where I replace H and W with P and K and S so the result will be:

Hello World
Pello World
Pello Porld
Pello Korld
Hello Korld
Hello World
Kello Porld
Sello Porld
Sello Sorld
Hello Sorld
...

and so on. The list should contain all possible combinations.

This is what i got so far:

/**
 * Get all permuations of a string based on an array of translations
 *
 * @author Kovik :) http://koviko.net/
 * @param string $str
 * @param array $rules
 * @return array
 */
function get_all_permutations($str, array $rules) {
    $rules_power_set = array(array());

    foreach ($rules as $from => $to) {
        foreach ($rules_power_set as $current_set) {
            $rules_power_set[] = array_merge(array($from => $to), $current_set);
        }
    }

    $permutations = array();
    foreach ($rules_power_set as $rules) {
        $permutations[] = strtr($str, $rules);
    }

    return $permutations;
}

$rules = array(
    'H' => 'S',
    'H' => 'K',
    'H' => 'P',
    'W' => 'S',
    'W' => 'K',
    'W' => 'P'

);

$input = "Hello World";
$permutations = get_all_permutations($input, $rules);
print_r($permutations);

Result:

Array
(
[0] => Hello World
[1] => Pello World
[2] => Hello Porld
[3] => Pello Porld
)

I hope it makes sense and someone has cracked this nut :-)

it's a;ready clear, replace H and W with P and K and S with any occurrences — George G
– George G, Commented Aug 15, 2014 at 9:29
your $rules array is wrong at final state it contains just 2 elements instead of 6, because array keys must be unique — George G
– George G, Commented Aug 15, 2014 at 9:33
Doh, thanks :-) That has been fixed, but obviously i can't use strtr() - it will never work as it required unique keys - and have several translations for the same key... Any ideas for the translation part then? — larsd
– larsd, Commented Aug 15, 2014 at 9:44

George G · Accepted Answer · 2017-12-11 19:17:35Z

1

I don't think this question is duplicate, anyway I can't get the right answer from the link.

Here is the solution (I'll do explain a bit later, how does it work):

/**
 * finds the indexes of characters for replacement letter
 * 
 * @param string $table
 * @param array|string $freeSits array of 
 * letter or string `A|f|p...` can be passed
 * @param bool $caseSensitive
 * @return array
 */
function getSeatNumbers($table, $freeSits, $caseSensitive = false)
{
    if (is_array($freeSits))
    {
        $freeSits= implode('|', $freeSits);
    }

    $flag = $caseSensitive ? '' : 'i' ;


    preg_match_all("/$freeSits/$flag", $table, $match, PREG_OFFSET_CAPTURE);

    $positions = array();
    foreach ($match[0] as $i)
    {
        $positions[] = $i[1];
    }

    return $positions;
}

/**
 * do the sitting
 * @param string $table
 * @param array $seats
 * @param array $guests
 * @param array $variations
 */
function recursiveSitting($table, array $seats, array $guests, &$variations)
{
    $s = $seats;
    while (count($s)) 
    :
        $seat = current($s);
        $s = array_slice($s, 1);
        $t = $table;

        foreach ($guests as $guest) 
        {
            $t[$seat] = $guest;

            if(count($s) > 0)
            {
                recursiveSitting($t,  $s, $guests, $variations);
            }

            $variations[] = $t;
        }

    endwhile;
}


$table = "Hello World";

$freeSits= array('H','W','D');

$guests = array('P','K','S');


$seats = getSeatNumbers($table, $freeSits, true); 
$variations = array($table);
recursiveSitting($table, $seats, $guests, $variations);

echo "<pre>";

//you can sort the array
sort($variations);

print_r($variations);

edited Dec 11, 2017 at 19:17

answered Aug 15, 2014 at 14:22

George G

7,72512 gold badges48 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

MAZux Over a year ago

Hi, at your first line of your first function, you have to change the variable name to $freeSits, now it's $freeSeats ;)

George G Over a year ago

Hi @MAZux thanks for the catch, I've edited my answer. Cheers

Lake · Accepted Answer · 2014-08-15 10:07:24Z

1

Try

<?php
$array  = array("Hello","World");
$rep    = array("H","S","K","P","W");
$c      = array();
foreach($array as $k=>$item):
    foreach($rep as $r):
        $c[$k][] = $r.substr($item,1);
    endforeach;
endforeach;
echo "<pre>";
print_r(myCombine($c));
echo "</pre>";
function myCombine($a)
{
    if(empty($a)) return array();
    $r = array_shift($a);
    foreach($a as $i):
        $s = array();
        foreach($i as $o):
            foreach($r as $j):
                $s[] = $j." ".$o;
            endforeach;
        endforeach;
        $r = $s;
    endforeach;
    return $r;
}
?>

edited Aug 15, 2014 at 10:07

answered Aug 15, 2014 at 9:57

Lake

9134 silver badges6 bronze badges

1 Comment

larsd Over a year ago

Hi! I like your approach, but the string could also be "How are you" where the w is not the first letter in a word... the position of the letters to be replaces are not always the same

ilpaijin · Accepted Answer · 2014-08-15 14:52:37Z

Provided that, because of duplicated indexes, you can't have:

$rules = array(
    'H' => 'S',
    'H' => 'K',
    'H' => 'P',
    ...
);

I was playing around this:

$rules = array(
    array(
        "match" => array("H", "W"),
        "replace" => array("Z", "PC")
    ),    
    array(
        "match" => "W",
        "replace" => array("A","CP")
    )
);    

$input = "Hello World";

$results = array();

foreach ($rules as $k => $rule) 
{
    $inputs = array();

    $strings = array_pad($inputs, count($rule["replace"]), $input);

    foreach ($strings as $key => $string) 
    {
        if(is_array($rule["match"]))
        {
            foreach($rule["match"] as $rulematch)
            {
                $results[] = preg_replace("#(".$rulematch.")#", $rule["replace"][$key], $string);
            }
            $results[] = preg_replace("#[(".implode("?)(", $rule["match"])."?)]#", $rule["replace"][$key], $string);
        }
        else 
        {
            $results[] = preg_replace("#(".$rule["match"].")#", $rule["replace"][$key], $string);
        }
    } 
}

var_dump($results);

that is currently giving me:

array (size=8)
    0 => string 'Zello World' (length=11)
    1 => string 'Hello Zorld' (length=11)
    2 => string 'Zello Zorld' (length=11)
    3 => string 'PCello World' (length=12)
    4 => string 'Hello PCorld' (length=12)
    5 => string 'PCello PCorld' (length=13)
    6 => string 'Hello Aorld' (length=11)
    7 => string 'Hello CPorld' (length=12)

Not a bulletproof solution but just a different perspective to investigate on.

marco811 · Accepted Answer · 2017-12-11 18:45:58Z

0

Works for me:

<?php
$leetDict = array(
'a' => array('@', 'q'),
'w' => array('vv', 'v'),
'l' => array('i', '|')
);

function permute($dictWord) {

    global $leetDict;

    if(strlen($dictWord)==0) return;
    $currentLetter = $dictWord{0};
    $restOfWord = substr($dictWord, 1);

    if(array_key_exists($currentLetter, $leetDict)) {
        $substitutions = $leetDict[$currentLetter];
    } else {
        $substitutions = array($currentLetter);
    }

    if(strlen($restOfWord)>0) {
        $perms = array();

        foreach($substitutions as $s) {

            foreach($substitutions as $s) {
                foreach(permute($restOfWord) as $p) {
                    $perms[] = $s . $p;
                }
            }
        }
    } else {
        $perms = $substitutions;
    }

    return $perms;
}

$result = permute("Hola");
print_r($result);

Returns:

Array
(
    [0] => Hoi@
    [1] => Hoiq
    [2] => Ho|@
    [3] => Ho|q
    [4] => Hoi@
    [5] => Hoiq
    [6] => Ho|@
    [7] => Ho|q
)

answered Dec 11, 2017 at 18:45

marco811

481 silver badge8 bronze badges

1 Comment

Tom Aranda Over a year ago

Generally, answers are much more helpful if they include an explanation of what the code is intended to do, and why that solves the problem without introducing others.

Collectives™ on Stack Overflow

Permutate at string in PHP using external array of letters

4 Answers 4

2 Comments

1 Comment

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related