Opened 12 years ago
Last modified 6 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 )
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 12 years ago by
comment:2 Changed 12 years ago by
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 12 years ago by
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 12 years ago by
- 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 12 years ago by
- Description modified (diff)
- Milestone set to sage-3.0.3
comment:6 Changed 12 years ago by
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 12 years ago by
- Cc sage-combinat added
comment:8 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:9 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:10 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:11 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
How often does one want to iterate through a CartesianProduct? of infinite things? Is the speed tradeoff for implementing the general solution worth it?