Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations Westi on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

combinatorial algorithm 1

Status
Not open for further replies.

vasah20

Programmer
Feb 16, 2001
559
US
Hey -
anyone know of a good combinatorial algorithm that I can use?

I'm going to have a result set similar to this:

set A set B set c
1 i a
2 ii b
3 iii
iv

I need to be able to form all the combinations of these three sets.
eg:
1,i,a
1,ii,a
1,iii,a
1,iv,a
2,i,a
2,ii,a
2,iii,a

etc...

anyone have any ideas?
thanks in advance.
leo
 
Hello,
Is the order in which you presented expected results important?
If it is not, your question has simple answer:
just do three nested cycles on index from sets.
<script language=&quot;vbscript&quot;>
seta = array(1,2,3)
setb = array(&quot;i&quot;,&quot;ii&quot;,&quot;iii&quot;,&quot;iv&quot;)
setc = array(&quot;a&quot;,&quot;b&quot;)
Sub pr
for i = 0 to Ubound(seta)
for k = 0 to Ubound (setc)
for j = 0 to Ubound(setb)
MsgBox seta(i) & &quot;, &quot; & setb(j) & &quot;, &quot; & setc(k)
next
next
next
End Sub
</script>

If the order is important, I wish you success in seeking another answer.
D.
 
order is unimportant, but the problem is that I don't know how many sets I'm going to be combining from. it is anywhere from 1 to N number of sets... plus, since this is an ASP solution, the runtime is very important, so I'm trying to limit the number of nested loops I have.

any ideas?
leo
 
Try to use a simple method (i've got 10 on this project in highschool)

let's say we have:


N- nr of sets
for each set we have a number of elements
MAXDIM- max nr of M1...MN

setsdim(N)
sets(N,MAXDIM)

' setsdim(1)=M1
' setsdim(2)=M2
' ...
' setsdim(N)=MN
for i=1 to N do
setsdim(i)=dim_of_set
next 'i

for i=1 to N do
for j=1 to setsdim(i) do
sets(i,j)=value_of_current_set 'introduction of values on each set
next 'j
next 'i

Elements(N) - is tha array that we add 1
for i=1 to N do
Elements(i)=1
next 'i

'and we extract elements from the all sets
str=&quot;&quot;
for i=N downto 1 do
str=str+sets(i,Elements(i))
next 'i

it's like u have an numer with each digit in another base
digit 1 in base M1
digit 2 in base M2
...
digit N in base MN
all u have to do is to write an function that's add 1 to this array of digits (Elements) and be careful to not outbound the digits base

example
if we have N=4 and MAXDIM=100

setsdim(4)
setsdim(1)=2 'base 2
setsdim(2)=1 'base 1
setsdim(3)=4 'base 4
setsdim(4)=21 'base 21

sets(4,100)

'introduction of sets

in the beginning

Elements(N) will look like
Elements:{1,1,1,1}

witch means

str=sets(1,E(1))+sets(2,E(2))+sets(3,E(3))+sets(4,E(4))
'str=sets(1, 1) +sets(2, 1) +sets(3, 1) +sets(4, 1)

if we add 1 to Elements this will look like

Elements:{1,1,1,2}

add1
...

Elements:{1,1,1,21} 'because the four digit of this is in the base 21

add 1
Elements:{1,1,2,1}
...


and so on

My project was to generate an cartezian product for an undefined nr of sets each with undefined nr of elements

sorry for my english
i hope this help u
if u want a full sample tell me and i will post u my sample

 
I think that I understand most of it, shaddow.
Do you think that you could send me some source code, just so that I know I'm implementing this the right way?

my email address is
lmendoza@b2b4business.com

thanks
leo
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top