On 15/11/2013 23:04, Nicolas M. Thiery wrote:
On Fri, Nov 15, 2013 at 02:43:29PM -0500, Vincent Delecroix wrote:
Thanks for taking care of it. I would like cartesian products to be
smarter about iteration... especially when one of the factor is
infinite. I have a working implementation of the iterator that you can
use on the sage-combinat misc repo.
I assume this is some diagonal iterator, right? IIRC, Nicolas B. also
has some similar stuff (Nicolas?). I guess this is a good candidate to
go in EnumeratedSets.Infinite.CartesianProducts.ParentMethods.
Hello,
In fact, my use case was a little different : I wanted a smart iterator
on a SearchForest having an infinite number of roots and each node has
also an infinite number of children. This is still an enumerated set but
both deep first search and breadth first search produced dummy
iterables. So the strategy was to manipulate a growing to infinity stack
of iterables. Elements were pondered by the sum of their generation and
their position between their brotherhood. I am also afraid this code is
perhaps lost (not enougth backup with laptop change...)
For CartesianProduct build on n atoms: (A_1 x A_2 x A_3 x ... x A_n), a
way consist in setting a SearchForest with a single root: (A_1.first(),
A_2.first(), ... A_n.first()) and use a breadth first search with the
following children function :
for an element : (x_1, x_2, ... x_i, ... , x_n) wherein x_i IS THE PART
THE MOST ON THE RIGHT WHICH IS NOT THE FIRST OF ITS ATOM A_i, we set its
children to be the iterable on
[(x_1, x_2, ... A_i.next(x_i), ... , x_n),
(x_1, x_2, ... x_i, A_{i+1}.next(x_{i+1}) ... , x_n)
, ... ,
(x_1, x_2, ... x_i, ... , A_n.next(x_n))]
That will produce a kind of deglex iterator in which the degree is the
sum of the generation (= number of time you need to call next from first
before seeing it) of each part.
I don't know if there exist not something better. Perhaps not, but
defining a SearchForest just for an iterable is perhaps a little bit
loud. I don't know. My X.next() method was consisting in add +1 to an
integer but if the method X.next(a) reroll an iterable from begining,
this is probably not very efficient.... Perhaps there is no way to
genericaly do it smarter. Hope that can help...
Cheers,
Nicolas B.
P.S. : Sorry for my English. I don't love to post drafty and old stuff
but as you asked for... I just grab it from my trash... The following
code (2 or 3 years old) enumerate along the integer vectors of any
length. This is still in the old combinat queue.
(refactor_interger_vectors....-nb.patch)
1797
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1797>
+cpdef list all_children(IntegerVector_class v):
1798
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1798>
+ r"""
1799
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1799>
+ Returns all the children of an integer vector (ClonableIntArray) ``v``
1800
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1800>
+ in the tree of enumeration by lexicographic order. The children of
1801
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1801>
+ an integer vector ``v`` whose entries have for sum `n` are all integer
1802
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1802>
+ vectors of sum `n+1` which follow ``v`` in the lexicographic order.
1803
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1803>
+
1804
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1804>
+ That means this function adds `1` on the last non zero entries and the
1805
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1805>
+ following ones. For an integer vector `v` such that
1806
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1806>
+
1807
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1807>
+ .. math::
1808
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1808>
+
1809
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1809>
+ v = [ \dots, a , 0, 0 ] \text{ with } a \neq 0,
1810
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1810>
+
1811
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1811>
+ then, the list of children is
1812
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1812>
+
1813
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1813>
+ .. math::
1814
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1814>
+
1815
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1815>
+ [ [ \dots, a+1 , 0, 0 ] , [ \dots, a , 1, 0 ], [ \dots, a , 0, 1 ] ].
1816
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1816>
+
1817
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1817>
+ EXAMPLES::
1818
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1818>
+
1819
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1819>
+ sage: from sage.combinat.enumeration_mod_permgroup import all_children
1820
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1820>
+ sage: v = IntegerVector([1,2,3,4])
1821
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1821>
+ sage: all_children(v)
1822
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1822>
+ [[1, 2, 3, 5]]
1823
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1823>
+ """
1824
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1824>
+ cdef int l, j
1825
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1825>
+ cdef IntegerVector_class child
1826
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1826>
+ cdef list all_children
1827
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1827>
+ l = len(v)
1828
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1828>
+ all_children = []
1829
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1829>
+ j = l - 1
1830
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1830>
+ while j >= 1 and v[j] == 0:
1831
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1831>
+ j = j - 1
1832
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1832>
+ for i in range(j,l):
1833
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1833>
+ child = v.clone()
1834
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1834>
+ child._list[i] = v._list[i]+1
1835
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1835>
+ child.set_immutable()
1836
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1836>
+ all_children.append(child)
1837
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1837>
+ return all_children
1838
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1838>
+
1839
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1839>
+cpdef list all_children_completed(IntegerVector_class v):
1840
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1840>
+ r"""
1841
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1841>
+ This internal function allows to enumerate all integer
1842
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1842>
+ vectors. There is no real natural enumeration in a such set but it
1843
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1843>
+ is interesting to have an iterator on such set for the
1844
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1844>
+ development of other features on integer vectors.
1845
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1845>
+
1846
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1846>
+ Let us define the degree of an integer vector by the sum of two
1847
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1847>
+ characteristics : the sum of the entries of the integer vector and
1848
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1848>
+ the length of the integer vector. for example `v = \[1,0,3,5,0\]` has
1849
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1849>
+ entries that sum up to `9` and has `5` different entries, its degree
1850
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1850>
+ is thus `14`.
1851
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1851>
+
1852
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1852>
+ Using the SearchForest feature setting by breadth first search,
1853
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1853>
+ plugging this function as children function and setting the root
1854
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1854>
+ to be the empty integer vector `\[ \]`, we obtain an enumeration
1855
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1855>
+ of all integer vectors by deglex order.
1856
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1856>
+
1857
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1857>
+ For that, this function do exactly the same job as
1858
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1858>
+ :func:`all_children` but it had an extra child when the entries of
1859
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1859>
+ the integer vector sum up to `0`. This child is obtained by his
1860
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1860>
+ father by adding a last entry with the integer `0`.
1861
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1861>
+
1862
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1862>
+ EXAMPLES::
1863
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1863>
+
1864
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1864>
+
1865
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1865>
+ """
1866
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1866>
+ cdef list children
1867
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1867>
+ if list(v) == []:
1868
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1868>
+ return [IntegerVector_class(v.parent() ,[0], check=False)]
1869
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1869>
+ children = all_children(v)
1870
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1870>
+ if v.sum() == 0:
1871
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1871>
+ children.append(IntegerVector_class(v.parent() ,list(v)+[0],
check=False))
1872
<http://combinat.sagemath.org/patches/file/44cce9b172b7/refactor_integer_vectors_clonableintarray-nb.patch#l1872>
+ return children
the resulted iterator on integer vectors was [] -> [0] -> [1] -> [0,0]
-> [2] -> [1,0] -> [0,1] -> [0,0,0] -> [3] -> [2,0] -> [1,1] -> [0,2] ->
[1,0,0] -> [0,1,0] -> [0,0,1] -> [0,0,0,0] -> [4] -> ...
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel.
For more options, visit https://groups.google.com/groups/opt_out.
