views:

765

answers:

6

I'd like to get all the permutations of swapped characters pairs of a string. For example:

Base string: abcd Combinations:

  1. bacd
  2. acbd
  3. abdc

etc.

What's the best way to do this?

+2  A: 

Edit: Markdown hates me today...

$input = "abcd";
$len = strlen($input);
$output = array();

for ($i = 0; $i < $len - 1; ++$i) {
    $output[] = substr($input, 0, $i)
              . substr($input, $i + 1, 1)
              . substr($input, $i, 1)
              . substr($input, $i + 2);
}
print_r($output);
nickf
That doesn't give every possible version though, does it? Unless I'm misunderstanding OP's question.
HoboBen
HoboBen i ment to swap only letters that are next to each other. like first with second, second with third but not third with sixth.
Chris
A: 

Related concept: Damerau–Levenshtein distance.

eed3si9n
+1  A: 

nickf made beautiful solution thank you , i came up with less beautiful:

  $arr=array(0=>'a',1=>'b',2=>'c',3=>'d');
  for($i=0;$i<count($arr)-1;$i++){
  $swapped="";
  //Make normal before swapped
  for($z=0;$z<$i;$z++){
   $swapped.=$arr[$z];
  }
  //Create swapped
  $i1=$i+1;
  $swapped.=$arr[$i1].$arr[$i];

  //Make normal after swapped.     
  for($y=$z+2;$y<count($arr);$y++){
  $swapped.=$arr[$y];

  }
$arrayswapped[$i]=$swapped;
}
var_dump($arrayswapped);
Chris
+1  A: 

A fast search in google gave me that:

http://cogo.wordpress.com/2008/01/08/string-permutation-in-php/

Georg
A: 

How about just using the following:

function swap($s, $i)
{
  $t = $s[$i];
  $s[$i] = $s[$i+1];
  $s[$i+1] = $t;

  return $s;
}

$s = "abcd";
$l = strlen($s);
for ($i=0; $i<$l-1; ++$i)
{
  print swap($s,$i)."\n";
}
mweerden
why make that function change the string by reference, just to change it back again? Why not just make the change and return the new string?
nickf
I was trying to be smart and avoid string creations. However, it was a bit of a premature optimisation and one that is probably useless in most cases. Also, I hardly know PHP (or its memory model), so I actually don't know whether it was a optimisation. I changed it now; thanks for your comment.
mweerden
A: 

Here is a slightly faster solution as its not overusing substr().

function swapcharpairs($input = "abcd") {
  $pre = "";
  $a="";
  $b = $input[0];
  $post = substr($input, 1);
  while($post!='') {
    $pre.=$a;
    $a=$b;
    $b=$post[0];
    $post=substr($post,1);
    $swaps[] = $pre.$b.$a.$post;
  };
  return $swaps;
}

print_R(swapcharpairs());
Czimi