Can you help me find a complex program control structure in php?

October 10, 2006 11:33 AM

I'm writing a php/mySQL script to create new records in my GOALS table by comparing all possible combinations of one or more records from my EXPENSES table with information pulled from my ACCOUNTS table. The actual comparison and record generation should prove relatively simple, but the 'all possible combinations' bit is kicking my butt. I simply cannot fathom a control structure that will facilitate that requirement.

My EXPENSES table currently has six records in it (but I'd rather not have the solution rely on any given quantity of records, since it could vary in the future).

Practical experimentation suggests that there are sixty-three possible combinations of six expenses: twenty different combinations of three expenses, fifteen different combinations of two and four expenses, six different combinations of one and five expenses, and (of course) one combination of all six expenses.

The challenge is finding a control structure (combination of flow statements) that will iterate through all combinations of an arbitrary number of expenses, and so far my normal support group (#php on the dalnet IRC network) has come up empty.

(I believe that I have posed the core of my problem as succinctly and cogently as possible. If I have not been clear enough, here is the question as posed to the #php channel on dalnet, and the implementation of my scripting thus far, which should make my current aim clearer.)

posted by The Confessor to Computers & Internet (9 answers total)

Before thinking about this, you need to fix the gaping security hole in the code you posted. The variable $_GET['macro'] is, after some manipulation, put directly into an SQL query. This means an attacker put could all sorts of nastiness into the querystring resulting in your database being emptied, tables dropped, passwords shown etc etc. You need to look into quote escaping, or using the mysql_real_escape_string() or the mysqli extension. There are various questions on AskMeFi about this.
posted by matthewr at 12:00 PM on October 10, 2006

The techinical term for this kind of attack is SQL injection.
posted by matthewr at 12:02 PM on October 10, 2006

I don't know any php, so take this with a grain of salt, but...
you're looking at a bitmask type situation, right? each expense is either included (1) or not (0)
2^6 = 64 -1 for the 'no expenses' case = 63.
so would a simple loop from 1 up to (2^Expenses.RecordCount - 1) be viable?
posted by juv3nal at 12:11 PM on October 10, 2006

Combinatorics uses the binomial coefficient to calculate the number of combinations of k items taken out of a pool of n objects, without repetition, where order does not matter

For example, A-B-C is the same combination of letters taken out of the alphabet as A-C-B, C-B-A, B-A-C, B-C-A, and C-A-B.

This is read as: n-choose-k.

You can use this PHP code to build a list of combination indices to use to build each SQL statement.

For each expense item 1...n, do an INNER JOIN on a UNION of subquery combinations of k (1 ≤ k ≤ n) EXPENSES records to your ACCOUNTS table.

To do this for ranges (e.g., for three items: 1, 1..2, 2, 1..3, 2..3, 3), you can SELECT * FROM EXPENSES LIMIT k OFFSET 0...k-1.

This will take care of most of your searches.

For the rest (e.g., 1-and-3) you would build a UNION from multiple SELECT w/LIMIT and OFFSET for each specific index, e.g., SELECT * FROM EXPENSES LIMIT 1 OFFSET 5 UNION SELECT * FROM EXPENSE LIMIT 1 OFFSET 14 will return records 6 and 15.
posted by Blazecock Pileon at 12:38 PM on October 10, 2006

I think you need a solution using combinatorics.
Here's an implementation of a combination algorithm in PHP with source code. Enter the total number of elements in the first field and the number you want in the combination in the second to produce all possible combinations (as opposed to permutations, i.e. order doesn't matter). You should be able to use that code, with a simple loop to iterate through the different element counts, to produce the results you need. Just divert the numbers output by that example to walk through an array.
(On preview, I'm posting this anyway as it offers a solution using PHP rather than SQL and choice is almost always a good thing...)
posted by tomsk at 12:39 PM on October 10, 2006

Best answer: There are plenty of libraries out there to handle combination sort permutations, but you're missing the easiest way: just do it in SQL.

SQL is all about combinations, they're called joins.

All combination of two expenses:
select * from Expenses a, Expenses b
All combinations of two expenses where every expense is used only once per combination:
select * from Expenses a, Expenses b where a.id &lgt;> b.id
All combinations of two expenses where every expense is used once, and order of elements is unimportant:
select * from Expenses a, Expenses b where a.id > b.id

For three combinations, first make the two combination select a view:
create view Expenses2Combination as select a.id as aid, b.id as bid, a.name as aname, b.name as b.name from Expenses a, Expenses b where a.id > b.id

Now join a third copy of Expenses to the view, to get combinations of three expenses
select * from Expenses2Combination, expenses c where bid > c.id

For combinations of four, join two copies of Expenses2Combination:
select * from Expenses2Combination a, Expenses2Combination b where a.bid > b.aid

And so forth.

At some point ( more than 16 tables) your SQL engine will complain you've reached the table limit. Just select the result rows of the 16-table join into a temp table, and then join that temp table to another up to 15 tables.
posted by orthogonality at 12:43 PM on October 10, 2006

Response by poster: matthewr
The 'macro' script will reside behind a passworded directory of my hosting, so futher security is of secondary importance... I'll get to it later. Thanks for the heads up, though.

everyone
You've given me some damned good ideas, people.

I'll post the result up here when I get a working script.
posted by The Confessor at 1:46 PM on October 10, 2006

juv3nal's answer is sufficient and much simpler than using a combinatorics library. Something like this:

for ($i = 1; i < (1 << $numExpenses); ++$i) {
    $expenses = array();

    for ($j = 0; $j < $numExpenses; ++$j) {
        if ($i & (1 << $j)) {
            $expenses[] = $j;
        }
    }

    // Now $expenses lists which expense
    // records to process this iteration.
}
posted by Khalad at 3:35 PM on October 10, 2006 [1 favorite]

Response by poster: Promised I'd update with my solution.

Here it is.

Thanks again for all of your help.
posted by The Confessor at 8:24 PM on October 10, 2006