PARI's commands

[science_man_88]

interCol(C) ={ IC=intersection(C[1],C[2]);for(i=1,#C,IC=intersection(IC,C[i]));IC;}

problem is intersection makes it pretty which then makes it useless here. I think I'll have to add a control to pretty it or not.

[CRGreathouse]

Originally Posted by science_man_88

I looked over the other thread and I realized it's simple:

union(A,B)=concat(A,B);vecsort(union,,8)

so simple I messed it up:

union(A,B)= U=concat(A,B);vecsort(U,,8)

Yes... though you should *only* use variables that have been declared with my() or local() -- and use my() unless you have a good reason to use local(). So

union(A,B)=my(U=concat(A,B));vecsort(U,,8)

Of course in this case you don't even need a variable at all -- can you see how to avoid it?

[CRGreathouse]

Originally Posted by science_man_88

okay I added a new thing to that and on my end it works it's and if loop checking if #a and #b are = 0 but that shouldn't make a difference in that:

aredisjoint(A=[],B=[]) ={
if(#A!=0 && #B!=0,
a=0;
for(i=1,#A,
    for(j=1,#B,
	    if(A[i]==B[j],
		   return(0),
		   a=a+1;
		   if(a==#A*#B,
		      return(1),
			 )
		)
	)
)
,return(0)
)};

Still wrong.

The check that neither are empty is not only needless but actually harmful here. Also, there's no need to count the number of times you find disjoint pairs -- if you find any identical elements they're not disjoint, otherwise they are.

[CRGreathouse]

Originally Posted by science_man_88

Just to update I've changed one thing in Cp and fixed the output for CPC.

hopefully I can program more of this it may become very useful.

When you get all of them working maybe you can post them all in one swell foop.

Originally Posted by science_man_88

interCol(C) ={ IC=intersection(C[1],C[2]);for(i=1,#C,IC=intersection(IC,C[i]));IC;}

problem is intersection makes it pretty which then makes it useless here. I think I'll have to add a control to pretty it or not.

I don't know what this is trying to do.

[science_man_88]

Originally Posted by CRGreathouse

Yes... though you should *only* use variables that have been declared with my() or local() -- and use my() unless you have a good reason to use local(). So

union(A,B)=my(U=concat(A,B));vecsort(U,,8)

Of course in this case you don't even need a variable at all -- can you see how to avoid it?

vecsort(concat(A,B),,8)

[CRGreathouse]

Yep, you win.

As for the disjoint program: If you have a working intersection program you can just use that. If the sets are disjoint, what (by definition!) will their intersection be? That makes for a very short (albeit potentially slow) disjoint function.

[science_man_88]

Originally Posted by CRGreathouse

Yep, you win.

As for the disjoint program: If you have a working intersection program you can just use that. If the sets are disjoint, what (by definition!) will their intersection be? That makes for a very short (albeit potentially slow) disjoint function.

yeah well I tried this:

(17:57)>aredisjoint(v,c)
%9 = 1
(17:57)>##
  ***   last result computed in 0 ms.
(17:57)>aredisjoint2(v,c)
%10 = 1
(17:57)>##
  ***   last result computed in 328 ms.
(17:57)>?aredisjoint2
aredisjoint2(A,B)=if(intersection(A,B)==[],return(1),return(0))

the aredisjoint is:

aredisjoint(A=[],B=[]) ={
a=0;
for(i=1,#A,
    for(j=1,#B,
	    if(A[i]==B[j],
		   return(0),
		      return(1)
			 )
		)
	)};

the reason the aredisjoint2 is slower is because my intersection script doesn't check if they have a intersection but goes through both sets creating a new vector for their intersection. my disjoint script aredisjoint only has to check the whole of both sets if no exception is found. never mind I'm an idiot.

[CRGreathouse]

Originally Posted by science_man_88

the reason the aredisjoint2 is slower is because my intersection script doesn't check if they have a intersection but goes through both sets creating a new vector for their intersection. my disjoint script aredisjoint only has to check the whole of both sets if no exception is found. never mind I'm an idiot.

Certainly you can check whether two sets are disjoint faster than you can compute their intersection in most cases. But your current code is broken and I was suggesting a way to fix it.

The whole idea of breaking programs into different functions is that you can change the internal workings of one without affecting the others. Generally I recommend making a function that gives the correct answer, even if it runs very slowly, and using that to check if your newer, fast versions are correct.

Originally Posted by science_man_88

aredisjoint(A=[],B=[]) ={
a=0;
for(i=1,#A,
    for(j=1,#B,
	    if(A[i]==B[j],
		   return(0),
		      return(1)
			 )
		)
	)};

This function is equivalent to

aredisjoint(A=[],B=[]) ={
  a=0;
  if(#A & #B, A[1] != B[1])
};

That is, the function does this:
1. It clobbers the global a variable. That is,

a=1;aredisjoint();print(a)

prints 0 instead of 1, a bad side-effect. (This is why you should always use my() or local().)
2. It checks if either vector is of length 0. If so, it does nothing -- internally it returns a value called gnil which is interpreted as 0 if needed but which is not displayed in gp.
3. Otherwise, it looks at A[1] and B[1]. If the values are the same it returns 0, otherwise it returns 1. It never looks at any other values.

[science_man_88]

Originally Posted by CRGreathouse

Certainly you can check whether two sets are disjoint faster than you can compute their intersection in most cases. But your current code is broken and I was suggesting a way to fix it.

The whole idea of breaking programs into different functions is that you can change the internal workings of one without affecting the others. Generally I recommend making a function that gives the correct answer, even if it runs very slowly, and using that to check if your newer, fast versions are correct.




This function is equivalent to

aredisjoint(A=[],B=[]) ={
  a=0;
  if(#A & #B, A[1] != B[1])
};

That is, the function does this:
1. It clobbers the global a variable. That is,

a=1;aredisjoint();print(a)

prints 0 instead of 1, a bad side-effect. (This is why you should always use my() or local().)
2. It checks if either vector is of length 0. If so, it does nothing -- internally it returns a value called gnil which is interpreted as 0 if needed but which is not displayed in gp.
3. Otherwise, it looks at A[1] and B[1]. If the values are the same it returns 0, otherwise it returns 1. It never looks at any other values.

I suck at this:

(19:37)>aredisjoint([],[])
%1 = 0
(19:38)>aredisjoint([],[1,2,3])
%2 = 0
(19:38)>aredisjoint([4,5,6],[1,2,3])
%3 = 1
(19:38)>aredisjoint([3,5,6],[1,2,3])
%4 = 0
(19:38)>

aredisjoint(A=[],B=[]) ={
if(#A!=0 && #B!=0,
for(i=1,#A,
    for(j=1,#B,
	    if(A[i]==B[j],
		   return(0)
			 )
		)
	);return(1)
	,return(0))
	}

I think this could be changed to || because [] is a subset of every other set and hence no set can be disjoint from it so if it appears even once we know it's 0.

[CRGreathouse]

You should remove that entire if() test on the size of the vectors, it doesn't need to be there.

[science_man_88]

Originally Posted by CRGreathouse

You should remove that entire if() test on the size of the vectors, it doesn't need to be there.

well it will return 1 for aredisjoint([],[]) it would also do that if only one is empty as we know the empty set is not disjoint from any set.