PHP MySQL for permutations on MySQL Table

Question

I have a mysql table with 7 columns, on which with each row contains integer values.

I have a simple site which receives values from the user and I have to try to see if the values sent by the user match or are similiar to any of the rows in the table.

So the user writes e.g. 1 2 3 4 5 6 7 as input.

I have to find out if any of the rows in my table are similar to it without order. So 1 2 3 4 5 6 7 = 7 6 5 4 3 2 1 and so on. The table my contain more than 40,000 rows of data.

I also have to see if they share at least 5, 6 or 7 digits in common.

This means using permutations to find all possible combinations. However what is the best approach for such a problem?

1. Take the input from the user and get all permutations and match against first row, second row, etc and report if found? Alternatively, do the reverse, get a row from the table and get all permutations and do the match against the user input?

2. What about memory and CPUusage when going through such a big table with so many permutations?

Answer 1

In a full normalized schema this is a single having query

Let's suppose your table with pk as:

create table T1 
( pk char (1), a1 int, a2 int, a3 int, a4 int, a5 int, a6 int, a7 int);

insert into T1 values 
('a',1,2,3,4,5,6,7),
('b',2,3,4,5,6,7,8),
('z',10,11,12,13,14,15,16);

At this time, we can normalize data as:

select
   pk, 
   case a
    when 1 then a1
    when 2 then a2
    when 3 then a3
    when 4 then a4
    when 5 then a5
    when 6 then a6
    when 7 then a7
   end
   as v
from T1   
cross join 
   (select 1 as a from dual union all
    select 2 as a from dual union all
    select 3 as a from dual union all
    select 4 as a from dual union all
    select 5 as a from dual union all
    select 6 as a from dual union all
    select 7 as a from dual ) T2

In the previous query, it is easy to match your requirements with a single having:

select pk
from
(
select
   pk, 
   case a
    when 1 then a1
    when 2 then a2
    when 3 then a3
    when 4 then a4
    when 5 then a5
    when 6 then a6
    when 7 then a7
   end
   as v
from T1   
cross join 
   (select 1 as a from dual union all
    select 2 as a from dual union all
    select 3 as a from dual union all
    select 4 as a from dual union all
    select 5 as a from dual union all
    select 6 as a from dual union all
    select 7 as a from dual ) T2
) T
where
   T.v in ( 4,5,6,7,8,9,10)
group by pk
having                                           <-- The Having
   count( pk ) > 4

Results:

| PK |
------
|  b |

Answer 2

a light method might be to add an additional field in your database, which is a numerically ordered version of all 7 fields combined.

eg. if the data in the database was 2 4 7 6 5 1 3 , the combination field would be 1234567

Then when comparing, sort the users response numerically and compare against the combination field in the database.

Depending on what you are doing, you could write your query like this

select * from table where combination like '12%' or combination like '123%' 

If you know what the minimum number of matching numbers needs to be , that would lighten up the query

To find out how similar what they wrote vs what is in the database. You could use the levenshtein PHP function: http://php.net/manual/en/function.levenshtein.php

$result = levenshtein($input,$combination);