Permuting Touch-Tone keypad combinations

DaveRandom

Hello all

I have been trying to do this for days and it is driving me round the bend. I am sure it is possible, but I cannot for the life of me figure out how to do it.

I need to interpret touch-tone key presses, and figure out what possible combinations relate to the keys pressed. So it a user entered '222' on their touch tone keypad, this could mean 'aaa', 'aab', 'aac', 'aba', 'abb' ... 'ccc'.

What I want to do is take a variable length input string, and permute it into all possible interpretations, into an indexed array. The element order is not significant, but I figure any way of doing it will probably put elements in the order as specified above.

I would like ALL possible interpretations - I am not bothered about only getting valid character strings from a dictionary.

I am aware this could take a lot of processing for more than a few characters, as the number of possible permuations increases exponentially with every additional key, but this is also not a problem.

I have got this far...

<?php

  $query = '222';

  $keys = array(
    '2'=>array('a','b','c'),
    '3'=>array('d','e','f'),
    '4'=>array('g','h','i'),
    '5'=>array('j','k','l'),
    '6'=>array('m','n','o'),
    '7'=>array('p','q','r','s'),
    '8'=>array('t','u','v'),
    '9'=>array('w','x','y','z')
  );

  $results = array();
  $qlength = strlen($query);

  for ($i = ($qlength - 1); $i >= 0; $i--) { // Loop through input chars backwards
    for ($j = ($qlength - 1); $i >= $j; $j--) { // Loop though chars ahead of current char backwards
      // Something horrible which loops through chars an unknown number of times and adds strings to the $results array
    }
  }

?>

I know this is throughly unhelpful, but all my attempts at building the looping structure have been miserable failures.

The real problem, so far as I can work out, is that the input string is of a variable length (it could be '2', it could be '22', it could be '222' etc etc).

Any ideas gratefully recieved.

Cheers

Chris

DaveRandom

No-one has any ideas? Well that is disappointing... 😃

I am still pulling my hair out over this, if I come up with the answer I'll put it on here

Res

Let me fish around and see if I have some code that can help you out. One of my guys was trying to find all the possible dice rolls for X six-sided dice. If he figured that out I think it could help you here.

Res

Apparently he never got it working how he wanted to. It looks like these functions might help, but trying to get an array of unique strings to feed to these functions is a bit of a headache. I'd be interested in your results if you can get it working. It's a fun problem so I will take a stab at it tonight, but the 30 minutes I did attempt hurt my brain.

DaveRandom

No worries Res, if you can manage it will will buy you a v. large virtual beer... 😃

Res

Didn't get a chance last night, but will be working on it this weekend. Between your issue and wanting to make a dice probability calculator (probability of getting Y value when X dice are rolled), I really want to crack this one.

DaveRandom

Right.

  class permute_touchtone {

var $keys = array( 
  '2'=>array('a','b','c'), 
  '3'=>array('d','e','f'), 
  '4'=>array('g','h','i'), 
  '5'=>array('j','k','l'), 
  '6'=>array('m','n','o'), 
  '7'=>array('p','q','r','s'), 
  '8'=>array('t','u','v'), 
  '9'=>array('w','x','y','z') 
);
var $combinations = array();

function permute ($str) {
  $combos = array();
  foreach (str_split($str) as $key) if (isset($this->keys[$key])) $combos[] = $this->keys[$key];
  $this->helper($combos);
  return $this->combinations;
}

function helper ($combos, $str = '', $i = 0) {
  if ($i >= count($combos)) {
    $this->combinations[] = trim($str);
  } else {
    foreach ($combos[$i] as $combo) $this->helper($combos, "$str$combo", $i + 1);
  }
}

  }

  $touch = new permute_touchtone;
  print_r($touch->permute('222'));

That works, albeit in a horrible way. I pinched the 'helper' method from here, but found that I had to wrap it in a class, as I couldn't find a satisfactory way to pass the return array through the recursion.

It's written in that v. basic syntax as it has to work on a PHP4 box (a phone system with no compilers, so I can't upgrade it).

If anyone can find a tidy way of wrapping all that into a single routine (i.e. a procedural function) I would be glad to know, I can't do it because I have been staring at it for too long.