2

I need help finding all possible combination of value in database, for Example i have this table:

ITEM_SET           Support  
I1               0.244999999
I2               0.274999999     
I3               0.258333333    
I4               0.103333333

i need to find all possible combination like this :

I1,I2    I1,I2,I3    I1,I2,I3,I4
I1,I3    I1,I2,I4
I1,I4    I1,I3,I4
I2,I3    I2,I3,I4
I2,I4 
I3,I4

*Please note that this formatting meant only to help reading, as what i need is only a list of the possible combination like this Table:

ITEMSET
I1               
I2                    
I3                 
I4  
I1,I2    
I1,I3    
I1,I4    
I2,I3    
I2,I4 
I3,I4
I1,I2,I3 
I1,I2,I4 
I1,I3,I4 
I2,I3,I4   
I1,I2,I3,I4
Rico
  • 244
  • 4
  • 12
  • Which flavor of SQL/RDBMS? E.g. MySql, Sql Server, Oracle etc.? – Paul Sasik Dec 04 '10 at 06:41
  • Seconded. While my answer covers a pseudo-ANSI SQL approach that works in MySQL, having more context might give us potential optimizations. I'm still interested in the main problem you're trying to tackle, though. – MrGomez Dec 04 '10 at 07:12
  • i'm working with msaccess, refer to my comment below for the big picture. in short it's a part of apriori algorithm – Rico Dec 04 '10 at 07:19

2 Answers2

3

What you're suggesting is an n! combination of all of the elements for lengths 1-n. Ignoring the possibility of using a code generator to create your elements, you could do something like this for each combination (in MySQL):

One item:

SELECT item from ITEM_SET;

Two items:

SELECT one.item,two.item from ITEM_SET as one, ITEM_SET as two where one.item != two.item;

Three items:

SELECT one.item,two.item,three.item from ITEM_SET as one, ITEM_SET as two, ITEM_SET as three where one.item != two.item and one.item != three.item and two.item != three.item;

Rinse and repeat. To be pedantic, I define ITEM_SET as my table name and item as my attribute, which is a more meaningful table composition.

This and the related question are code smells to me, though. If you're walking all permutations of elements programmatically for all candidate answers, there's likely a much simpler algorithm to solve your problem. Given your other question is directly related to this one, perhaps you can offer more background information?

Community
  • 1
  • 1
MrGomez
  • 23,788
  • 45
  • 72
  • yup it's related :D since there's low response on my other question i divide the problem into smaller stack :) here's the big picture [Data Mining](http://stackoverflow.com/questions/4349698/sql-data-mining-operation-using-sql-query-fuzzy-apriori-algorithm-how-do-i) – Rico Dec 04 '10 at 06:59
  • Here's some rep. Comment away. ;-) Nice answer btw. – Paul Sasik Dec 04 '10 at 07:05
1

One of the most simple algorithms for generating combinations is bit counting.
Pseudo-code

N items, indexed 1-N

for i=1 to 2^N-1 
   for each bit in i
      if bit is set, output item[i]

Example for N=4:

N = 4, 2^4 = 16
i = 1:  binary = 00000001 -> output I1
i = 2:  binary = 00000010 -> output I2
i = 3:  binary = 00000011 -> output I1, I2
i = 4:  binary = 00000100 -> output I3
i = 6:  binary = 00000101 -> output I1, I3
i = 7:  binary = 00000111 -> output I1, I2, I3
i = 8:  binary = 00001000 -> output I4
i = 9:  binary = 00001001 -> output I1, I4
i = 10: binary = 00001010 -> output I2, I4
i = 11: binary = 00001011 -> output I1, I2, I4
i = 12: binary = 00001100 -> output I3, I4
i = 13: binary = 00001011 -> output I1, I2, I4
i = 14: binary = 00001110 -> output I2, I2, I4
i = 15: binary = 00001111 -> output I1, I2, I3, I4
Pavel Urbančík
  • 1,466
  • 9
  • 6