www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Set operation like cartesian product

reply "Andrea Fontana" <nospam example.com> writes:
I see cartesianProduct in std.algorithm. I read:

auto N = sequence!"n"(0); // the range of natural numbers
auto N2 = cartesianProduct(N, N); // the range of all pairs of 
natural numbers

So it gives (0,0) (0,1) (1,0) ... and so on.

Is there a way to generate only tuple:

a[0] > a[1] (0,1) (0,2) ... (1,2) (1,3) .. (2,3) (2,4)

or

a[0] >= a[1] (0,0) (0,1) (0,2) ... (1,1) (1,2) (1,3) .. (2,2) 
(2,3) (2,4)

Or the only way is use filter!(...) after cartesianProduct?
Feb 28 2013
next sibling parent reply "Andrea Fontana" <nospam example.com> writes:
On Thursday, 28 February 2013 at 15:32:00 UTC, Andrea Fontana 
wrote:

 I see cartesianProduct in std.algorithm. I read:

 auto N = sequence!"n"(0); // the range of natural numbers
 auto N2 = cartesianProduct(N, N); // the range of all pairs of 
 natural numbers

 So it gives (0,0) (0,1) (1,0) ... and so on.

 Is there a way to generate only tuple:

 a[0] > a[1] (0,1) (0,2) ... (1,2) (1,3) .. (2,3) (2,4)

 or

 a[0] >= a[1] (0,0) (0,1) (0,2) ... (1,1) (1,2) (1,3) .. (2,2) 
 (2,3) (2,4)

 Or the only way is use filter!(...) after cartesianProduct?


PS: In my case I can't use filter!(...): I'm trying to compare an 
array of struct with itself to find similar ones, so I can't 
filter Tuple(struct, struct) in any way...

I have to write:

for (i; 0..arr.length) for(j; i+1..arr.length) // check arr[i] 
and arr[j] for similarities

Any ideas?
Feb 28 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrea Fontana:


 Any ideas?


I suggested pairwise():
http://d.puremagic.com/issues/show_bug.cgi?id=6788

Bye,
bearophile
Feb 28 2013
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Feb 28, 2013 at 04:31:59PM +0100, Andrea Fontana wrote:

 I see cartesianProduct in std.algorithm. I read:
 
 auto N = sequence!"n"(0); // the range of natural numbers
 auto N2 = cartesianProduct(N, N); // the range of all pairs of
 natural numbers
 
 So it gives (0,0) (0,1) (1,0) ... and so on.
 
 Is there a way to generate only tuple:
 
 a[0] > a[1] (0,1) (0,2) ... (1,2) (1,3) .. (2,3) (2,4)


[...]

auto triangularProduct(R1,R2)(R1 r1, R2 r2)
	if (isForwardRange!R1)
{
	return map!(function(a) => zip(take(a[1].save, a[0]), repeat(a[2])))(
			zip(sequence!"n"(0), repeat(r1.save), r2)
		)
		.joiner();
}

Both ranges can be infinite, only the first one needs to be a forward
range.



 a[0] >= a[1] (0,0) (0,1) (0,2) ... (1,1) (1,2) (1,3) .. (2,2) (2,3)
 (2,4)


[...]

auto triangularProduct2(R1,R2)(R1 r1, R2 r2)
	if (isForwardRange!R1)
{
	return map!(function(a) => zip(take(a[1].save, a[0]), repeat(a[2])))(
			zip(sequence!"n"(1), repeat(r1.save), r2)
		)
		.joiner();
}

As above, both ranges can be infinite, only the first one needs to be a
forward range.

Hope this helps. ;-)


T

-- 
Gone Chopin. Bach in a minuet.
Feb 28 2013
parent reply "Andrea Fontana" <nospam example.com> writes:
On Thursday, 28 February 2013 at 18:23:04 UTC, H. S. Teoh wrote:

 On Thu, Feb 28, 2013 at 04:31:59PM +0100, Andrea Fontana wrote:

 I see cartesianProduct in std.algorithm. I read:
 
 auto N = sequence!"n"(0); // the range of natural numbers
 auto N2 = cartesianProduct(N, N); // the range of all pairs of
 natural numbers
 
 So it gives (0,0) (0,1) (1,0) ... and so on.
 
 Is there a way to generate only tuple:
 
 a[0] > a[1] (0,1) (0,2) ... (1,2) (1,3) .. (2,3) (2,4)


 [...]

 auto triangularProduct(R1,R2)(R1 r1, R2 r2)
 	if (isForwardRange!R1)
 {
 	return map!(function(a) => zip(take(a[1].save, a[0]), 
 repeat(a[2])))(
 			zip(sequence!"n"(0), repeat(r1.save), r2)
 		)
 		.joiner();
 }

 Both ranges can be infinite, only the first one needs to be a 
 forward
 range.



 a[0] >= a[1] (0,0) (0,1) (0,2) ... (1,1) (1,2) (1,3) .. (2,2) 
 (2,3)
 (2,4)


 [...]

 auto triangularProduct2(R1,R2)(R1 r1, R2 r2)
 	if (isForwardRange!R1)
 {
 	return map!(function(a) => zip(take(a[1].save, a[0]), 
 repeat(a[2])))(
 			zip(sequence!"n"(1), repeat(r1.save), r2)
 		)
 		.joiner();
 }

 As above, both ranges can be infinite, only the first one needs 
 to be a
 forward range.

 Hope this helps. ;-)


 T


triangulaProduct2 for [0,1,2,3] and [0,1,2,3] doesn't give (0,0) 
(1,1) (2,2) (3,3)

:)
Feb 28 2013
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Feb 28, 2013 at 09:20:52PM +0100, Andrea Fontana wrote:

 On Thursday, 28 February 2013 at 18:23:04 UTC, H. S. Teoh wrote:


[...]

auto triangularProduct2(R1,R2)(R1 r1, R2 r2)
	if (isForwardRange!R1)
{
	return map!(function(a) => zip(take(a[1].save, a[0]),
repeat(a[2])))(
			zip(sequence!"n"(1), repeat(r1.save), r2)
		)
		.joiner();
}

As above, both ranges can be infinite, only the first one needs to
be a
forward range.

Hope this helps. ;-)


T


 
 triangulaProduct2 for [0,1,2,3] and [0,1,2,3] doesn't give (0,0)
 (1,1) (2,2) (3,3)
 
 :)


Ahhh, slight mistake there, it should be:

auto triangularProduct2(R1,R2)(R1 r1, R2 r2)
	if (isForwardRange!R1)
{
	return map!(function(a) => zip(take(a[1].save, a[0]+1), repeat(a[2])))(
			zip(sequence!"n"(1), repeat(r1.save), r2)
		)
		.joiner();
}

There, better now? ;-)

Also, if you only need products of finite ranges, it's possible to
rewrite it so that it produces items in a nicer order. The strange order
output by my examples are to cater for the infinite case.


T

-- 
Life would be easier if I had the source code. -- YHL
Feb 28 2013
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Feb 28, 2013 at 03:01:48PM -0800, H. S. Teoh wrote:

 On Thu, Feb 28, 2013 at 09:20:52PM +0100, Andrea Fontana wrote:

 On Thursday, 28 February 2013 at 18:23:04 UTC, H. S. Teoh wrote:


 [...]

auto triangularProduct2(R1,R2)(R1 r1, R2 r2)
	if (isForwardRange!R1)
{
	return map!(function(a) => zip(take(a[1].save, a[0]),
repeat(a[2])))(
			zip(sequence!"n"(1), repeat(r1.save), r2)
		)
		.joiner();
}

As above, both ranges can be infinite, only the first one needs to
be a
forward range.

Hope this helps. ;-)


T


 
 triangulaProduct2 for [0,1,2,3] and [0,1,2,3] doesn't give (0,0)
 (1,1) (2,2) (3,3)
 
 :)


 
 Ahhh, slight mistake there, it should be:
 
 auto triangularProduct2(R1,R2)(R1 r1, R2 r2)
 	if (isForwardRange!R1)
 {
 	return map!(function(a) => zip(take(a[1].save, a[0]+1), repeat(a[2])))(
 			zip(sequence!"n"(1), repeat(r1.save), r2)


[...]

Argh. Another mistake. The above line should read:

 			zip(sequence!"n"(0), repeat(r1.save), r2)

:-/


T

-- 
Once bitten, twice cry...
Feb 28 2013