Opened 11 years ago

Last modified 5 years ago

#3389 new enhancement

CartesianProduct infinite sequences

Reported by: PolyBoRi Owned by: mhansen
Priority: minor Milestone: sage-6.4
Component: combinatorics Keywords:
Cc: sage-combinat Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by mabshoff)

Hi!

The Cartesian Product iterator of infinite sequences doesn't enumerate the every element in the product.

I tried:

for t in CartesianProduct(QQ,ZZ):

....:     print t

....:     

[0, 0]

[0, 1]

[0, -1]

[0, 2]

This is equivalent to nest for loops, which won't work. You have to enumerate the set in a different way.

See http://en.wikipedia.org/wiki/Recursively_enumerable http://en.wikipedia.org/wiki/Cantor_pairing_function

Best regards, Michael

Change History (11)

comment:1 Changed 11 years ago by mhansen

How often does one want to iterate through a CartesianProduct? of infinite things? Is the speed tradeoff for implementing the general solution worth it?

comment:2 Changed 11 years ago by PolyBoRi

I would try checking via len if the sequence might be finite (of course, there are finite sequence, where len doesn't work). If you know, that the sequences are finite, you can return an naive iterator.

comment:3 Changed 11 years ago by mhansen

Sure, but I still feel a bit like I'd be writing a bunch of useless code in the end. I'd be more apt to rename CartesianProduct? to CartesianProductOfFiniteSets? or something like that.

comment:4 Changed 11 years ago by mhansen

  • Status changed from new to assigned

So... it looks like I already have some code that does something similar in http://trac.sagemath.org/sage_trac/attachment/ticket/1448/1448-2.patch . The question then becomes whether to cache the elements as you iterate over them or reiterate to them each time you need them. Also, there are many things finite things whose cartesian product I want to iterate over for which len() takes a nontrivial amount of time.

comment:5 Changed 11 years ago by mabshoff

  • Description modified (diff)
  • Milestone set to sage-3.0.3

comment:6 Changed 11 years ago by PolyBoRi

I don't think, this could give acceptable performance without caching in a similar way as in the code for the matrix spaces.

comment:7 Changed 11 years ago by nthiery

  • Cc sage-combinat added

comment:8 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:10 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.