ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 13 Feb 2021 21:40:36 +0100prove an identity for any integerhttps://ask.sagemath.org/question/55699/prove-an-identity-for-any-integer/Let $n$ be a positive integer and $m = (m_1, \ldots, m_n)$ an $n$-dimensional vector of real numbers.
Let $g$ be a real number.
I want to prove, for any $n$ and $m$, an equality of the form
$$ \sum_{i=1}^n f_i (m,g) = 0 $$
where the function $f_i$ is a rational function of $m$ and $g$.
Of course it's easy to check this by substituting finite values of $n$, but is there a way in Sage to prove it for any integer?rue82Sat, 13 Feb 2021 21:40:36 +0100https://ask.sagemath.org/question/55699/Not getting correct output while computing posets with some conditions.https://ask.sagemath.org/question/54386/not-getting-correct-output-while-computing-posets-with-some-conditions/I want to compute finite posets on 6 elements. Also, I want the following conditions on the posets: 2 covers 0, 4 covers 2, 3 covers 1, 5 covers 3. Also, 0, 1 are incomparable and 4, 5 are incomparable. For that I am giving the following commands:
A=[]
P = Posets(6)
for p in P:
if p.covers(0, 2) and p.covers(2, 4) and p.covers(1, 3) and p.covers(3, 5) and p.compare_elements(1, 0) is None and p.compare_elements(4, 5) is None:
A.append(p);
print(A)
The output I am getting is not correct. There is only one element in sage output but that is not true. Is there any issue with my code?
DharmThu, 26 Nov 2020 06:42:33 +0100https://ask.sagemath.org/question/54386/Built-in tools for fast extraction of tuples of a given grade with respect to grading on [1, 2, ..., n]https://ask.sagemath.org/question/52440/built-in-tools-for-fast-extraction-of-tuples-of-a-given-grade-with-respect-to-grading-on-1-2-n/Hi,
Note that I have just posted [the same question on Stack Overflow](https://stackoverflow.com/q/62864317/2886628).
I am in the process of coding 2 mathematical combinatorial operations that I want to iterate (as) many times (as possible), so speed is obviously crucial.
Here is an example of what I want to do as fast and efficiently as possible for any positive integer n and any grading (see example below).
**Remark:** This is a self-motivated question coming from mathematical experimentations with Sage.
Many thanks in advance for your help.
**Example:**
Let us take n = 6, and the set S = {1, 2, ..., n} = {1, 2, 3, 4, 5, 6}.
There are binomial(6, 2) = 15 couples
```
[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]
```
in increasing order that we can extract from S.
The built-in tool I was advised to use in order to obtain the above list is the following:
```
from itertools import combinations
n = 6
iterable = list(range(1, n+1))
r = 2
print(list(combinations(iterable, r)))from itertools
```
**Question 0:** Is there anything faster in Python?
Now let me choose a grading on the set S in the form of a function from S to {1, 2, 3}
grading: 1, 2, 3 --> 1 and 4, 5 --> 2 and 6 --> 3
I have decided to store this function as a dictionary as follows:
```
grading = {1: 1, 2:1, 3: 1, 4: 2, 5: 2, 6: 3}
```
With respect to this grading, we can compute the grade of elements, couples, or tuples constructed from S.
Examples:
- grade(2) = 1
- grade(5) = 2
- grade((2, 5)) = grade(2) + grade(5) = 1 + 2 = 3
- grade((2, 3, 5)) = 1 + 1 + 2 = 5
1 - First Construction:
I want all the couples with grade equal to g0 = 4.
Here is an obvious way to do it, which is built naively on the previous lines of code:
```
g0 = 4
gradedList = []
for couple in list(combinations(iterable, 2)):
grade = grading[couple[0]] + grading[couple[1]]
if grade == g0:
gradedList.append(couple)
print(gradedList)
```
This yields
```
[(1, 6), (2, 6), (3, 6), (4, 5)]
```
as desired.
**Question 1:** Is there a built-in way to obtain gradedList and/or what is the fastest way to do this with Python?
2 - Second Construction:
Now I want to extract all the increasing 3-tuples (i, j, k) with grade equal to 4, and which starts with i = 1.
In other terms, I want the following list:
```
[(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)]
```
Of course, this can be obtained as follows:
```
newIterable = list(range(2, n+1))
secondGradedList = []
for couple in list(combinations(newIterable, 2)):
grade = grading[1] + grading[couple[0]] + grading[couple[1]]
if grade == g0:
secondGradedList.append((1,) + couple)
print(secondGradedList)
```
**Question 2:** Is there a built-in way to obtain secondGradedList and/or what is the fastest way to do this with Python?
Thanks,
JulienBostonSun, 12 Jul 2020 19:37:33 +0200https://ask.sagemath.org/question/52440/Removing some element of a list according to the zero of anotherhttps://ask.sagemath.org/question/51676/removing-some-element-of-a-list-according-to-the-zero-of-another/I have the following code.
candidats = 4 # nombre de candidats
Pref = Arrangements(["a", "b", "c", "d"], candidats).list()
show(Pref)
show(LatexExpr("Nombre~de~préférences~possibles~="+latex(len(Pref))))
elec = 100
candidats = 4
nn = list([i for i in range(len(Pref))])
ZZ = IntegerRing()
PP = ([0 for i in nn])
PP[0] = ZZ.random_element(0, elec)
for k in nn:
PP[k] = ZZ.random_element(0, elec - sum(PP[j] for j in nn[:k]))
PP[len(Pref) - 1] = (PP[len(Pref) - 1] if (elec - sum(PP)) == 0
else PP[len(Pref) - 1] + (elec - sum(PP)))
import random
PP1 = random.sample(PP, len(PP))
show(sum(PP))
show(PP)
show(PP1)
show(Pref)
def rz(l1, l2):
for k in range(len(l1)):
if l1[k] == 0:
del(l2[k])
show([len(PP), len(Pref)])
show(rz(PP, Pref))
The problem here begins with `def rz...` I would like to delete the elements of the lists `Pref` and `PP` at indices where the list `PP` has zeros. But it doesn't work. I do not find my error. I was also wondering if it could be done by embedding "two list comprehensions".CyrilleMon, 01 Jun 2020 15:38:49 +0200https://ask.sagemath.org/question/51676/Attribute error: "'Graphics' object has no attribute 'get_pos'" with plotting Hasse diagram of posethttps://ask.sagemath.org/question/50995/attribute-error-graphics-object-has-no-attribute-get_pos-with-plotting-hasse-diagram-of-poset/So I am trying to obtain the position dictionary used for displaying a poset P that can be used in the plotting of the Hasse diagram of P through the hasse_diagram() function.
To clarify, if I run the following code:
P = posets.BooleanLattice(3)
P.plot()
G = P.hasse_diagram().to_undirected()
G.plot()
The locations of the vertices of G do not line up with where the corresponding elements of the poset were. I know that we can save the position dictionary for graphs, but for whatever reason, I'm struggling with obtaining the position dictionary of elements in a poset. (With the specific posets I am working with, maintaining the position when obtaining the undirected Hasse diagram is important because I need a particular planar embedding which is not being preserved if I simply use the hasse_diagram() function in its canned form).
In the finite posets SageMath documentation, the `plot()` function says that it also accepts all options of `GenericGraph.plot` which should include the `save_pos` option and `get_pos()`. However, when I run
P = posets.BooleanLattice(3)
Pplot = P.plot(save_pos=True)
G = P.hasse_diagram().to_undirected()
position = Pplot.get_pos()
G.plot(pos = position)
I get an attribute error:
Error in lines 4-4
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1234, in execute
flags=compile_flags), namespace, locals)
File "", line 1, in <module>
AttributeError: 'Graphics' object has no attribute 'get_pos'
Is there any way to extract a position dictionary of a graphics object corresponding to the Hasse diagram of a poset?DerekHFri, 24 Apr 2020 23:58:54 +0200https://ask.sagemath.org/question/50995/Major index of skew-SYThttps://ask.sagemath.org/question/45836/major-index-of-skew-syt/For a standard Young tableaux (SYT), I can compute the major index as follows:
T = Tableau([[1,2,3],[4,5]])
T.major_index()
Is there a way to compute the major index of a skew-SYT currently? Something like:
S = SkewTableaux().from_expr([[1,1],[[5],[3,4],[1,2]]])
S.major_index()
At the moment, it seems major_index() is not defined for the SkewTableau-class.
EDIT: The major index of a (skew) standard Young tableau $T$, denoted $\mathrm{maj}(T)$, is defined as follows. A descent of $T$ is an entry $i$ such that $i+1$ appears strictly below $i$ in $T$. Define $\mathrm{maj}(T)$ as the sum of all descents of $T$. For example, the major index of the skew standard Young tableau above is $2+4=6$.
FindStat has a [definition](http://www.findstat.org/StatisticsDatabase/St000330/), although they only define it for non-skew tableau. But the definition extends trivially to skew-shapes as well.joakim_uhlinTue, 19 Mar 2019 13:29:57 +0100https://ask.sagemath.org/question/45836/How did simplify_full() manipulate this expression?https://ask.sagemath.org/question/47674/how-did-simplify_full-manipulate-this-expression/ This is sort of a follow up to a previous question of mine: https://ask.sagemath.org/question/47535/checking-identity-of-two-combinatorial-expressions/
I wanted to prove a certain combinatorial equality. Now, to prove this identity in Sage, I can define the two function $\text{LHS}(n,k)$ and $\text{RHS}(n,k)$ representing the left- and righthand side and make sure that $\text{LHS}(n,k)-\text{RHS}(n,k)=0$ with the following code (actually the code provides a proof of a slightly more general identity,
which holds for other values of $n, k$ as well.):
var('n k')
def LHS(n,k):
return n/2*(
(n/2+1-k)/(n/2+1)*((n/2+1)/(k/2)*binomial(n/2-3,k-4)*2**(n/2-k+1)*1/(k/2-1)*binomial(k-4,k/2-2))+
2*(k/2+1)/(n/2+1)*((n/2+1)/(k/2+1)*binomial(n/2-3,k-2)*2**(n/2-k-1)*1/(k/2)*binomial(k-2,k/2-1)))
def RHS(n,k):
return (n/k)*(2**(n/2-k))*binomial(n/2-2,k-2)*binomial(k-2,k/2-1)
(LHS(n,k)-RHS(n,k)).simplify_full()
This outputs
0
which is what I want but I would like to prove this identity with pen-and-paper and this seems to be a bit tricky. I wonder if there is a way to see how exactly simplify_full() were able simplify the expressions?joakim_uhlinFri, 30 Aug 2019 17:48:04 +0200https://ask.sagemath.org/question/47674/Forming a polytope from only its combinatorial datahttps://ask.sagemath.org/question/34327/forming-a-polytope-from-only-its-combinatorial-data/ I would like to visualize a polytope given only its face lattice, i.e. something like
{1}, {2}, {3}, {4},
{1, 2}, {2, 3}, {3, 4}, {4, 1},
{1, 2, 3, 4}
for a square.
Is that possible in sage?renderusefullessThu, 04 Aug 2016 13:33:56 +0200https://ask.sagemath.org/question/34327/Checking identity of two combinatorial expressionshttps://ask.sagemath.org/question/47535/checking-identity-of-two-combinatorial-expressions/I have a reason to believe that a certain combinatorial identity holds for even integers $n, k$ that satisfies $2 \leq k \leq n/2$ and $n\geq 4$. To test it in Sage, I denote the expression on the right- and lefthandside as the functions RHS$(n,k)$ and LHS$(n,k)$ respectively and check if they agree for a variety of values $n$ and $k$.
def t(n,k):
sum=0
for i in range(n-2*k+1):
sum+=binomial(n-2*k,i)
return n/k*sum*binomial(n-4,2*k-4)*catalan_number(k-2)
def LHS(n,k):
return n/2*((n/2+1-k)/(n/2+1)*t(n/2+1,k/2)+2*(k/2+1)/(n/2+1)*t(n/2+1,k/2+1))
def RHS(n,k):
return (n/k)*(2**(n/2-k))*binomial(n/2-2,k-2)*binomial(k-2,k/2-1)
But when run the following code
for n in range(6,12,2):
for k in range(2,floor(n/2)+1,2):
print("n="+str(n)+", k="+str(k))
print(bool(LHS(n,k)==RHS(n,k)))
I get the output
n=6, k=2
True
n=8, k=2
True
n=8, k=4
True
n=10, k=2
True
n=10, k=4
False
which would indicate that the identity does not hold for $n=10$, $k=4$. However, when I write
print(bool(LHS(10,4)==RHS(10,4)))
I get the output TRUE (I also double checked this by hand, and both sides agree and are equal to $30$ in this case).
1. Why does the code in the double loop yield the wrong answer? EDIT: answered by rburing
2. Is there a better way to check equalities similar to this in Sage?joakim_uhlinTue, 20 Aug 2019 22:42:42 +0200https://ask.sagemath.org/question/47535/Constructing all NE-lattice paths from $(0,0)$ to $(m,n)$https://ask.sagemath.org/question/46087/constructing-all-ne-lattice-paths-from-00-to-mn/If I consider only [Dyck Paths](http://mathworld.wolfram.com/DyckPath.html), I can do write something like this:
DWS=DyckWords(3).list()
for D in DWS:
print(D.height())
to obtain the height of all Dyck paths of length $3$. However, I would like to do the same thing but using [$NE$-lattice paths](https://en.wikipedia.org/wiki/Lattice_path#North-East_lattice_paths) from $(0,0)$ to $(m,n)$. Is there an easy way to do this in Sage?joakim_uhlinThu, 11 Apr 2019 08:50:27 +0200https://ask.sagemath.org/question/46087/Setting t=0 in a non-symmetric E-Macdonald polynomialhttps://ask.sagemath.org/question/46090/setting-t0-in-a-non-symmetric-e-macdonald-polynomial/ Suppose I have a non-symmetric [E-Macdonald polynomial](https://arxiv.org/abs/math/0601693) indexed by, say, $\mu=(0,1,1)$. Then I can write
from sage.combinat.sf.ns_macdonald import E
E([0,1,1])
and I get a polynomial in three variables and with coefficients in $\mathbb{Q}(q,t)$:
((-t + 1)/(-q*t + 1))*x0*x1 + ((-t + 1)/(-q*t + 1))*x0*x2 + x1*x2
However, I am confused about how I can work with this polynomial. For my purposes, I would like to study the specialization $t=0$. It would be really neat if there were some way to get write something like
Epoly(x_0,x_1,x_2,q,t) =...
so I could easily specialize variables as I go along.
joakim_uhlinThu, 11 Apr 2019 09:56:49 +0200https://ask.sagemath.org/question/46090/Words avoiding patternshttps://ask.sagemath.org/question/43249/words-avoiding-patterns/I'm trying to write variations on the "words" generator from http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html. The code there is
def words(alphabet,l):
if l == 0:
yield []
else:
for word in words(alphabet, l-1):
for a in alphabet:
yield word + [a]
which produces words in "alphabet" of length l. (Parenthetical remark: Where I've written "for a in alphabet", the original
has "for l in alphabet", which looks confusing given that l is also the name of the input length.)
I'd like to modify this generator in various ways, for example to produce words
in which the same "letter" does not appear twice in a row. What I've tried is the following:
def non_rep_words(alphabet,l):
if l == 0:
yield []
elif l==1:
yield alphabet
else:
for word in words(alphabet, l-1):
for a in alphabet:
if word[-1] != a:
yield w+[a]
The idea is to take a word w of length l-1 and for each element a of the alphabet, test if it agrees with the end of w,
and if it doesn't, then tack it on to w.
This seems to work for l=0,1,2, but fails at l=3. Here's what my terminal looks like:
sage: list(non_rep_words(['a','b'],2))
[['a', 'b'], ['b', 'a']]
sage: list(non_rep_words(['a','b'],3))
[['a', 'a', 'b'], ['a', 'b', 'a'], ['b', 'a', 'b'], ['b', 'b', 'a']]
Clearly I am misunderstanding something basic, and I would appreciate any advice.
Eventually, I'd like to do other kinds of pattern avoidance. For example, elements of my "alphabet" might come in pairs, a yin and a yang version, and I might want to make words in which a_yin does not follow a_yang, and conversely.PoloniusSat, 04 Aug 2018 11:05:49 +0200https://ask.sagemath.org/question/43249/codomain could not be determinedhttps://ask.sagemath.org/question/42732/codomain-could-not-be-determined/ I created an InfiniteDimensionalFreeAlgebra using CombinatorialFreeModule. It looks something like this:
class InfiniteDimensionalFreeAlgebra(CombinatorialFreeModule):
r""" The algebra generated by ``a[0], a[1], a[2], ...`` over the integers. """
def __init__(self,
base_ring=IntegerRing(),
prefix='a',
index_set=NonNegativeIntegerSemiring()):
self._base_ring = base_ring
self._basis_monoid = FreeMonoid(index_set=index_set, commutative=True, prefix=prefix)
# category
category = Algebras(self._base_ring.category()).WithBasis().Commutative()
category = category.or_subcategory(category)
# init
CombinatorialFreeModule.__init__(
self,
self._base_ring,
self._basis_monoid,
category=category,
prefix='',
bracket=False)
Now I want to view it as a *ring* and take symmetric polynomials over the ring. For example, in 2 variables, the following is one such symmetric polynomial:
2a[7] * x[1] + 2a[7] * x[2] + x[1]x[2] + 5
In my code, I attempt to initialize some Schur symmetric functions over this ring with something like:
a = InfiniteDimensionalFreeAlgebra()
sym = SymmetricFunctions(a)
s = sym.s()
one = s.one()
one_poly = one.expand(2)
at which point I run into the error `codomain could not be determined` when it attempts to apply some sort of morphism to the Schur function `one`. The full stacktrace is
Traceback (most recent call last):
File "./test_all.py", line 1162, in <module>
h = double_homogeneous(1, 1)
File "/Users/Matthew/programming/sage/morse-code/k_combinat_for_sage/all.py", line 664, in double_homogeneous
one_poly = one.expand(n)
File "/Users/Matthew/programming/sage/official-git-repo/local/lib/python2.7/site-packages/sage/combinat/sf/schur.py", line 537, in expand
return self._expand(condition, n, alphabet)
File "/Users/Matthew/programming/sage/official-git-repo/local/lib/python2.7/site-packages/sage/combinat/sf/sfa.py", line 4986, in _expand
return parent._apply_module_morphism(self, f)
File "/Users/Matthew/programming/sage/official-git-repo/local/lib/python2.7/site-packages/sage/categories/modules_with_basis.py", line 1096, in _apply_module_morphism
raise ValueError('codomain could not be determined')
ValueError: codomain could not be determined
and the full code can be found at [k_combinat_for_sage](https://github.com/MareoRaft/k_combinat_for_sage/blob/master/k_combinat_for_sage/all.py).
Thank you, your help is greatly appreciated.ml9nnMon, 25 Jun 2018 21:12:25 +0200https://ask.sagemath.org/question/42732/Posets(10) freezinghttps://ask.sagemath.org/question/41912/posets10-freezing/For some reason in SageMath 8.1 the following code leads to a freeze:
p10 = Posets(10)
p10[18]
I have tried different indices, and everything works fine for i<=17, but starting from 18 I can not access to p10[i] without an immediate freeze.
The bug does not depend on system: I tried macOS and Windows 10, both lead to the same result.artem.kSun, 08 Apr 2018 20:36:48 +0200https://ask.sagemath.org/question/41912/Combinatorial Species of Phylogenetic Treeshttps://ask.sagemath.org/question/41852/combinatorial-species-of-phylogenetic-trees/I would like to study the combinatorial class ${\cal H}$ of labelled phylogenetic trees, defined as rooted trees, whose internal nodes are unlabelled
and are constrained to have outdegree $\geq 2$, while their leaves have labels attached to them.
According to Flajolet, Sedgewick:
*Analytic Combinatorics*, p. 128, this class satisfies the recursive specification
$${\cal H}={\cal Z}+\mbox{Set}_{\geq 2}({\cal H})$$
I defined their [species](https://en.wikipedia.org/wiki/Combinatorial_species) $H$ by the code
Z=species.SingletonSpecies()
E2=species.SetSpecies(min=2)
G=CombinatorialSpecies()
H=CombinatorialSpecies()
G.define(E2(Z+G))
H=Z+G
The number of labelled structures is given by the [integer sequence](http://oeis.org/A000311).
In particular I tried to calculate (for a small cardinal number)
1. a list of such structures.
2. a generating series of this structures.
3. the number of such structures.
4. isomorphism-types of such structures.
5. a generating series of the isomorphism-types of such structures.
6. a random such structure.
7. automorphism-groups of of such structures.
using the [following](http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html#section-generic-species) code:
1. H.structures([1,2,3]).list()
2. g = H.generating_series()
3. g.counts(3)
4. H.isotypes([1,2,3])
5. g=H.isotype_generating_series()
6. r=H.structures([1,2,3]).random_element()
7. r.automorphism_group()
Only 2. seems to work.
If my code ist correct, I wonder if some of these (i.e. composition species)
are not implemented and when (whether) they will be.Frank ZenterSat, 31 Mar 2018 21:49:26 +0200https://ask.sagemath.org/question/41852/combinatorial equivalence for Polyhedra / isomorphism for latticeshttps://ask.sagemath.org/question/23180/combinatorial-equivalence-for-polyhedra-isomorphism-for-lattices/Is there an easy way to check whether two polyhedra are combinatorial equivalent, i.e. have have isomorphic face lattices.
this does not work:
Poly1=Polyhedron(vertices=[[0,1],[1,0],[1,1]], base_ring=QQ)
Poly2=Polyhedron(vertices=[[2,0],[2,2],[0,2]], base_ring=QQ)
Poly1.face_lattice()==Poly2.face_lattice()
In this case this would work:
str(Poly1.faces(1))==str(Poly2.faces(1))
but what would be a good way to check this in general?
mfThu, 03 Jul 2014 10:20:12 +0200https://ask.sagemath.org/question/23180/Sage code that receives a symmetric partition as an input and returns the corresponding partition with odd parts.https://ask.sagemath.org/question/36965/sage-code-that-receives-a-symmetric-partition-as-an-input-and-returns-the-corresponding-partition-with-odd-parts/ I am a beginner in Sage . I Just got how to find number of partitions and cardinality of partitions. But this questions is being complicated to me. Please help. sudiplaudariThu, 16 Mar 2017 14:14:32 +0100https://ask.sagemath.org/question/36965/DyckWords: workaround for from_ordered_tree?https://ask.sagemath.org/question/34763/dyckwords-workaround-for-from_ordered_tree/** MuPAD-Combinat knows (according to the docs)
for Dyck words the canonical bijection from
ordered trees with n+1 nodes to Dyck words of size n such that if a tree
t has t_1,...,t_k as childs then f(t) = [1,f(t_1),0,...,1,f(t_k),0].
* fromOrderedTree
– canonical bijection from ordered trees to Dyck words
combinat::dyckWords::fromOrderedTree(ordered tree t)
Returns the Dyck word corresponding to the ordered tree t.
* toOrderedTree
– canonical bijection from Dyck words to ordered trees
combinat::dyckWords::toOrderedTree(Dyck word w)
Returns the ordered tree corresponding to the Dyck word w.
** SageMath-Combinat knows
* to_ordered_tree()
* from_ordered_tree() NotImplementedError: TODO
What a pitty! My question is: What is a quick workaround for this missing function?
EDIT:
Since it is so easy as tmontail in his answer shows then I do not
understand why it is not implemented. At least a hint in the docs
seems appropriate.Peter LuschnyWed, 07 Sep 2016 12:18:22 +0200https://ask.sagemath.org/question/34763/OrderedSetPartitions (variant)https://ask.sagemath.org/question/34001/orderedsetpartitions-variant/I would like to have the list of partitions of [1,2,...N] of finite size k
but with using the NULL set
for example, if looking for the partitions of [1,2,3,4,5] of size 3,
i would like `[ [],[],[1,2,3,4,5] ]`
and `[ [],[1,2,3],[4,5] ]` to be in this list
is it possible to do natively in Sage, or should i write a custom function ?
> OrderedSetPartitions(5,3).list()
returns
[[{1, 2, 3}, {4}, {5}],
[{1, 2, 3}, {5}, {4}],
[{1, 2, 4}, {3}, {5}],
[{1, 2, 5}, {3}, {4}],...
EDIT: here is a (non optimized at all) attempt to solve naively this problem
def OrderedSetPartitions_0(A,k):
cols={i for i in range(k)}
# returns the list of k-OrderedSetPartitions of A, allowing for the empty set
s=Subsets(cols).list()
res=[]
count=0
P=[OrderedSetPartitions(A,i) for i in range(k+1)]
for sub in s:
print("sub=")
print(sub)
tmp=[ {} for i in range(k)]
c=sub.cardinality()
for part in P[c]:
print("part=")
print(part)
for i in range(c):
tmp[sub[i]]=part[i]
print("tmp=")
print(tmp)
res=res.append([tmp])
# res=res.append([tmp]) # tried this too
print("res=")
print(res)
count=count+1
return(res)
# print(count)
A=range(3)
k=2
A
P=[OrderedSetPartitions(A,i) for i in range(k+1)]
# note that P[2].list is a list of list !
P[2].list()
> [[{0, 1}, {2}],
> [{0, 2}, {1}],
> [{1, 2}, {0}],
> [{0}, {1, 2}],
> [{1}, {0, 2}],
> [{2}, {0, 1}]]
myset=OrderedSetPartitions_0(A,k)
I get this error message, and I admit I don't get it at all, because it looks fine when coding,
but somehow res seems to be "None" instead of []
> sub=
> {}
> sub=
> {0}
> part=
> [{0, 1, 2}]
> tmp=
> [{0, 1, 2}, {}]
> res=
> None
> sub=
> {1}
> part=
> [{0, 1, 2}]
> tmp=
> [{}, {0, 1, 2}]
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> File "_sage_input_21.py", line 10, in <module>
> exec compile(u'open("___code___.py","w").write("#
> -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("bXlzZXQ9T3JkZXJlZFNldFBhcnRpdGlvbnNfMChBLGsp"),globals())+"\\n");
> execfile(os.path.abspath("___code___.py"))
> File "", line 1, in <module>
>
> File "/private/var/folders/gm/z065gk616xg6g0xgn4c7_bvc0000gn/T/tmpryfYOj/___code___.py", line 2, in <module>
> exec compile(u'myset=OrderedSetPartitions_0(A,k)
> File "", line 1, in <module>
>
> File "/private/var/folders/gm/z065gk616xg6g0xgn4c7_bvc0000gn/T/tmpSH_9LF/___code___.py", line 27, in OrderedSetPartitions_0
> res=res.append([tmp])
> AttributeError: 'NoneType' object has no attribute 'append'
The problem is about res
if i omit the line res=res.append(tmp), i will get the enumeration ok i think
EDIT:
i changed `res=res.append(tmp)` by `res.append(tmp)`
i also changed the line initializing tmp into `tmp=[ set() for i in range(k)]`
now as a result of `print(tmp)` i get the correct enumeration
[{0, 1, 2}, set([]), set([])]
[set([]), {0, 1, 2}, set([])]
[set([]), set([]), {0, 1, 2}]
[{0, 1}, {2}, set([])]
[{0, 2}, {1}, set([])]
[{1, 2}, {0}, set([])]
[{0}, {1, 2}, set([])]
[{1}, {0, 2}, set([])]
[{2}, {0, 1}, set([])]
[{0, 1}, set([]), {2}]
[{0, 2}, set([]), {1}]
[{1, 2}, set([]), {0}]
[{0}, set([]), {1, 2}]
[{1}, set([]), {0, 2}]
[{2}, set([]), {0, 1}]
[set([]), {0, 1}, {2}]
[set([]), {0, 2}, {1}]
[set([]), {1, 2}, {0}]
[set([]), {0}, {1, 2}]
[set([]), {1}, {0, 2}]
[set([]), {2}, {0, 1}]
[{0}, {1}, {2}]
[{0}, {2}, {1}]
[{1}, {0}, {2}]
[{2}, {0}, {1}]
[{1}, {2}, {0}]
[{2}, {1}, {0}]
However, for res, i get the strange result
[[{0, 1, 2}, set(), set()],
[set(), {0, 1, 2}, set()],
[set(), set(), {0, 1, 2}],
[{2}, {0, 1}, set()],
[{2}, {0, 1}, set()],
[{2}, {0, 1}, set()],
[{2}, {0, 1}, set()],
[{2}, {0, 1}, set()],
[{2}, {0, 1}, set()],
[{2}, set(), {0, 1}],
[{2}, set(), {0, 1}],
[{2}, set(), {0, 1}],
[{2}, set(), {0, 1}],
[{2}, set(), {0, 1}],
[{2}, set(), {0, 1}],
[set(), {2}, {0, 1}],
[set(), {2}, {0, 1}],
[set(), {2}, {0, 1}],
[set(), {2}, {0, 1}],
[set(), {2}, {0, 1}],
[set(), {2}, {0, 1}],
[{2}, {1}, {0}],
[{2}, {1}, {0}],
[{2}, {1}, {0}],
[{2}, {1}, {0}],
[{2}, {1}, {0}],
[{2}, {1}, {0}]]
only the first 3 lines are correct. There seems to be some side-effects. This is very enigmatic to me because between
`print(tmp)` and `res.append(tmp)` there are no instructions at all !!!!faguiSun, 03 Jul 2016 15:18:42 +0200https://ask.sagemath.org/question/34001/How to draw special trees from a list consisting of tuples with Sage?https://ask.sagemath.org/question/30673/how-to-draw-special-trees-from-a-list-consisting-of-tuples-with-sage/ I have the following problem:
Imagine, we have tuples (1,1), (1,2), ... , (1,n), (2,1), (2,2), (2,n), (3,1), ... , (k,n) in a list `L`.
To every tuple `(i,j)` I have associated a list <code>L<sub>{ij}</sub>=[...]</code>. The entries of <code>L<sub>{ij}</sub></code> are special other tuples from `L`, which we call "compatible with the tuple `(i,j)`". So, in general, all the lists <code>L<sub>{ij}</sub></code> are different from one another.
I would like the PC to draw trees in the following manner:
In the first level, there is one tuple T. This was manually chosen from the list `L`.
In the second level, there are all the tuples <code>T<sub>1</sub>, ... , T<sub>r</sub></code>, which are compatible with T. Each of them shall be connected with `T` by a single line.
In the third level, for each tuple <code>T<sub>s</sub></code> of the second line, there are drawn all the tuples that are compatible with <code>T<sub>s</sub></code> **and** at the same time already appeared one level higher (here: in level 2). Call the tuples of this level <code>T<sub>1<sub>1</sub></sub>, ... , T<sub>1<sub>m</sub></sub>, T<sub>2<sub>1</sub></sub>, ... T<sub>2<sub>p</sub></sub>, ...</code>. Each of the <code>T<sub>1<sub>1</sub></sub>, ... , T<sub>1<sub>m</sub></sub></code> shall be connected with <code>T<sub>1</sub></code> by a single line. Each of the <code>T<sub>2<sub>1</sub></sub>, ... , T<sub>2<sub>p</sub></sub></code> shall be connected with <code>T<sub>2</sub></code> by a single line, and so on.
Iterate this, until the process stops (is finished) and you have drawn a tree.
The arrows of the tree are just edges and the points are the tuples, that should be numbered by `(1,1), ... , (k,n)`. Note that not every entry of `L` has to appear in the resulting tree, since the lists <code>L<sub>{ij}</sub></code> need not be a partition of `L`.
Here is a small example:
Let L=[(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)].
Let L_{11}=[(2,2), (2,3), (2,1)].
Let L_{12}=[(1,3), (2,1)].
Let L_{13}=[(1,2)].
Let L_{21}=[(1,1), (1,2),(2,2)].
Let L_{22}=[(1,1), (2,1)].
Let L_{23}=[(1,1)].
This gives the following tree for `(1,1)`:
(1,1)
--------------|--------------
| | |
(2,1) (2,2) (2,3)
| |
| |
(2,2) (2,1)
Not only the tree, but also its "longest" branches (i.e. these, that can no more be extended by the procedure above...in the above example, these are `(1,1)-(2,1)-(2,2)` and `(1,1)-(2,2)-(2,1)` and `(1,1)-(2,3)`) should be returned (there are no repetitions allowed in the branches).
Now, my question is:
> What's the best possibility to solve problems of this kind in a fast way with Sage?
Thanks for the help!BernThu, 12 Nov 2015 17:31:27 +0100https://ask.sagemath.org/question/30673/A proper combinatorics tutorial?https://ask.sagemath.org/question/8629/a-proper-combinatorics-tutorial/I've been looking around to see if there are any good combinatorics tutorials done up as sage worksheets.
I see a couple of things, for example: [http://sagenb.org/home/pub/3115/](http://sagenb.org/home/pub/3115/) and [http://userpages.umbc.edu/~rcampbel/Computers/SAGE/combin.html](http://userpages.umbc.edu/~rcampbel/Computers/SAGE/combin.html)
But something more comprehensive would be nice. If you know of one that exists, or if you have suggestions on style, so I can start building one myself, I'd appreciate it. Is there a good one for another area of mathematics?alejandroericksonSat, 14 Jan 2012 17:10:56 +0100https://ask.sagemath.org/question/8629/Some combinatorial lists related to partitions.https://ask.sagemath.org/question/28725/some-combinatorial-lists-related-to-partitions/I want to generate the lists on the right hand side of the arrow.
P (partitions) --> D (no name?)
[1, 1, 1, 1, 1, 1, 1] --> [0, 0, 0, 0, 0, 0, 1]
[2, 2, 2, 1] --> [0, 0, 1, 1]
[2, 2, 1, 1, 1] --> [0, 1, 0, 0, 1]
[2, 1, 1, 1, 1, 1] --> [1, 0, 0, 0, 0, 1]
[3, 3, 1] --> [0, 2, 1]
[3, 2, 2] --> [1, 0, 2]
[3, 2, 1, 1] --> [1, 1, 0, 1]
[3, 1, 1, 1, 1] --> [2, 0, 0, 0, 1]
[4, 3] --> [1, 3]
[4, 2, 1] --> [2, 1, 1]
[4, 1, 1, 1] --> [3, 0, 0, 1]
[5, 2] --> [3, 2]
[5, 1, 1] --> [4, 0, 1]
[6, 1] --> [5, 1]
[7] --> [7]
Assume 1-based lists. They have the properties:
P[1] = sum(D)
sum(P) = sum(i*t for (i,t) in enumerate(D))
My questions: is there a method in Sage which returns these
lists? If not, what is the best method to generate them given
the other methods of Sage? What is the name of these lists
if they have one?Peter LuschnyThu, 30 Jul 2015 22:05:49 +0200https://ask.sagemath.org/question/28725/Seeking an efficient filter for partitions.https://ask.sagemath.org/question/27321/seeking-an-efficient-filter-for-partitions/From the docs:
sage: Partitions(4, max_part=2).list()
[[2, 2], [2, 1, 1], [1, 1, 1, 1]]
I find this parlance confusing. Obviously
the partition [1, 1, 1, 1] has no max part = 2. Be that as it may, I do want to filter those
partitions which greatest part is 2, so in the
example would return
[[2, 2], [2, 1, 1]].
What is the most efficient way to implement
P(n,k) = Partitions(n, MAX_PART=k)
where MAX_PART is defined in my sense?
Peter LuschnyMon, 13 Jul 2015 11:38:26 +0200https://ask.sagemath.org/question/27321/Error in code or need more runtime?https://ask.sagemath.org/question/25394/error-in-code-or-need-more-runtime/ Hello everyone,
I would like to compute the number of sub-multisets (of a particular cardinality) of a multiset. The "mother" multiset contains exactly 2 copies of the numbers 0 through 52 (it has cardinality 106), and I would like to compute the number of distinct sub-multisets of size 14. I am attempting to do this with Sage (of course), and the code I am trying to use is as follows:
S = range(53); S.extend(range(53))
// This makes my mother set of two copies of the numbers 0 through 52
Hands = Subsets(S, 14, submultiset=true); Hands.cardinality()
// This defines a set of the sub-multisets of size 14, and then outputs their cardinality.
When I run this (in the Sage Notebook running inside Oracle VirtualBox with 2gb of allotted RAM), it gives me a small green rectangle that changes the cursor to a 'watch' as if it's still running. It's been like this for over and hour now. Is there an error in my code or should I expect such a calculation to take a 'long' time? I'm not familiar with 'large' calculations such as this one.
Thanks in advance!mengenSun, 04 Jan 2015 19:16:02 +0100https://ask.sagemath.org/question/25394/optimizing graph coloring for small chromatic numberhttps://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/I am using Sage to compute chromatic number of some moderately large graphs G (a few thousand vertices). These graphs are relatively sparse (average degree < 15) and the chromatic number is fairly small–––the graphs I've been looking at tend to have chromatic number either 4 or 5. For my purposes, though, there is a big difference between 4 and 5.
––I've been using G.chromatic_number() as a black box, but is there some way I could just ask Sage directly if the graph is 4-colorable? (If the answer is 'no' maybe I don't care about whether the chromatic number is actually 5, 6, or larger.)
––Also, is there anything else I can do to optimize chromatic number calculations in Sage if I know a priori that the chromatic number is relatively small?
MattKahleSun, 04 Jan 2015 21:35:41 +0100https://ask.sagemath.org/question/25395/The value of binomial(-1,-1) is?https://ask.sagemath.org/question/24418/the-value-of-binomial-1-1-is/ Maple says 1, Mathematica says 1, Sage says 0 (at least in the version installed on SMC).
Peter
Peter LuschnyTue, 07 Oct 2014 15:08:30 +0200https://ask.sagemath.org/question/24418/Simple counting on restricted n-ary k-tupleshttps://ask.sagemath.org/question/11068/simple-counting-on-restricted-n-ary-k-tuples/I have some simple counting problems, for example, how many n-ary k-tuples, i.e. $(v_0,v_1,\ldots, v_k)$ with $0\le v_i < n$, are there which have $v_0=1$, and $m$ non-zero coordinates.
What sort of functionality is there is Sage or other computer algebra systems for answering such questions for general $n,k$ and $m$?alejandroericksonWed, 11 Jun 2014 07:57:19 +0200https://ask.sagemath.org/question/11068/Strings with given frequencyhttps://ask.sagemath.org/question/10989/strings-with-given-frequency/Is there a sage function that gives me all vectors/strings/lists/tuples of integers with given "absolute frequency"? i.e.
dwim([2, 1]) == ["001", "010", "100"]alsdasdakjshdTue, 04 Feb 2014 17:52:06 +0100https://ask.sagemath.org/question/10989/Find linear combinations that meet certain criteriahttps://ask.sagemath.org/question/10881/find-linear-combinations-that-meet-certain-criteria/Hey,
I am quite new to SAGE, this is my first project. I'm not even sure if it is solvable or not, but here is what I want to do:
- w_1 is the smallest multiple of 5 that is >=
(volume / 30)
- w_n = w_1 + 5*n
- w_max is the largest multiple of 5 that is <=
((volume / 24) + 30)
- were n increases until w_n == w_max
I want to find all solutions to:
- (w_1)*(r_1) + (w_2)*(r_2) + ... +
(w_n)*(r_n) == volume
Given each/any r can be any integer from 5 to 10 and that the sum of all r's is less than or equal 30. Volume is just some constant integer multiple of 5 between 5425 and 7200. Its just an initial condition I want to be able to change. Is this possible or is it too many possibilities for SAGE to handle? I have some programing experience (C and .net ) and a little math experience(Calc 1,2 and 3 as well as differential equations) but I don't know were to start really. If there is any more information I can provide that would be useful I would be very happy to do so. I don't expect someone to make it for me, but I'm not quite sure what kind of approach I should be trying use, so I don't really know what to look up. Any help or advice is welcome.
Thanks.waryhermitFri, 03 Jan 2014 12:19:54 +0100https://ask.sagemath.org/question/10881/Ascending tuples of integershttps://ask.sagemath.org/question/10822/ascending-tuples-of-integers/Hi everyone,
I'm trying to define the set of all tuples of ascending integers (any length, repetitions allowed). What is the best way to do this? Do I use Family()? I'd like to use this set enumerate the basis of a combinatorial free algebra.
Bonus question: Is it possible to add an extra label to each integer in the tuple?GonnemanWed, 11 Dec 2013 04:27:21 +0100https://ask.sagemath.org/question/10822/