ExcelBanter - View Single Post - PLEASE READ IF YOU PROGRAM: Help Continue Visual Basic

Harlan Grove

wrote...
....
1) you have a table called N1 that has the numbers from 1 to 100
2) you have a table called N2 that has the numbers from 1 to 100

if you want to cartesian these two tables; to make every possible
combination; all you need to do is

SELECT N1.N AS N1, N2.N AS N2 FROM N1, N2

this will give you a nice little combination of every possible
combination for N1 and N2.

Which in your example gives 10000 combinations. There are only 9900
permutations of 100 distinct numbers, 9900 = 100 * 99 = 100! / 99! /
1!, or 100 choose 2. You could add a WHERE clause specifying that N1
not equal N2 to get all permutations of 2 items drawn from 100 items.

Very good. That's permutations of 2 items. How about complete
permutations, i.e., permutations of all 100 distinct numbers? That
get's messy using your approach. Do you generate the permutations
incrementally, requiring 99 different queries with the one above
converted into an INSERT query to generate a table named NT2, and the
permutations of 3 items given by

SELECT TN2.N1, TN2.N2, N1.N AS N3 FROM TN2, N1
WHERE ((TN2.N1 < N3) AND (TN2.N2 < N3))

Writing 99 queries in which all clauses keep growing isn't exactly
simple, but it'd work. It also isn't efficient. It's at least
O(N!*N^2). The generator formula approach I provided several months ago
is O((N+1)!*log(N)). And storagewise, I only need one cell for each
item in each of the permutations. Your approach (rather the one I've
extrapolated from your faulty 2 item beginning), even if intermediate
tables were deleted after each cartesian the final cartesian would use
TN99 to generate TN100, with TN99 having 99! records of 99 fields each
(9.24*10^157) and TN100 having 100! records of 100 fields each
(9.33*10^159).

Now all the computers in all the world at the current time couldn't
even generate all these permutations, so it's a moot point for N = 100.
FWIW, N = 12, TN11 would have a mere 439 million entries and TN12 just
5.75 billion. And it'd only take your approach 69 billion compares to
achieve it. My generator formulas would require only 6.7 billion
compares. OLAP may be good, but it's not good enough to offset that
differential.

Select Y.YYYY, M.MMM FROM tblYEAR Y, tblMONTH M

This would give you a nice little 'spreadsheet' of every combination of
years and months.
....

Kinda like having years listed in A2:A101 and months in B1:M1,
selecting B2:M101, typing the formula =$A2&" "&B$1, and pressing
[Ctrl]+[Enter]. Or just using nested For loops. Yes, this is an example
of what database do well (generating FULL cartesians). Generating
partial combinations, like permutations, takes more work (and fuller
understanding).