Auxilliary Tool:
A data structure that represents an image in an efficient memory layout, and manipulates that image in ways useful for efficient feature processing.
More...
#include <ImagePatch2.h>
Public Member Functions | |
| ImagePatch2 () | |
| Constructor. | |
| ~ImagePatch2 () | |
| Destructor. | |
| ImagePatch2 (const ImagePatch2 ©) | |
| Copy Constructor. | |
| ImagePatch2 & | operator= (const ImagePatch2 &rhs) |
| Assignment operator. | |
| void | setImage (const cv::Mat &image, int setData=1, int setIntegral=1, int setSqInt=0, int setTInt=0) |
| Sets the ImagePatch to contain this image's data. | |
| void | setImage (const cv::Mat &image, cv::Rect ROI, int setData=1, int setIntegral=1, int setSqInt=0, int setTInt=0) |
| Sets the ImagePatch to contain this image's data contained in ROI. | |
| cv::Size | getImageSize () const |
| Get the size of the ImagePatch. | |
| const cv::Mat | getImageHeader () const |
| Get this image patch's data. | |
| const cv::Mat | getIntegralHeader () const |
| Get this image patch's integral data. | |
| const cv::Mat | getSqIntegralHeader () const |
| Get this image patch's sqared integral data. | |
| const cv::Mat | getTIntegralHeader () const |
| Get this image patch's tilted integral data. | |
| int | hasImageRep () const |
| Test whether this image patch has image data. | |
| int | hasIntegralRep () const |
| Test whether this image patch has integral data. | |
| int | hasSqIntegralRep () const |
| Test whether this image patch has sqare integral data. | |
| int | hasTIntegralRep () const |
| Test whether this image patch has tilted integral data. | |
| void | createRepIfNeeded (int setData=1, int setIntegral=1, int setSqInt=0, int setTInt=0) |
| If a representation has not previously been set, set it now. |
Auxilliary Tool:
A data structure that represents an image in an efficient memory layout, and manipulates that image in ways useful for efficient feature processing.
| ImagePatch2::ImagePatch2 | ( | ) |
Constructor.
Creates an empty image patch, which can be set later using setImage.
| void ImagePatch2::setImage | ( | const cv::Mat & | image, |
| int | setData = 1 , |
||
| int | setIntegral = 1 , |
||
| int | setSqInt = 0 , |
||
| int | setTInt = 0 |
||
| ) |
Sets the ImagePatch to contain this image's data.
Copies the whole image, so any cropping, converting, and resizing must be done prior to calling setImage. The image must be of type IPL_DEPTH_8U (8-bit, unsigned integer), with a single channel.
| image | The image we want to represent. |
| setData | Copy the image data. This takes some memory, and is often not needed if we are only using integral based features. However, it is necessary for visualization of ImagePatch data, and may be useful for other feature types. |
| setIntegral | Compute the integral of the ImagePatch. This is required to apply BoxFeature to the ImagePatch. |
| setSqInt | Compute the square integral of the ImagePatch. This is required to apply features that rely on variance. |
| setTInt | Compute the tilted integral of the image patch. |
| void ImagePatch2::setImage | ( | const cv::Mat & | image, |
| cv::Rect | ROI, | ||
| int | setData = 1 , |
||
| int | setIntegral = 1 , |
||
| int | setSqInt = 0 , |
||
| int | setTInt = 0 |
||
| ) |
Sets the ImagePatch to contain this image's data contained in ROI.
Any converting, and resizing must be done prior to calling setImage. The image must be of type IPL_DEPTH_8U (8-bit, unsigned integer), with a single channel.
| image | The image we want to represent. |
| ROI | The region of the image we want to represent. |
| setData | Copy the image data. This takes some memory, and is often not needed if we are only using integral based features. However, it is necessary for visualization of ImagePatch data, and may be useful for other feature types. |
| setIntegral | Compute the integral of the ImagePatch. This is required to apply BoxFeature to the ImagePatch. |


If you're looking for service which isn't listed below, please send us a message!
Methodology
{{ static.methodologies_one }}
{{ static.methodologies_two }}
Features
{% for feature in features %}
- {{ feature.feature }}
{% endfor %}
{% for service in services %}
{% if forloop.counter0|divisibleby:"2" %}
{% endif %}
{{ service.title }}
{{ service.body|safe }}
{% if forloop.counter0|divisibleby:"2" %}
{% endif %}
{% endfor %}
{% if clients %}
{% for client in clients %}
-
{% endfor %}
{% endif %}
{% endblock %}


I am a student in the School of Information at the University of Michigan. I focus on learning programming and business courses such as SI 106, SI 339, SI 364 and ACC 471.
My previous jobs include Teleoperator at Unisono. I will receive my BS from IE University. I still don't know yet what my thesis will be about... Help me jesus.


The Data Manager Tab is a searchable database of the QuantConnect Data Library. Each asset's details are accessible, including the start date, delist date, source of the data, resolutions available, and the exchange on which the asset is traded.
If you find an issue with the QuantConnect data library, you can report this through our Data page. The Data page provides a public reporting and tracking system to fix issues systematically.


Noise Reduction
Generally, the first reaction people have to automated dependency updates like Renovate is "oh great/feel the power of automation". The next reaction a few days or weeks later is often "this is getting overwhelming". Indeed, if you leave Renovate on its default settings of raising a PR every single time any dependency receives any update.. you will get a lot of PRs and related notifications. This document will give you some ideas of how to reduce the amount of "noise" in your repository and the Pros/Cons of each approach.
Of course, please keep in mind that people's definitions of "noise" may differ. For some people, it's noisy only if they get a notification or email from GitHub. For others, too many commits in their base branch may be "noise". In other words, your mileage may vary. If you have any ideas on this topic, please contact the author by starting a new discussion on the Renovate repository.
Package Grouping
To reduce noise, you can reduce the number of updates in total, and a good way to do that is via intelligent grouping of related packages.
As an example, our default ":app"
and ":library"
presets include the rule "group:monorepos"
, which means that "sibling" packages from known monorepos will always be grouped into the same branch/PR by renovate.
For example, all @angular/*
packages that are updated at the same time will be raised in a "Renovate angular monorepo packages" PR.
And every package in the React monorepo will be grouped together in a React monorepo PR too.
You may wish to take this further, for example you might want to group together all packages related to eslint
, even if they come from separate repositories/authors.
In that case you might create a config like this:
"packageRules": [
{
"matchPackagePatterns": [ "eslint" ],
"groupName": "eslint"
}
]
By setting matchPackagePatterns
to "eslint", it means that any package with ESLint anywhere in its name will be grouped into a renovate/eslint
branch and related PR.
Caution: Any time you group dependencies together, you naturally increase the chance that the branch will have an error ("break" your build). When you have more than one package upgrade in a PR, it's going to take you longer to work out which one broke than if they were all in separate PRs. Also, you will be held up upgrading all those dependencies until they all pass. If you weren't grouping, then you could keep upgrading all dependencies except the one that fails, instead of being held up. You will also have less flexibility about what to do when one or more in the group have a major upgrade and may break the others.
Scheduling Renovate
On its own, the Renovate CLI tool runs once and then exits.
Hence, it only runs as often as its administrator sets it to (e.g. via cron
).
For the Renovate app on GitHub, it currently runs continuously using a job queue that gets refreshed hourly, or when you make relevant commits to your repository.
Therefore, you can expect to get PRs at any time of the day, e.g. soon after versions are published to npm.
Receiving PRs at any hour can increase the feeling of being "overwhelmed" by updates and possibly interrupt your flow during working hours, so many Renovate users also consider reducing Renovate's schedule to be outside their normal working hours, for example weeknights and weekends.
This is achievable by configuring schedule
in your Renovate config and optionally timezone
(Renovate's default time zone is UTC, so you may find it easier to write schedules if you override timezone
to your local one).
Another example of adjusting schedules to fit with your workflow might be if your company performs releases every Monday. In that case, you might schedule Renovate to run every Tuesday after midnight to pick up new dependency updates that you can test over the following week before the next release.
Caution: You need to make sure you leave yourself and Renovate enough time in a week to actually get all your updating and merging done. There are multiple reasons why Renovate may need to "recreate" PRs after you merge another:
- Conflict with
package.json
(sometimes) - Conflict with lock files (often)
- If you have configured Renovate or GitHub that PRs must always be kept up-to-date with the base branch
Any of the above reasons can lead to a Renovate branch being considered "stale" and then Renovate needs to rebase it off the base branch before you can test and merge again, and Renovate won't do this until it's back in schedule.
Selective scheduling
Don't think that you need to apply blanket rules to scheduling.
Remember that Renovate's configuration is highly flexible so you can configure automerge
anywhere from globally (entire repo) right down to a package/upgrade type level.
You could even configure a nonsensical rule like: "patch updates of jquery
are for Mondays only".
Remember our example of grouping all eslint
packages?
If you think about it, updates to eslint
rules don't exactly need to be applied in real time!
You don't want to get too far behind, so how about we update eslint
packages only once a month?
"packageRules": [
{
"matchPackagePatterns": [ "eslint" ],
"groupName": "eslint",
"schedule": ["on the first day of the month"]
}
]
Or perhaps at least weekly:
"packageRules": [
{
"matchPackagePatterns": [ "eslint" ],
"groupName": "eslint",
"schedule": ["before 2am on monday"]
}
]
If you're wondering what is supported and not, under the hood, the schedule is parsed using @breejs/later using the later.parse.text(scheduleString)
API.
Read the parser documentation at breejs.github.io/later/parsers.html#text.
Renovate does not support scheduled minutes or "at an exact time" granularity.
Automerging
Automerging is a Renovate feature that can save you a lot of time/noise directly, while also benefiting grouping and scheduling. In short: it means that Renovate can merge PRs or even branches itself if they pass your tests.
We recommend that you enable automerge for any type of dependency update where you would just click Merge anyway. We all know that there are some types of updates that we (nearly) always verify manually before merging, and plenty of others that we don't bother looking at unless tests fail. Every time you click Merge on a Renovate PR without manually testing it, you should consider if you can enable automerge and save yourself the time in future.
Automerge works particularly well for devDependencies
and for production dependencies
that have great test coverage.
For example, if you have jest
or mocha
as a dependency, and it has an upgrade with passing tests: automerge them!
If you have a linter like eslint
or tslint
and its update passes: automerge them!
If you have an API with 100% test coverage and express
is updated: automerge it!
Branch automerging
Those of you familiar with GitHub might note that even if you automerge PRs, you are still going to get notifications (noise) anyway - one when the PR is created and another when it is merged.
For this reason we recommend you consider setting automergeType=branch
which will mean:
- Renovate first creates a branch and no PR
- If tests pass, Renovate pushes a commit directly to the base branch without PR
- If tests fail, Renovate raises a PR for you to review
The result is that passing updates are essentially "silent" - the only sign of them are the commits to your base branch.
Automerging and scheduling
Automerging is particularly beneficial if you have configured a schedule, because Renovate on its own may be able to automerge the majority of your updates.
And this is especially so if your repository needs rebasing, e.g. because you use lock files. e.g. let's say you have dependencies abc
and xyz
with upgrades, and you use a yarn.lock
file.
- At the start of the schedule,
Renovate
will create branches forabc
andxyz
upgrades, includingyarn.lock
updates - After
abc
passes tests,Renovate
will automerge it to your base branch - The
xyz
branch probably now hasyarn.lock
conflicts - Renovate will immediately check all other branches and rebase them
- The change to
xyz
branch will trigger another round of CI tests - After the updated
xyz
branch passes, Renovate will automerge it too
This is a lot better than you waking up to two PRs and then having to deal with conflicts yourself after you merge the first one.
Remember our running eslint
example?
Let's automerge it if all the linting updates pass:
"packageRules": [
{
"matchPackagePatterns": [ "eslint" ],
"groupName": "eslint",
"schedule": ["before 2am on monday"],
"automerge": true,
"automergeType": "branch"
}
]
Have you come up with a rule that you think others would benefit from?
How about a PR back to renovate-config with the above rule named ":automergeEslintWeekly"
?
Lock file considerations
Using lock files greatly increases the chance that merging one PR will result in a second PR becoming conflicted with the base branch. The table below highlights different noise reduction strategies and their effect on pull request and potential lock file conflicts:
| Action | Effect on pull requests | Chance of lock file conflicts |
|---|---|---|
| Group dependencies together | Decreases separate PRs | Decreases |
| Automerge dependencies | Decreases concurrent PRs | Decreases |
| Decrease scheduled time for Renovate | Increases concurrent PRs | Increases |
The Future of Noise Reduction
First of all, if you ever have any ideas about how to make Renovate less noisy, please raise or comment on issues in the main repository. Our philosophy is:
- Nearly everyone should use Renovate-like dependency update automation
- Over time, you should "see" Renovate less and less
One of our hopes with preset configs is that a set of "sensible" configs can be maintained by the community that combine grouping, scheduling and automerging to reduce the amount of noise in repositories with little downside or increased risk. Such lists could be maintained and used somewhat like Adblock lists - kept up to date by maintainers but for the majority of users they are simply trusted/automatic/invisible.


London
London is the capital city of England. It is the most populous city in the United Kingdom, with a metropolitan area of over 13 million inhabitants.
Hello world! This is my HTML5 sandbox.
The <!DOCTYPE html> tag is used to declare HTML 5 document
| Version | Year |
|---|---|
| HTML | 1991 |
| HTML 2.0 | 1995 |
| HTML 3.2 | 1997 |
| HTML 4.01 | 1999 |
| XHTML | 2000 |
| HTML 5 | 2014 |
Paragraph text
Pre
Code text
Headings are important because search engines use them to scan the content of your web page.
Image shrunk by setting width and height attributes
My colour style has been set to dodger blue. Go Dodgers!
Setting individual styles: <tagname style="property:value;">
<body style="background-color:lavenderblush">
Color set to coral
font-family wingdings
font-size set to 150%
text-align is right
Bold
Italic
Text is subscript and superscript
quoted text:
I have a dream...
Blockquote sample
For 50 years, WWF has been protecting the future of nature. The world's leading conservation organization, WWF works in 100 countries and is supported by 1.2 million members in the United States and close to 5 million globally.
Address sample
John Smith.The WHO was founded in 1948.
cite sample War and Peaceby John Smith
bi directional override: bdo This text will be written from right to left
A bunch of text
A bunch of text
A bunch of text
A bunch of text
A bunch of text
Setting image width and height with style is better because it prevents a style sheet from overridding the height and width attributes in the tag
The image will float to the right of the text.
HTML 5: The 'picture' tag is a way of serving different images to different devices
set list-style-type to disc
set list-style-type to square
set the list-style-type to none
Changed to ordered list
Changed list-style-type: decimal-leading-zero
Changed type to A
Changed type to a
Changed type to a
Changed to 'dl' description list
London is the capital city of "England". It is the most populous city in the United Kingdom, with a metropolitan area of over 13 million inhabitants.
London is the capital of England.
Paris is the capital of France.
Tokyo is the capital of Japan.
In this example, CSS styles all elements with the class name "city".
Try it Yourself »Scale-able text uses "vw", view width, not pixels: px
x = 5;
y = 6;
z = x + y;
// Put code inside pre because the code tag does not preserve whitespace and line-breaks
x = 5;
y = 6;
z = x + y;
Save the document by pressing Ctrl + S
If you input wrong value, the program will return Error! samp is used for sample output
Einstein wrote: E = mc2.Hello World with spaces!
My currency is £
I will display € with entity
I will display € with decimal
I will display € with hex
A ∉ {B, C, D}
Lonely ♥
If you click the "Submit" button, the form-data will be sent to a page called "/action_page.php".
Form target=_blank for new page and method=POST to submit lots of data more securely
Used fieldset to group data together and legend to give the fieldset a title
Drop down list
sie=4 and allow 'multiple'
textarea is an editor
HTML 5 datalist example
input type="tel"
First name:One form, submitting to two difference PHP scripts using 'formaction' attribute on the 'input' tag
One form, submitting two difference encoding types using 'formenctype' attribute on the 'input' tag
Quantity (between 1 and 5):Using regex to validate input with the 'pattern' attribute
'placeholder' attribute, suggests what to type
'reqiired' attribute, suggests what to type
'step' attribute set to 3, number picker goes up in increments of 3
Removed in HTML 5 elements
HTML 5 lets you create your own tags, using in the CSS
London is the capital city of England. It is the most populous city in the United Kingdom, with a metropolitan area of over 13 million inhabitants.
Paris is the capital and most populous city of France.
Tokyo is the capital of Japan, the center of the Greater Tokyo Area, and the most populous metropolitan area in the world.
New HTML 5 contextual tags
The World Wide Fund for Nature (WWF) is....
WWF's mission is to stop the degradation of our planet's natural environment, and build a future in which humans live in harmony with nature.
WWF's mission:
WWF's mission is to stop the degradation of our planet's natural environment, and build a future in which humans live in harmony with nature.
My family and I visited The Epcot center this summer.
this the mark tagImage to use:
Canvas to fill:
Video example:
Canvas (the code draws the current frame of the video every 20 millisecond):
Note: The canvas tag is not supported in Internet Explorer 8 and earlier versions.
Map sample: Won't work without Google API key
Click the button to get your coordinates.
Open map
Click the button to see the counter increase.
Close the browser tab (or window), and try again, and the counter is reset.
Note: Internet Explorer 9 and earlier versions do not support Web Workers.
Count numbers:


Before Change
}
address_id = atable.insert(**record)
record["id"] = address_id
if callable(address_onaccept):
aform = Storage(vars = record)
address_onaccept(aform)
// Add Contacts
ctable = s3db.pr_contact
// Currently no need to onaccept as none defined
record = {"pe_id": pe_id,
"contact_method": "SMS",
After Change
email = custom["email2"],
password = custom["password2"],
)
try:
user_id = db.auth_user.insert(**user2)
except:
import sys
error = sys.exc_info()[1]
current.log.error = "Unable to add 2nd Leader to database: %s" % error
else:
user2.id = user_id
// Approve User (Creates Person & Email)
auth.s3_approve_user(user2)
pe_id = auth.s3_user_pe_id(user_id)
// Add Address
record = {"addr_street": custom["addr_street2"],
"addr_postcode": custom["addr_postcode2"],
}
location_id = gtable.insert(**record)
record["id"] = location_id
if callable(location_onaccept):
gform = Storage(vars = record)
location_onaccept(gform)
record = {"pe_id": pe_id,
"location_id": location_id,
"realm_entity": realm_entity,
}
address_id = atable.insert(**record)
record["id"] = address_id
if callable(address_onaccept):
aform = Storage(vars = record)
address_onaccept(aform)
// Add Contacts
ctable = s3db.pr_contact
// Currently no need to onaccept as none defined
record = {"pe_id": pe_id,
"contact_method": "SMS",
"value": custom["mobile2"],
"realm_entity": realm_entity,
}
ctable.insert(**record)
home_phone = custom["home2"]
if home_phone:
record = {"pe_id": pe_id,
"contact_method": "HOME_PHONE",
"value": home_phone,
"realm_entity": realm_entity,
}
ctable.insert(**record)
// Add Leader to Group
person = db(ptable.pe_id == pe_id).select(ptable.id,
limitby = (0, 1),
).first()
record = {"group_id": group_id,
"person_id": person.id,
"group_head": True,
}
membership_id = mtable.insert(**record)
record["id"] = membership_id
if callable(membership_onaccept):
mform = Storage(vars = record)
membership_onaccept(mform)
// Assign correct Role
auth.add_membership(user_id = user_id,
role = "Volunteer Group Leader",
entity = realm_entity,
)
// Create Group Skills
ctable = s3db.pr_group_competency
for skill_id in custom["skill_id"]:
record = {"group_id": group_id,
"skill_id": skill_id,


--- title: JavaScript Distributed Computing layout: post tags: [javascript] uuid: e859a5e0-5ce4-3eca-d8eb-9379578c00b0 ---
I'm not the first to come across this idea: the browser could be used as part of a distributed computing system. A web server hands out JavaScript and the browser runs the script and reports the results back to the server. The browser is a portable, widely available platform so just about anyone can easily contribute, possibly without even knowing.
Browsers aren't really expecting this sort of thing. They will
complain if a script is running for too long. If you tell Firefox to
continue running the script anyway, it will lock up until the script
is done (or when it complains again). This can be worked around by writing a simple
scheduler with setTimeout()
.
This could also potentially be used as an alternative to advertising. Instead of selling advertising space, a website operator could sell visitor's CPU time by including a little snippet of code. This may be more successful, because most visitors would be unaware of it, making it less intrusive. It will be less likely to be blocked. Of course, there ethical issues about this. In fact, there is already a company doing this with secret Java applets.
There are two serious constraints on using JavaScript in a browser as a distributed computing platform:
Low bandwidth. There isn't a lot of opportunity to transfer data between the server and the node, and nodes can't talk to each other. The data needed by a node must be small. The results data must also be small.
Short computational units. The JavaScript in the browser has no way to store its running state between browser sessions, so it must rely on the server for this. This means that the units of work must be able to be completed within a short period of time. A few minutes at the most on a normal computer.
A lot of problems won't fit inside these limitations. One that I thought might was a Mersenne prime search. A Mersenne prime is a prime of the form,
2n - 1
So even though the largest known Mersenne prime has nearly 13 million
digits (about 5 MB just to store the entire number), it can be
described by it's exponent, 43,112,609
, which is small
enough to fit in a 4-byte integer. The result of a calculation, a
probabilistic primality test, is a "yes" or "no". One bit. It fits the
first constraint very well.
However, the smallest amount of work a node can do is an entire primality test. If we break it down any further, the prime will have been expanded and we will not fit the first constraint. There will be too much data. To see how possible it might be, I implemented it, which you can try out here,
/download/mersenne/ (sloppy code warning!)
I modified an
existing JavaScript bigint library which allowed me to get it up
running quickly. After you receive the page, your browser will run the
Miller-Rabin primality test on 2^9941 - 1
. You can
edit the source HTML to try a different exponent. Running it on
several of my computers on different browsers it took anywhere from an
hour to 8 hours. And that's only with an exponent of
9941
. It's an unsuitable problem.
It would be neat to see a browser computing grid in action, but I can't think of a problem to solve with it.


[Erowid Warning: Our understanding of the literature is that there is no such thing as safe use of volatile solvents, aerosols and other street inhalants : their psychoactive effects are inseparable from nerve and organ damage. We have chosen to include these reports to help document the real world use of inhalants, but their inclusion is not intended to imply that they are anything but dangerous.]
Last year me and my roommate in college decided to go pick up a couple cans of Duster for a fun night. We went crazy with it that night. We each took about 1/2-3/4 of a can within a period of about 5 hours. It was a very amusing night to say the least. We watched some Comedy Central Presents and laughed our asses off. Later on we played some Mario Kart 64. This was sort of difficult. I lost a lot of time due to trying to huff while in the middle of a race. It was a blast.
I did get officially freaked out though. My roommate took 3 full, deep breaths and started laughing hysterically. A few seconds later he started drooling all over himself. I told him he was drooling everywhere, but he didn't seem to hear me. Luckily, that ended in just a few minutes.
I, personally, enjoy Duster, though not as much as Whippets (Nitrous Oxide).
Pros:
Wah-Wahs - slightly more intense 'audio hallucinatios' than with whippets
Visuals - visuals more intense than with whippets. (Rainbow Road was INTENSE!)
Inexpensive - $3 for a whole night of fun.
Cons:
Nausea - I felt very crappy after 3/4 of a bottle, but I expected that.
Wah-wahs - even hours after taking it, I still had the Wah-Wahs..
Sleep - This kept me from getting to sleep, it reminded me of trying to sleep on Ritalin.
Experience Reports are the writings and opinions of the individual authors who submit them.
Some of the activities described are dangerous and/or illegal and none are recommended by Erowid.


--- title: calcFourier sidebar: function_reference_sidebar permalink: SO3FunComposition.calcFourier.html folder: function_reference toc: false ---
compute Fourier coefficients of an ODF
| odf | SO3Fun |
| L | order up to which Fourier coefficients are calculated |
| f_hat | vector of Fourier coefficients order as [fh000 fh1-1-1 ... fh111 fh2-2-2 fh222 ...] |
| l2 | normalization - logical |
SO3Fun.plotSpektra SO3Fun.Fourier wignerD FourierODF SO3Fun.textureindex SO3Fun.entropy SO3Fun.eval


/api/posts Get all posts stored on DB
/api/r/<community>/<post_id> Get a post stored on DB, if it exists. (Example: /r/uady_community/post:968658748)
/create_new_post Actually, it's a built-in service that sends you a form to create a new post
/remove_vote/<post_id> Add a vote to a Post
/add_vote/<post_id> Remove a vote or Decrease the vote count of a Post
/delete_post/<post_id> Deletes the desired post


Article
What is Hagura?
Hagura is a Kannada word for light-weight. The theme is very light and has very little CSS. The theme has very legible font style and distraction free layout.
Now, a little more about Kannada. Kannada is probably the only language where spoken and written forms of a word are same.
English and German: Most of the time in these languages we don’t read the word as a combination of letters probably because they use Latin script. In fact, what we speak is the phonetic transcription of the words. examples: take two similar English words “put (/pʊt/)” and “cut (/kʌt/)” the ‘u’ in “put” is spoken with ‘ʊ’ sound but in “cut” it is having ‘ʌ’ sound. Similarly the German ‘G’ in “Tag” is pronounced like English ‘K’ but the same German ‘G’ in “Gut” is pronounced like English ‘G’ itself.
So it’s plain that in European languages (at least in English and German and probably in French, Italian and Spanish also) the written and spoken forms of words are quite different. Further there are more strange practices especially in English, like using silent letters(doubt), epiglottis stop for repeated letters (bottle), not pronouncing ending letters (come, going, trying) and some really strange words (programme, analogue, queue) etc.
Now the question is whether there is a language where spoken and written forms of a word are same? The answer is yes, there is a language called Kannada where a word is written and spoken in exactly same way. You can just pick up the letters that you want and put them together to form a word, it may not have meaning but it will be pronounced as if you are reading the letters together. I don’t want to call it as a superiority aspect of this language and take pride in this language being my mother tongue but I would say that it is something unique of this language.
Source: prismoflife


{% extends 'your_files/restore-table-base.html' %} {% load explorer_tags %} {% block page_title %}Uploaded tables{% endblock page_title %} {% block breadcrumbs %}
{% endblock breadcrumbs %} {% block content %}Here you can see all uploaded tables and restore if necessary
{% regroup object_list by display_name as tables_list %}


TSR MHoC ISideWith
Section 4 of 8
Constitutional issues to me are:
Most Important
Very Important
Moderately Important
Less Important
Not Important


Don't forget the main aim is to win
A player rolls the dice
If the player gets "1" then their turn is over and they score 0.
If the player does not get "1" then the die amount is added to their turn score and they can roll again or hold.
When the player holds, their turn amount is added to their total score.
Repeat until one player has 100 points ore more.


Introduction to combinatorics in Sage#
This thematic tutorial is a translation by Hugh Thomas of the
combinatorics chapter written by Nicolas M. Thiéry in the book “Calcul
Mathématique avec Sage” [CMS2012]. It covers mainly the treatment in
Sage
of the following combinatorial problems: enumeration (how
many elements are there in a set \(S\)?), listing (generate all the
elements of \(S\), or iterate through them), and random selection
(choosing an element at random from a set \(S\) according to a given
distribution, for example the uniform distribution). These questions
arise naturally in the calculation of probabilities (what is the
probability in poker of obtaining a straight or a four-of-a-kind of
aces?), in statistical physics, and also in computer algebra (the number
of elements in a finite field), or in the analysis of
algorithms. Combinatorics covers a much wider domain (partial orders,
representation theory, …) for which we only give a few pointers
towards the possibilities offered by Sage
.
Todo
Add link to some thematic tutorial on graphs
A characteristic of computational combinatorics is the profusion of types of objects and sets that one wants to manipulate. It would be impossible to describe them all or, a fortiori, to implement them all. After some Initial examples, this chapter illustrates the underlying method: supplying the basic building blocks to describe common combinatorial sets Common enumerated sets, tools for combining them to construct new examples Constructions, and generic algorithms for solving uniformly a large class of problems Generic algorithms.
This is a domain in which Sage
has much more extensive capabilities
than most computer algebra systems, and it is rapidly expanding; at the
same time, it is still quite new, and has many unnecessary limitations
and incoherences.
Initial examples#
Poker and probability#
We begin by solving a classic problem: enumerating certain combinations of cards in the game of poker, in order to deduce their probability.
A card in a poker deck is characterized by a suit (hearts, diamonds, spades, or clubs) and a value (2, 3, …, 10, jack, queen, king, ace). The game is played with a full deck, which consists of the Cartesian product of the set of suits and the set of values:
We construct these examples in Sage
:
sage: Suits = Set(["Hearts", "Diamonds", "Spades", "Clubs"])
sage: Values = Set([2, 3, 4, 5, 6, 7, 8, 9, 10,
....: "Jack", "Queen", "King", "Ace"])
sage: Cards = cartesian_product([Values, Suits])
There are \(4\) suits and \(13\) possible values, and therefore \(4\times 13=52\) cards in the poker deck:
sage: Suits.cardinality()
4
sage: Values.cardinality()
13
sage: Cards.cardinality()
52
Draw a card at random:
sage: Cards.random_element() # random
(6, 'Clubs')
Now we can define a set of cards:
sage: Set([Cards.random_element(), Cards.random_element()]) # random
{(2, 'Hearts'), (4, 'Spades')}
This problem should eventually disappear: it is planned to change the implementation of Cartesian products so that their elements are immutable by default.
Returning to our main topic, we will be considering a simplified version of poker, in which each player directly draws five cards, which form his hand. The cards are all distinct and the order in which they are drawn is irrelevant; a hand is therefore a subset of size \(5\) of the set of cards. To draw a hand at random, we first construct the set of all possible hands, and then we ask for a randomly chosen element:
sage: Hands = Subsets(Cards, 5)
sage: Hands.random_element() # random
{(4, 'Hearts', 4), (9, 'Diamonds'), (8, 'Spades'),
(9, 'Clubs'), (7, 'Hearts')}
The total number of hands is given by the number of subsets of size \(5\) of a set of size \(52\), which is given by the binomial coefficient \(\binom{52}{5}\):
sage: binomial(52,5)
2598960
One can also ignore the method of calculation, and simply ask for the size of the set of hands:
sage: Hands.cardinality()
2598960
The strength of a poker hand depends on the particular combination of cards present. One such combination is the flush; this is a hand all of whose cards have the same suit. (In principle, straight flushes should be excluded; this will be the goal of an exercise given below.) Such a hand is therefore characterized by the choice of five values from among the thirteen possibilities, and the choice of one of four suits. We will construct the set of all flushes, so as to determine how many there are:
sage: Flushes = cartesian_product([Subsets(Values, 5), Suits])
sage: Flushes.cardinality()
5148
The probability of obtaining a flush when drawing a hand at random is therefore:
sage: Flushes.cardinality() / Hands.cardinality()
33/16660
or about two in a thousand:
sage: 1000.0 * Flushes.cardinality() / Hands.cardinality()
1.98079231692677
We will now attempt a little numerical simulation. The following function tests whether a given hand is a flush or not:
sage: def is_flush(hand):
....: return len(set(suit for (val, suit) in hand)) == 1
We now draw 10000 hands at random, and count the number of flushes obtained (this takes about 10 seconds):
sage: n = 10000
sage: nflush = 0
sage: for i in range(n): # long time
....: hand = Hands.random_element()
....: if is_flush(hand):
....: nflush += 1
sage: n, nflush # random
(10000, 18)
Enumeration of trees using generating functions#
In this section, we discuss the example of complete binary trees, and illustrate in this context many techniques of enumeration in which formal power series play a natural role. These techniques are quite general, and can be applied whenever the combinatorial objects in question admit a recursive definition (grammar) (see Species, decomposable combinatorial classes for an automated treatment). The goal is not a formal presentation of these methods; the calculations are rigorous, but most of the justifications will be skipped.

Our goal is to determine the number \(c_n\) of complete binary trees with \(n\) leaves (in this section, except when explicitly stated otherwise, “trees” always means complete binary trees). This is a typical situation in which one is not only interested in a single set, but in a family of sets, typically parameterized by \(n\in \NN\).
According to the solution of Exercise: enumeration of binary trees, the first terms are given by \(c_1,\dots,c_5=1,1,2,5,14\). The simple fact of knowing these few numbers is already very valuable. In fact, this permits research in a gold mine of information: the Online Encyclopedia of Integer Sequences, commonly called “Sloane”, the name of its principal author, which contains more than 190000 sequences of integers:
sage: oeis([1,1,2,5,14]) # optional -- internet
0: A000108: Catalan numbers: ...
1: ...
2: ...
The result suggests that the trees are counted by one of the most famous sequences, the Catalan numbers. Looking through the references supplied by the Encyclopedia, we see that this is really the case: the few numbers above form a digital fingerprint of our objects, which enable us to find, in a few seconds, a precise result from within an abundant literature.
Our next goal is to recover this result using Sage
. Let
\(C_n\) be the set of trees with \(n\) leaves, so that
\(c_n=|C_n|\); by convention, we will define
\(C_0=\emptyset\) and \(c_0=0\). The set of all trees is
then the disjoint union of the sets \(C_n\):
Having named the set \(C\) of all trees, we can translate the recursive definition of trees into a set-theoretic equation:
In words: a tree \(t\) (which is by definition in \(C\)) is either a leaf (so in \(\{\mathrm{L}\}\)) or a node to which two trees \(t_1\) and \(t_2\) have been attached, and which we can therefore identify with the pair \((t_1,t_2)\) (in the Cartesian product \(C\times C\)).
The founding idea of algebraic combinatorics, introduced by Euler in a letter to Goldbach of 1751 to treat a similar problem , is to manipulate all the numbers \(c_n\) simultaneously, by encoding them as coefficients in a formal power series, called the generating function of the \(c_n\)’s:
where \(z\) is a formal variable (which means that we do not have to worry about questions of convergence). The beauty of this idea is that set-theoretic operations \((A\uplus B\), \(A\times B)\) translate naturally into algebraic operations on the corresponding series (\(A(z)+B(z)\), \(A(z)\cdot B(z)\)), in such a way that the set-theoretic equation satisfied by \(C\) can be translated directly into an algebraic equation satisfied by \(C(z)\):
Now we can solve this equation with Sage
. In order to do so, we
introduce two variables, \(C\) and \(z\), and we define the
equation:
sage: C, z = var('C,z') # needs sage.symbolic
sage: sys = [ C == z + C*C ] # needs sage.symbolic
There are two solutions, which happen to have closed forms:
sage: sol = solve(sys, C, solution_dict=True); sol # needs sage.symbolic
[{C: -1/2*sqrt(-4*z + 1) + 1/2}, {C: 1/2*sqrt(-4*z + 1) + 1/2}]
sage: s0 = sol[0][C]; s1 = sol[1][C] # needs sage.symbolic
and whose Taylor series begin as follows:
sage: s0.series(z, 6) # needs sage.symbolic
1*z + 1*z^2 + 2*z^3 + 5*z^4 + 14*z^5 + Order(z^6)
sage: s1.series(z, 6) # needs sage.symbolic
1 + (-1)*z + (-1)*z^2 + (-2)*z^3 + (-5)*z^4 + (-14)*z^5
+ Order(z^6)
The second solution is clearly aberrant, while the first one gives the expected coefficients. Therefore, we set:
sage: C = s0 # needs sage.symbolic
We can now calculate the next terms:
sage: C.series(z, 11) # needs sage.symbolic
1*z + 1*z^2 + 2*z^3 + 5*z^4 + 14*z^5 + 42*z^6 +
132*z^7 + 429*z^8 + 1430*z^9 + 4862*z^10 + Order(z^11)
or calculate, more or less instantaneously, the 100-th coefficient:
sage: C.series(z, 101).coefficient(z,100) # needs sage.symbolic
227508830794229349661819540395688853956041682601541047340
It is unfortunate to have to recalculate everything if at some point we
wanted the 101-st coefficient. Lazy power series (see
sage.rings.lazy_series_ring
) come into their own here, in that
one can define them from a system of equations without solving it, and,
in particular, without needing a closed form for the answer. We begin by
defining the ring of lazy power series:
sage: L.<z> = LazyPowerSeriesRing(QQ)
Then we create a “free” power series, which we name, and which we then define by a recursive equation:
sage: C = L.undefined(valuation=1)
sage: C.define(z + C * C)
sage: [C.coefficient(i) for i in range(11)]
[0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
At any point, one can ask for any coefficient without having to redefine \(C\):
sage: C.coefficient(100)
227508830794229349661819540395688853956041682601541047340
sage: C.coefficient(200)
129013158064429114001222907669676675134349530552728882499810851598901419013348319045534580850847735528275750122188940
We now return to the closed form of \(C(z)\):
sage: z = var('z') # needs sage.symbolic
sage: C = s0; C # needs sage.symbolic
-1/2*sqrt(-4*z + 1) + 1/2
The \(n\)-th coefficient in the Taylor series for \(C(z)\) being given by \(\frac{1}{n!} C(z)^{(n)}(0)\), we look at the successive derivatives \(C(z)^{(n)}(z)\):
sage: derivative(C, z, 1) # needs sage.symbolic
1/sqrt(-4*z + 1)
sage: derivative(C, z, 2) # needs sage.symbolic
2/(-4*z + 1)^(3/2)
sage: derivative(C, z, 3) # needs sage.symbolic
12/(-4*z + 1)^(5/2)
This suggests the existence of a simple explicit formula, which we will now seek. The following small function returns \(d_n=n! \, c_n\):
sage: def d(n): return derivative(s0, n).subs(z=0)
Taking successive quotients:
sage: [ (d(n+1) / d(n)) for n in range(1,17) ] # needs sage.symbolic
[2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62]
we observe that \(d_n\) satisfies the recurrence relation \(d_{n+1}=(4n-2)d_n\), from which we deduce that \(c_n\) satisfies the recurrence relation \(c_{n+1}=\frac{(4n-2)}{n+1}c_n\). Simplifying, we find that \(c_n\) is the \((n-1)\)-th Catalan number:
We check this:
sage: n = var('n') # needs sage.symbolic
sage: c = 1/n*binomial(2*(n-1),n-1) # needs sage.symbolic
sage: [c.subs(n=k) for k in range(1, 11)] # needs sage.symbolic
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
sage: [catalan_number(k-1) for k in range(1, 11)]
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
We can now calculate coefficients much further; here we calculate \(c_{100000}\) which has more than \(60000\) digits:
sage: cc = c(n=100000) # needs sage.symbolic
This takes a couple of seconds:
sage: %time cc = c(100000) # not tested # needs sage.symbolic
CPU times: user 2.34 s, sys: 0.00 s, total: 2.34 s
Wall time: 2.34 s
sage: ZZ(cc).ndigits() # needs sage.symbolic
60198
The methods which we have used generalize to all recursively defined
objects: the system of set-theoretic equations can be translated into a
system of equations on the generating function, which enables the
recursive calculation of its coefficients. If the set-theoretic
equations are simple enough (for example, if they only involve Cartesian
products and disjoint unions), the equation for \(C(z)\) is
algebraic. This equation has, in general, no closed-form solution.
However, using confinement, one can deduce a linear differential
equation which \(C(z)\) satisfies. This differential equation, in
turn, can be translated into a recurrence relation of fixed length on
its coefficients \(c_n\). In this case, the series is called
D-finite. After the initial calculation of this recurrence relation,
the calculation of coefficients is very fast. All these steps are purely
algorithmic, and it is planned to port into Sage
the implementations
which exist in Maple
(the gfun
and combstruct
packages) or
MuPAD-Combinat
(the decomposableObjects
library).
For the moment, we illustrate this general procedure in the case of complete binary trees. The generating function \(C(z)\) is a solution to an algebraic equation \(P(z,C(z)) = 0\), where \(P=P(x,y)\) is a polynomial with coefficients in \(\QQ\). In the present case, \(P=y^2-y+x\). We formally differentiate this equation with respect to \(z\):
sage: # needs sage.symbolic
sage: x, y, z = var('x, y, z')
sage: P = function('P')(x, y)
sage: C = function('C')(z)
sage: equation = P(x=z, y=C) == 0
sage: diff(equation, z)
diff(C(z), z)*D[1](P)(z, C(z)) + D[0](P)(z, C(z)) == 0
or, in a more readable format,
From this we deduce:
In the case of complete binary trees, this gives:
sage: P = y^2 - y + x # needs sage.symbolic
sage: Px = diff(P, x); Py = diff(P, y) # needs sage.symbolic
sage: - Px / Py # needs sage.symbolic
-1/(2*y - 1)
Recall that \(P(z, C(z))=0\). Thus, we can calculate this fraction mod \(P\) and, in this way, express the derivative of \(C(z)\) as a polynomial in \(C(z)\) with coefficients in \(\QQ(z)\). In order to achieve this, we construct the quotient ring \(R= \QQ(x)[y]/ (P)\):
sage: Qx = QQ['x'].fraction_field()
sage: Qxy = Qx['y']
sage: R = Qxy.quo(P); R # needs sage.symbolic
Univariate Quotient Polynomial Ring in ybar
over Fraction Field of Univariate Polynomial Ring in x
over Rational Field with modulus y^2 - y + x
Note: ybar
is the name of the variable \(y\) in the quotient ring.
Todo
add link to some tutorial on quotient rings
We continue the calculation of this fraction in \(R\):
sage: fraction = - R(Px) / R(Py); fraction # needs sage.symbolic
(1/2/(x - 1/4))*ybar - 1/4/(x - 1/4)
Note
The following variant does not work yet:
sage: fraction = R( - Px / Py ); fraction # todo: not implemented
Traceback (most recent call last):
...
TypeError: denominator must be a unit
We lift the result to \(\QQ(x)[y]\) and then substitute \(z\) and \(C(z)\) to obtain an expression for \(\frac{d}{dz}C(z)\):
sage: fraction = fraction.lift(); fraction # needs sage.symbolic
(1/2/(x - 1/4))*y - 1/4/(x - 1/4)
sage: fraction(x=z, y=C) # needs sage.symbolic
2*C(z)/(4*z - 1) - 1/(4*z - 1)
or, more legibly,
In this simple case, we can directly deduce from this expression a linear differential equation with coefficients in \(\QQ[z]\):
sage: # needs sage.symbolic
sage: equadiff = diff(C,z) == fraction(x=z, y=C)
sage: equadiff
diff(C(z), z) == 2*C(z)/(4*z - 1) - 1/(4*z - 1)
sage: equadiff = equadiff.simplify_rational()
sage: equadiff = equadiff * equadiff.rhs().denominator()
sage: equadiff = equadiff - equadiff.rhs()
sage: equadiff
(4*z - 1)*diff(C(z), z) - 2*C(z) + 1 == 0
or, more legibly,
It is trivial to verify this equation on the closed form:
sage: Cf = sage.symbolic.function_factory.function('C') # needs sage.symbolic
sage: equadiff.substitute_function(Cf, s0.function(z)) # needs sage.symbolic
(4*z - 1)/sqrt(-4*z + 1) + sqrt(-4*z + 1) == 0
sage: bool(equadiff.substitute_function(Cf, s0.function(z))) # needs sage.symbolic
True
In the general case, one continues to calculate successive derivatives of \(C(z)\). These derivatives are confined in the quotient ring \(\QQ(z)[C]/(P)\) which is of finite dimension \(\deg P\) over \(\QQ(z)\). Therefore, one will eventually find a linear relation among the first \(\deg P\) derivatives of \(C(z)\). Putting it over a single denominator, we obtain a linear differential equation of degree \(\leq \deg P\) with coefficients in \(\QQ[z]\). By extracting the coefficient of \(z^n\) in the differential equation, we obtain the desired recurrence relation on the coefficients; in this case we recover the relation we had already found, based on the closed form:
After fixing the correct initial conditions, it becomes possible to calculate the coefficients of \(C(z)\) recursively:
sage: def C(n): return 1 if n <= 1 else (4*n-6)/n * C(n-1)
sage: [ C(i) for i in range(10) ]
[1, 1, 1, 2, 5, 14, 42, 132, 429, 1430]
If \(n\) is too large for the explicit calculation of \(c_n\), a sequence asymptotically equivalent to the sequence of coefficients \(c_n\) may be sought. Here again, there are generic techniques. The central tool is complex analysis, specifically, the study of the generating function around its singularities. In the present instance, the singularity is at \(z_0=1/4\) and one would obtain \(c_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}\).
Summary#
We see here a general phenomenon of computer algebra: the best data structure to describe a complicated mathematical object (a real number, a sequence, a formal power series, a function, a set) is often an equation defining the object (or a system of equations, typically with some initial conditions). Attempting to find a closed-form solution to this equation is not necessarily of interest: on the one hand, such a closed form rarely exists (e.g., the problem of solving a polynomial by radicals), and on the other hand, the equation, in itself, contains all the necessary information to calculate algorithmically the properties of the object under consideration (e.g., a numerical approximation, the initial terms or elements, an asymptotic equivalent), or to calculate with the object itself (e.g., performing arithmetic on power series). Therefore, instead of solving the equation, we look for the equation describing the object which is best suited to the problem we want to solve.
As we saw in our example, confinement (for example, in a finite dimensional vector space) is a fundamental tool for studying such equations. This notion of confinement is widely applicable in elimination techniques (linear algebra, Gröbner bases, and their algebro-differential generalizations). The same tool is central in algorithms for automatic summation and automatic verification of identities (Gosper’s algorithm, Zeilberger’s algorithm, and their generalizations; see also Exercise: alternating sign matrices).
Todo
add link to some tutorial on summation
All these techniques and their many generalizations are at the heart of
very active topics of research: automatic combinatorics and analytic
combinatorics, with major applications in the analysis of algorithms. It is
likely, and desirable, that they will be progressively implemented in
Sage
.
Common enumerated sets#
First example: the subsets of a set#
Fix a set \(E\) of size \(n\) and consider the subsets of
\(E\) of size \(k\). We know that these subsets are counted
by the binomial coefficients \(\binom n k\). We can therefore
calculate the number of subsets of size \(k=2\) of
\(E=\{1,2,3,4\}\) with the function binomial
:
sage: binomial(4, 2)
6
Alternatively, we can construct the set \(\mathcal P_2(E)\) of all the subsets of size \(2\) of \(E\), then ask its cardinality:
sage: S = Subsets([1,2,3,4], 2)
sage: S.cardinality()
6
Once S
has been constructed, we can also obtain the list of its
elements:
sage: S.list()
[{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]
or select an element at random:
sage: S.random_element() # random
{1, 4}
More precisely, the object S
models the set
\(\mathcal P_2(E)\) equipped with a fixed order (here,
lexicographic order). It is therefore possible to ask for its
\(5\)-th element, keeping in mind that, as with Python
lists, the first
element is numbered zero:
sage: S.unrank(4)
{2, 4}
As a shortcut, in this setting, one can also use the notation:
sage: S[4]
{2, 4}
but this should be used with care because some sets have a natural indexing other than by \((0, 1, \dots)\).
Conversely, one can calculate the position of an object in this order:
sage: s = S([2,4]); s
{2, 4}
sage: S.rank(s)
4
Note that S
is not the list of its elements. One can, for example,
model the set \(\mathcal P(\mathcal P(\mathcal P(E)))\) and
calculate its cardinality (\(2^{2^{2^4}}\)):
sage: E = Set([1,2,3,4])
sage: S = Subsets(Subsets(Subsets(E))); S
Subsets of Subsets of Subsets of {1, 2, 3, 4}
sage: n = S.cardinality(); n
2003529930406846464979072351560255750447825475569751419265016973...
which is roughly \(2\cdot 10^{19728}\):
sage: n.ndigits()
19729
or ask for its \(237102124\)-th element:
sage: S.unrank(237102123) # random print output
{{{2, 4}, {1, 4}, {}, {1, 3, 4}, {1, 2, 4}, {4}, {2, 3}, {1, 3}, {2}},
{{1, 3}, {2, 4}, {1, 2, 4}, {}, {3, 4}}}
It would be physically impossible to construct explicitly all the elements of \(S\), as there are many more of them than there are particles in the universe (estimated at \(10^{82}\)).
Remark: it would be natural in Python
to use len(S)
to ask for the
cardinality of S
. This is not possible because Python
requires that the
result of len
be an integer of type int
; this could cause
overflows, and would not permit the return of {Infinity} for infinite
sets:
sage: len(S)
Traceback (most recent call last):
...
OverflowError: cannot fit 'int' into an index-sized integer
Partitions of integers#
We now consider another classic problem: given a positive integer \(n\), in how many ways can it be written in the form of a sum \(n=i_1+i_2+\dots+i_\ell\), where \(i_1,\dots,i_\ell\) are positive integers? There are two cases to distinguish:
the order of the elements in the sum is not important, in which case we call \((i_1,\dots,i_\ell)\) a partition of \(n\);
the order of the elements in the sum is important, in which case we call \((i_1,\dots,i_\ell)\) a composition of \(n\).
We will begin with the partitions of \(n=5\); as before, we begin by constructing the set of these partitions:
sage: P5 = Partitions(5); P5
Partitions of the integer 5
then we ask for its cardinality:
sage: P5.cardinality()
7
We look at these \(7\) partitions; the order being irrelevant, the entries are ordered, by convention, in decreasing order.
sage: P5.list()
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1],
[1, 1, 1, 1, 1]]
The calculation of the number of partitions uses the Rademacher
formula (Wikipedia article Partition_(number_theory)), implemented in C
and highly optimized, which makes it very fast:
sage: Partitions(100000).cardinality()
27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
Partitions of integers are combinatorial objects naturally equipped with many operations. They are therefore returned as objects that are richer than simple lists:
sage: P7 = Partitions(7)
sage: p = P7.unrank(5); p
[4, 2, 1]
sage: type(p)
<class 'sage.combinat.partition.Partitions_n_with_category.element_class'>
For example, they can be represented graphically by a Ferrers diagram:
sage: print(p.ferrers_diagram())
****
**
*
We leave it to the user to explore by introspection the available operations.
Note that we can also construct a partition directly by:
sage: Partition([4,2,1])
[4, 2, 1]
or:
sage: P7([4,2,1])
[4, 2, 1]
If one wants to restrict the possible values of the parts
\(i_1,\dots,i_\ell\) of the partition as, for example, when giving
change, one can use WeightedIntegerVectors
. For example, the
following calculation:
sage: WeightedIntegerVectors(8, [2,3,5]).list()
[[0, 1, 1], [1, 2, 0], [4, 0, 0]]
shows that to make 8 dollars using 2, 3, and 5 dollar bills, one can use a 3 and a 5 dollar bill, or a 2 and two 3 dollar bills, or four 2 dollar bills.
Compositions of integers are manipulated the same way:
sage: C5 = Compositions(5); C5
Compositions of 5
sage: C5.cardinality()
16
sage: C5.list()
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 3],
[1, 2, 1, 1], [1, 2, 2], [1, 3, 1], [1, 4], [2, 1, 1, 1],
[2, 1, 2], [2, 2, 1], [2, 3], [3, 1, 1], [3, 2], [4, 1], [5]]
The number \(16\) above seems significant and suggests the existence of a formula. We look at the number of compositions of \(n\) ranging from \(0\) to \(9\):
sage: [Compositions(n).cardinality() for n in range(10)]
[1, 1, 2, 4, 8, 16, 32, 64, 128, 256]
Similarly, if we consider the number of compositions of \(5\) by length, we find a line of Pascal’s triangle:
sage: x = var('x') # needs sage.symbolic
sage: sum(x^len(c) for c in C5) # needs sage.symbolic
x^5 + 4*x^4 + 6*x^3 + 4*x^2 + x
The above example uses a functionality which we have not seen yet:
C5
being iterable, it can be used like a list in a for
loop or
a comprehension (Set comprehension and iterators).
Prove the formulas suggested by the above examples for the number of compositions of \(n\) and the number of compositions of \(n\) of length \(k\); investigate by introspection whether
Sage
uses these formulas for calculating cardinalities.
Some other finite enumerated sets#
Essentially, the principle is the same for all the finite sets with
which one wants to do combinatorics in Sage
; begin by constructing
an object which models this set, and then supply appropriate methods,
following a uniform interface [1]. We now give a few more typical
examples.
Intervals of integers:
sage: C = IntegerRange(3, 21, 2); C
{3, 5, ..., 19}
sage: C.cardinality()
9
sage: C.list()
[3, 5, 7, 9, 11, 13, 15, 17, 19]
Permutations:
sage: C = Permutations(4); C
Standard permutations of 4
sage: C.cardinality()
24
sage: C.list()
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2],
[1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3],
[2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1],
[3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1],
[3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2],
[4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
Set partitions:
sage: C = SetPartitions(["a", "b", "c"])
sage: C # random print output
Set partitions of {'a', 'c', 'b'}
sage: C.cardinality()
5
sage: C.list()
[{{'a', 'b', 'c'}},
{{'a', 'b'}, {'c'}},
{{'a', 'c'}, {'b'}},
{{'a'}, {'b', 'c'}},
{{'a'}, {'b'}, {'c'}}]
Partial orders on a set of \(8\) elements, up to isomorphism:
sage: C = Posets(8); C
Posets containing 8 elements
sage: C.cardinality()
16999
sage: C.unrank(20).plot()
Graphics object consisting of 20 graphics primitives
One can iterate through all graphs up to isomorphism. For example, there are 34 simple graphs with 5 vertices:
sage: len(list(graphs(5)))
34
Here are those with at most \(4\) edges:
sage: up_to_four_edges = list(graphs(5, lambda G: G.size() <= 4))
sage: pretty_print(*up_to_four_edges)
However, the set C
of these graphs is not yet available in
Sage
; as a result, the following commands are not yet
implemented:
sage: # not implemented
sage: C = Graphs(5)
sage: C.cardinality()
34
sage: Graphs(19).cardinality()
24637809253125004524383007491432768
sage: Graphs(19).random_element()
Graph on 19 vertices
What we have seen so far also applies, in principle, to finite algebraic structures like the dihedral groups:
sage: G = DihedralGroup(4); G
Dihedral group of order 8 as a permutation group
sage: G.cardinality()
8
sage: G.list()
[(), (1,3)(2,4), (1,4,3,2), (1,2,3,4), (2,4), (1,3), (1,4)(2,3), (1,2)(3,4)]
or the algebra of \(2\times 2\) matrices over the finite field \(\ZZ/2\ZZ\):
sage: C = MatrixSpace(GF(2), 2) # needs sage.modules sage.rings.finite_rings
sage: C.list() # needs sage.modules sage.rings.finite_rings
[
[0 0] [1 0] [0 1] [0 0] [0 0] [1 1] [1 0] [1 0] [0 1] [0 1]
[0 0], [0 0], [0 0], [1 0], [0 1], [0 0], [1 0], [0 1], [1 0], [0 1],
[0 0] [1 1] [1 1] [1 0] [0 1] [1 1]
[1 1], [1 0], [0 1], [1 1], [1 1], [1 1]
]
sage: C.cardinality() # needs sage.modules sage.rings.finite_rings
16
Set comprehension and iterators#
We will now show some of the possibilities offered by Python
for
constructing (and iterating through) sets, with a notation that is
flexible and close to usual mathematical usage, and in particular the
benefits this yields in combinatorics.
We begin by constructing the finite set \(\{i^2\ \|\ i \in \{1,3,7\}\}\):
sage: [ i^2 for i in [1, 3, 7] ]
[1, 9, 49]
and then the same set, but with \(i\) running from \(1\) to \(9\):
sage: [ i^2 for i in range(1,10) ]
[1, 4, 9, 16, 25, 36, 49, 64, 81]
A construction of this form in Python
is called set comprehension.
A clause can be added to keep only those elements with \(i\) prime:
sage: [ i^2 for i in range(1,10) if is_prime(i) ]
[4, 9, 25, 49]
Combining more than one set comprehension, it is possible to construct the set \(\{(i,j) \ | \ 1\leq j < i <5\}\):
sage: [ (i,j) for i in range(1,6) for j in range(1,i) ]
[(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3),
(5, 1), (5, 2), (5, 3), (5, 4)]
or to produce Pascal’s triangle:
sage: [[binomial(n,i) for i in range(n+1)] for n in range(10)]
[[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1],
[1, 6, 15, 20, 15, 6, 1],
[1, 7, 21, 35, 35, 21, 7, 1],
[1, 8, 28, 56, 70, 56, 28, 8, 1],
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]
The execution of a set comprehension is accomplished in two steps; first
an iterator is constructed, and then a list is filled with the
elements successively produced by the iterator. Technically, an
iterator is an object with a method next
which returns a new value
each time it is called, until it is exhausted. For example, the
following iterator it
:
sage: it = (binomial(3, i) for i in range(4))
returns successively the binomial coefficients \(\binom 3 i\) with \(i=0,1,2,3\):
sage: next(it)
1
sage: next(it)
3
sage: next(it)
3
sage: next(it)
1
When the iterator is finally exhausted, an exception is raised:
sage: next(it)
Traceback (most recent call last):
...
StopIteration
More generally, an iterable is a Python
object L
(a list,
a set, …) over whose elements it is possible to iterate. Technically,
the iterator is constructed by iter(L)
. In practice, the commands
iter
and next
are used very rarely, since for
loops and list
comprehensions provide a much pleasanter syntax:
sage: for s in Subsets(3):
....: print(s)
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
sage: [ s.cardinality() for s in Subsets(3) ]
[0, 1, 1, 1, 2, 2, 2, 3]
What is the point of an iterator? Consider the following example:
sage: sum( [ binomial(8, i) for i in range(9) ] )
256
When it is executed, a list of \(9\) elements is constructed, and
then it is passed as an argument to sum
to add them up. If, on the
other hand, the iterator is passed directly to sum
(note the absence
of square brackets):
sage: sum( binomial(8, i) for i in range(9) )
256
the function sum
receives the iterator directly, and can
short-circuit the construction of the intermediate list. If there are a
large number of elements, this avoids allocating a large quantity of
memory to fill a list which will be immediately destroyed.
Most functions that take a list of elements as input will also accept an iterator (or an iterable) instead. To begin with, one can obtain the list (or the tuple) of elements of an iterator as follows:
sage: list(binomial(8, i) for i in range(9))
[1, 8, 28, 56, 70, 56, 28, 8, 1]
sage: tuple(binomial(8, i) for i in range(9))
(1, 8, 28, 56, 70, 56, 28, 8, 1)
We now consider the functions all
and any
which denote
respectively the \(n\)-ary and and or:
sage: all([True, True, True, True])
True
sage: all([True, False, True, True])
False
sage: any([False, False, False, False])
False
sage: any([False, False, True, False])
True
The following example verifies that all primes from \(3\) to \(99\) are odd:
sage: all( is_odd(p) for p in range(3,100) if is_prime(p) )
True
A Mersenne prime is a prime of the form \(2^p -1\). We verify that, for \(p<1000\), if \(2^p-1\) is prime, then \(p\) is also prime:
sage: def mersenne(p): return 2^p -1
sage: [ is_prime(p)
....: for p in range(1000) if is_prime(mersenne(p)) ]
[True, True, True, True, True, True, True, True, True, True,
True, True, True, True]
Is the converse true?
We now try to find the smallest counter-example. In order to do this, we
use the Sage
function exists
:
sage: exists( (p for p in range(1000) if is_prime(p)),
....: lambda p: not is_prime(mersenne(p)) )
(True, 11)
Alternatively, we could construct an iterator on the counter-examples:
sage: counter_examples = (p for p in range(1000)
....: if is_prime(p) and not is_prime(mersenne(p)))
sage: next(counter_examples)
11
sage: next(counter_examples)
23
Operations on iterators#
Python
provides numerous tools for manipulating iterators; most of them
are in the itertools
library, which can be imported by:
sage: import itertools
We will demonstrate some applications, taking as a starting point the permutations of \(3\):
sage: list(Permutations(3))
[[1, 2, 3], [1, 3, 2], [2, 1, 3],
[2, 3, 1], [3, 1, 2], [3, 2, 1]]
We can list the elements of a set by numbering them:
sage: list(enumerate(Permutations(3)))
[(0, [1, 2, 3]), (1, [1, 3, 2]), (2, [2, 1, 3]),
(3, [2, 3, 1]), (4, [3, 1, 2]), (5, [3, 2, 1])]
or select only the elements in positions 2, 3, and 4 (analogue of
l[1:4]
):
sage: import itertools
sage: list(itertools.islice(Permutations(3), int(1), int(4)))
[[1, 3, 2], [2, 1, 3], [2, 3, 1]]
To apply a function to all the elements, one can do:
sage: [z.cycle_type() for z in Permutations(3)]
[[1, 1, 1], [2, 1], [2, 1], [3], [3], [2, 1]]
and similarly to select the elements satisfying a certain condition:
sage: [z for z in Permutations(3) if z.has_pattern([1,2])]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]
Implementation of new iterators#
It is easy to construct new iterators, using the keyword yield
instead of return
in a function:
sage: def f(n):
....: for i in range(n):
....: yield i
After the yield
, execution is not halted, but only suspended, ready
to be continued from the same point. The result of the function is
therefore an iterator over the successive values returned by yield
:
sage: g = f(4)
sage: next(g)
0
sage: next(g)
1
sage: next(g)
2
sage: next(g)
3
sage: next(g)
Traceback (most recent call last):
...
StopIteration
The function could be used as follows:
sage: [ x for x in f(5) ]
[0, 1, 2, 3, 4]
This model of computation, called continuation, is very useful in combinatorics, especially when combined with recursion. Here is how to generate all words of a given length on a given alphabet:
sage: def words(alphabet,l):
....: if l == 0:
....: yield []
....: else:
....: for word in words(alphabet, l-1):
....: for l in alphabet:
....: yield word + [l]
sage: [ w for w in words(['a','b'], 3) ]
[['a', 'a', 'a'], ['a', 'a', 'b'], ['a', 'b', 'a'],
['a', 'b', 'b'], ['b', 'a', 'a'], ['b', 'a', 'b'],
['b', 'b', 'a'], ['b', 'b', 'b']]
These words can then be counted by:
sage: sum(1 for w in words(['a','b','c','d'], 10))
1048576
Counting the words one by one is clearly not an efficient method in this case, since the formula \(n^\ell\) is also available; note, though, that this is not the stupidest possible approach - it does, at least, avoid constructing the entire list in memory.
We now consider Dyck words, which are well-parenthesized words in the letters “\((\)” and “\()\)”. The function below generates all the Dyck words of a given length (where the length is the number of pairs of parentheses), using the recursive definition which says that a Dyck word is either empty or of the form \((w_1)w_2\) where \(w_1\) and \(w_2\) are Dyck words:
sage: def dyck_words(l):
....: if l==0:
....: yield ''
....: else:
....: for k in range(l):
....: for w1 in dyck_words(k):
....: for w2 in dyck_words(l-k-1):
....: yield '('+w1+')'+w2
Here are all the Dyck words of length \(4\):
sage: list(dyck_words(4))
['()()()()', '()()(())', '()(())()', '()(()())', '()((()))',
'(())()()', '(())(())', '(()())()', '((()))()', '(()()())',
'(()(()))', '((())())', '((()()))', '(((())))']
Counting them, we recover a well-known sequence:
sage: [ sum(1 for w in dyck_words(l)) for l in range(10) ]
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
Constructions#
We will now see how to construct new sets starting from these building blocks. In fact, we have already begun to do this with the construction of \(\mathcal P(\mathcal P(\mathcal P(\{1,2,3,4\})))\) in the previous section, and to construct the example of sets of cards in Initial examples.
Consider a large Cartesian product:
sage: C = cartesian_product([Compositions(8), Permutations(20)]); C
The Cartesian product of (Compositions of 8, Standard permutations of 20)
sage: C.cardinality()
311411457046609920000
Clearly, it is impractical to construct the list of all the elements of this Cartesian product! And, in the following example, \(H\) is equipped with the usual combinatorial operations and also its structure as a product group:
sage: G = DihedralGroup(4)
sage: H = cartesian_product([G,G])
sage: H in Groups()
True
sage: H.an_element()
((1,3), (1,3))
sage: t = H([G.gen(0), G.gen(0)])
sage: t
((1,2,3,4), (1,2,3,4))
sage: t*t
((1,3)(2,4), (1,3)(2,4))
We now construct the union of two existing disjoint sets:
sage: C = DisjointUnionEnumeratedSets(
....: [ Compositions(4), Permutations(3)] )
sage: C
Disjoint union of Family (Compositions of 4,
Standard permutations of 3)
sage: C.cardinality()
14
sage: C.list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2],
[3, 1], [4], [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],
[3, 1, 2], [3, 2, 1]]
It is also possible to take the union of more than two disjoint sets, or even an infinite number of them. We will now construct the set of all permutations, viewed as the union of the sets \(P_n\) of permutations of size \(n\). We begin by constructing the infinite family \(F=(P_n)_{n\in N}\):
sage: F = Family(NonNegativeIntegers(), Permutations); F
Lazy family (<class 'sage.combinat.permutation.Permutations'>(i))_{i in Non negative integers}
sage: F.keys()
Non negative integers
sage: F[1000]
Standard permutations of 1000
Now we can construct the disjoint union \(\bigcup_{n\in \NN}P_n\):
sage: U = DisjointUnionEnumeratedSets(F); U
Disjoint union of
Lazy family (<class 'sage.combinat.permutation.Permutations'>(i))_{i in Non negative integers}
It is an infinite set:
sage: U.cardinality()
+Infinity
which doesn’t prohibit iteration through its elements, though it will be necessary to interrupt it at some point:
sage: for p in U: # not tested
....: print(p)
[]
[1]
[1, 2]
[2, 1]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
...
Note: the above set could also have been constructed directly with:
sage: U = Permutations(); U
Standard permutations
Summary#
Sage
provides a library of common enumerated sets, which can be
combined by standard constructions, giving a toolbox that is flexible
(but which could still be expanded). It is also possible to add new
building blocks to Sage
with a few lines (see the code in
FiniteEnumeratedSets().example()
). This is made possible by the
uniformity of the interfaces and the fact that Sage
is based on an
object-oriented language. Also, very large or even infinite sets can
be manipulated thanks to lazy evaluation strategies (iterators, etc.).
There is no magic to any of this: under the hood, Sage
applies the
usual rules (for example, that the cardinality of \(E\times E\) is
\(|E|^2\)); the added value comes from the capacity to manipulate
complicated constructions. The situation is comparable to Sage
’s
implementation of differential calculus: Sage
applies the usual
rules for differentiation of functions and their compositions, where
the added value comes from the possibility of manipulating complicated
formulas. In this sense, Sage
implements a calculus of finite
enumerated sets.
Generic algorithms#
Lexicographic generation of lists of integers#
Among the classic enumerated sets, especially in algebraic combinatorics, a certain number are composed of lists of integers of fixed sum, such as partitions, compositions, or integer vectors. These examples can also have supplementary constraints added to them. Here are some examples. We start with the integer vectors with sum \(10\) and length \(3\), with parts bounded below by \(2\), \(4\) and \(2\) respectively:
sage: IntegerVectors(10, 3, min_part=2, max_part=5,
....: inner=[2, 4, 2]).list()
[[4, 4, 2], [3, 5, 2], [3, 4, 3], [2, 5, 3], [2, 4, 4]]
The compositions of \(5\) with each part at most \(3\), and with length \(2\) or \(3\):
sage: Compositions(5, max_part=3,
....: min_length=2, max_length=3).list()
[[3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2], [1, 3, 1],
[1, 2, 2], [1, 1, 3]]
The strictly decreasing partitions of \(5\):
sage: Partitions(5, max_slope=-1).list()
[[5], [4, 1], [3, 2]]
These sets share the same underlying algorithmic structure, implemented
in the more general (and slightly more cumbersome) class
IntegerListsLex
. This class models sets of vectors
\((\ell_0,\dots,\ell_k)\) of non-negative integers, with
constraints on the sum and the length, and bounds on the parts and on
the consecutive differences between the parts. Here are some more
examples:
sage: IntegerListsLex(10, length=3,
....: min_part=2, max_part=5,
....: floor=[2, 4, 2]).list()
[[4, 4, 2], [3, 5, 2], [3, 4, 3], [2, 5, 3], [2, 4, 4]]
sage: IntegerListsLex(5, min_part=1, max_part=3,
....: min_length=2, max_length=3).list()
[[3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2],
[1, 3, 1], [1, 2, 2], [1, 1, 3]]
sage: IntegerListsLex(5, min_part=1, max_slope=-1).list()
[[5], [4, 1], [3, 2]]
sage: list(Compositions(5, max_length=2))
[[5], [4, 1], [3, 2], [2, 3], [1, 4]]
sage: list(IntegerListsLex(5, max_length=2, min_part=1))
[[5], [4, 1], [3, 2], [2, 3], [1, 4]]
The point of the model of IntegerListsLex
is in the compromise
between generality and efficiency. The main algorithm permits
iteration through the elements of such a set \(S\) in reverse
lexicographic order with a good complexity in most practical use
cases. Roughly speaking, the time needed to iterate through all the
elements of \(S\) is proportional to the number of elements, where the
proportion factor is controlled by the length \(l\) of the longest
element of \(S\). In addition, the memory usage is also controlled by
\(l\), which is to say negligible in practice.
This algorithm is based on a very general principle for traversing a decision tree, called branch and bound: at the top level, we run through all the possible choices for \(\ell_0\); for each of these choices, we run through all the possible choices for \(\ell_1\), and so on. Mathematically speaking, we have put the structure of a prefix tree on the elements of \(S\): a node of the tree at depth \(k\) corresponds to a prefix \(\ell_0,\dots,\ell_k\) of one (or more) elements of \(S\) (see Figure: The prefix tree of the partitions of 5.).
The usual problem with this type of approach is to avoid bad decisions which lead to leaving the prefix tree and exploring dead branches; this is particularly problematic because the growth of the number of elements is usually exponential in the depth. It turns out that the constraints listed above are simple enough to be able to reasonably predict when a sequence \(\ell_0,\dots,\ell_k\) is a prefix of some element \(S\). Hence, most dead branches can be pruned.
Integer points in polytopes#
Although the algorithm for iteration in IntegerListsLex
is
efficient, its counting algorithm is naive: it just iterates over all
the elements.
There is an alternative approach to treating this problem: modelling the
desired lists of integers as the set of integer points of a polytope,
that is to say, the set of solutions with integer coordinates of a
system of linear inequalities. This is a very general context in which
there exist advanced counting algorithms (e.g. Barvinok), which are
implemented in libraries like LattE
. Iteration does not pose a hard problem
in principle. However, there are two limitations that justify the
existence of IntegerListsLex
. The first is theoretical: lattice
points in a polytope only allow modelling of problems of a fixed
dimension (length). The second is practical: at the moment only the
library PALP
has a Sage
interface, and though it offers multiple
capabilities for the study of polytopes, in the present application it
only produces a list of lattice points, without providing either an
iterator or non-naive counting:
sage: A = random_matrix(ZZ, 6, 3, x=7)
sage: L = LatticePolytope(A.rows())
sage: L.points() # random
M(4, 1, 0),
M(0, 3, 5),
M(2, 2, 3),
M(6, 1, 3),
M(1, 3, 6),
M(6, 2, 3),
M(3, 2, 4),
M(3, 2, 3),
M(4, 2, 4),
M(4, 2, 3),
M(5, 2, 3)
in 3-d lattice M
sage: L.npoints() # random
11
This polytope can be visualized in 3D with L.plot3d()
(see
Figure: The polytope L and its integer points, in cross-eyed stereographic perspective.).
Species, decomposable combinatorial classes#
In Enumeration of trees using generating functions, we showed how to use the recursive definition of binary trees to count them efficiently using generating functions. The techniques we used there are very general, and apply whenever the sets involved can be defined recursively (depending on who you ask, such a set is called a decomposable combinatorial class or, roughly speaking, a combinatorial species). This includes all the types of trees, but also permutations, compositions, functional graphs, etc.
Here, we illustrate just a few examples using the Sage
library on
combinatorial species:
sage: from sage.combinat.species.library import *
sage: o = var('o') # needs sage.symbolic
We begin by redefining the complete binary trees; to do so, we stipulate the recurrence relation directly on the sets:
sage: BT = CombinatorialSpecies(min=1)
sage: Leaf = SingletonSpecies()
sage: BT.define( Leaf + (BT*BT) )
Now we can construct the set of trees with five nodes, list them, count them…:
sage: BT5 = BT.isotypes([o]*5) # needs sage.symbolic
sage: BT5.cardinality() # needs sage.symbolic
14
sage: BT5.list() # needs sage.symbolic
[o*(o*(o*(o*o))), o*(o*((o*o)*o)), o*((o*o)*(o*o)),
o*((o*(o*o))*o), o*(((o*o)*o)*o), (o*o)*(o*(o*o)),
(o*o)*((o*o)*o), (o*(o*o))*(o*o), ((o*o)*o)*(o*o),
(o*(o*(o*o)))*o, (o*((o*o)*o))*o, ((o*o)*(o*o))*o,
((o*(o*o))*o)*o, (((o*o)*o)*o)*o]
The trees are constructed using a generic recursive structure; the
display is therefore not wonderful. To do better, it would be necessary
to provide Sage
with a more specialized data structure with the
desired display capabilities.
We recover the generating function for the Catalan numbers:
sage: g = BT.isotype_generating_series(); g
z + z^2 + 2*z^3 + 5*z^4 + 14*z^5 + 42*z^6 + 132*z^7 + O(z^8)
which is returned in the form of a lazy power series:
sage: g[100]
227508830794229349661819540395688853956041682601541047340
We finish with the Fibonacci words, which are binary words without two consecutive “\(1\)”s. They admit a natural recursive definition:
sage: Eps = EmptySetSpecies()
sage: Z0 = SingletonSpecies()
sage: Z1 = Eps*SingletonSpecies()
sage: FW = CombinatorialSpecies()
sage: FW.define(Eps + Z0*FW + Z1*Eps + Z1*Z0*FW)
The Fibonacci sequence is easily recognized here, hence the name:
sage: L = FW.isotype_generating_series()[:15]; L
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
sage: oeis(L) # optional -- internet
0: A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
1: ...
2: ...
This is an immediate consequence of the recurrence relation. One can also generate immediately all the Fibonacci words of a given length, with the same limitations resulting from the generic display.
sage: FW3 = FW.isotypes([o]*3) # needs sage.symbolic
sage: FW3.list() # needs sage.symbolic
[o*(o*(o*{})), o*(o*(({}*o)*{})), o*((({}*o)*o)*{}),
(({}*o)*o)*(o*{}), (({}*o)*o)*(({}*o)*{})]
Graphs up to isomorphism#
We saw in Some other finite enumerated sets that Sage
could generate
graphs and partial orders up to isomorphism. We will now describe the
underlying algorithm, which is the same in both cases, and covers a
substantially wider class of problems.
We begin by recalling some notions. A graph \(G=(V,E)\) is a set \(V\) of vertices and a set \(E\) of edges connecting these vertices; an edge is described by a pair \(\{u,v\}\) of distinct vertices of \(V\). Such a graph is called labelled; its vertices are typically numbered by considering \(V=\{1,2,3,4,5\}\).
In many problems, the labels on the vertices play no role. Typically a chemist wants to study all the possible molecules with a given composition, for example the alkanes with \(n=8\) atoms of carbon and \(2n+2=18\) atoms of hydrogen. He therefore wants to find all the graphs consisting of \(8\) vertices with \(4\) neighbours, and \(18\) vertices with a single neighbour. The different carbon atoms, however, are all considered to be identical, and the same for the hydrogen atoms. The problem of our chemist is not imaginary; this type of application is actually at the origin of an important part of the research in graph theory on isomorphism problems.
Working by hand on a small graph it is possible, as in the example of Some other finite enumerated sets, to make a drawing, erase the labels, and “forget” the geometrical information about the location of the vertices in the plane. However, to represent a graph in a computer program, it is necessary to introduce labels on the vertices so as to be able to describe how the edges connect them together. To compensate for the extra information which we have introduced, we then say that two labelled graphs \(g_1\) and \(g_2\) are isomorphic if there is a bijection from the vertices of \(g_1\) to those of \(g_2\), which maps bijectively the edges of \(g_1\) to those of \(g_2\); an unlabelled graph is then an equivalence class of labelled graphs.
In general, testing if two labelled graphs are isomorphic is expensive.
However, the number of graphs, even unlabelled, grows very
rapidly. Nonetheless, it is possible to list unlabelled graphs very efficiently
considering their number. For example, the program Nauty
can list the
\(12005168\) simple graphs with \(10\) vertices in
\(20\) seconds.
As in Lexicographic generation of lists of integers, the general principle of the algorithm is to organize the objects to be enumerated into a tree that one traverses.
For this, in each equivalence class of labelled graphs (that is to say, for each unlabelled graph) one fixes a convenient canonical representative. The following are the fundamental operations:
Testing whether a labelled graph is canonical
Calculating the canonical representative of a labelled graph
These unavoidable operations remain expensive; one therefore tries to minimize the number of calls to them.
The canonical representatives are chosen in such a way that, for each canonical labelled graph \(G\), there is a canonical choice of an edge whose removal produces a canonical graph again, which is called the father of \(G\). This property implies that it is possible to organize the set of canonical representatives as a tree: at the root, the graph with no edges; below it, its unique child, the graph with one edge; then the graphs with two edges, and so on. The set of children of a graph \(G\) can be constructed by augmentation, adding an edge in all the possible ways to \(G\), and then selecting, from among those graphs, the ones that are still canonical [2]. Recursively, one obtains all the canonical graphs.
In what sense is this algorithm generic? Consider for example planar graphs (graphs which can be drawn in the plane without edges crossing): by removing an edge from a planar graph, one obtains another planar graph; so planar graphs form a subtree of the previous tree. To generate them, exactly the same algorithm can be used, selecting only the children which are planar:
sage: [len(list(graphs(n, property=lambda G: G.is_planar())))
....: for n in range(7)]
[1, 1, 2, 4, 11, 33, 142]
In a similar fashion, one can generate any family of graphs closed under deletion of an edge, and in particular any family characterized by a forbidden subgraph. This includes for example forests (graphs without cycles), bipartite graphs (graphs without odd cycles), etc. This can be applied to generate:
partial orders, via the bijection with Hasse diagrams which are oriented graphs without cycles and without edges implied by the transitivity of the order relation;
lattices (not implemented in
Sage
), via the bijection with the meet semi-lattice obtained by deleting the maximal vertex; in this case an augmentation by vertices rather than by edges is used.
REFERENCES:
[CMS2012]Alexandre Casamayou, Nathann Cohen, Guillaume Connan, Thierry Dumont, Laurent Fousse, François Maltey, Matthias Meulien, Marc Mezzarobba, Clément Pernet, Nicolas M. Thiéry, Paul Zimmermann Calcul Mathématique avec Sage https://www.sagemath.org/sagebook/french.html


@* * Copyright 2021 HM Revenue & Customs * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. *@ @import uk.gov.hmrc.govukfrontend.views.html.layouts.govukLayout @import uk.gov.hmrc.govukfrontend.views.html.components._ @import uk.gov.hmrc.play.config.AccessibilityStatementConfig @import uk.gov.hmrc.hmrcfrontend.views.html.helpers.HmrcStandardFooter @import views.html.govuk.{scripts => scriptsTemplate} @import views.html.govuk.head @this( govukLayout: govukLayout, head: head, scripts: scriptsTemplate, govukPhaseBanner: govukPhaseBanner, siteHeader: components.siteHeader, govukTemplate: GovukTemplate, govukBackLink: GovukBackLink, govukSummaryList: GovukSummaryList, accessibilityStatementConfig: AccessibilityStatementConfig, hmrcStandardFooter: HmrcStandardFooter ) @( pageTitle: String, backLinkUrl: Option[String] = None, baCode: Option[String] = None, beforeContentBlock: Option[Html] = None, showSignOut: Boolean = true )(contentBlock: Html)( implicit request: Request[_], messages: Messages) @beforeBlock = { @govukPhaseBanner( PhaseBanner( tag = Option(Tag(Text("BETA"))), content = HtmlContent("This is a new service – your feedback will help us to improve it."), classes = "govuk-!-display-none-print" ) ) @backLinkUrl.map{ url =>


In August 2010, Dani has established the Pango Mobile parking operation in the US as a licensee in PA, MD, DC. He was responsible for the financial and operational localization and the successful implementation of the Pango SAAS (Software as Service) cloud based system for the Pango operation in the US. Raising capital from private investors, establishing the payment processing method while partnering with the second largest Bank in the US - Wells Fargo, and introducing Pango to municipalities and parking operators while structuring Pango’s strategy and CI (Corporate Identity) in the US market.
Currently, Pango is operational in several cities in the US and bidding large cities that are expected to join Pango during the next few months.
In February 2014, the licensee has been acquired by the Licensor - Pango Mobile Parking LTD
Until 2010, for 4 years, Dani was the CEO of Eldan Transportation Group, one of the leading car leasing and rental companies in Israel.
Prior to becoming the CEO of Eldan, he served as the Managing Director of the successful Hyundai cars distributorship in Israel for 4.5 years.
Before Hyundai, Dani was the Managing Director of SKF distributorship in Israel for 2 years.
At the beginning of his professional career, he worked for 8 years as a Mechanical Engineer at
Yona Uspiz Electric Motors ltd, the largest electric motors manufacturer in Israel.
Dani succeeded in leading these companies to a high level of achievement measured by financial prosperity and by guiding them to be leaders in their respective fields
The skills that brought him to this level of accomplishment cover several fields of expertise.
Dani holds an M.Sc. in Mechanical Engineering from the Technion, the Israeli Institute of Technology. He also has an "International Executive MBA" from the Kellogg-Recanati program of the Kellogg School in Evanston, Il, USA.
These degrees have contributed to his instructive and analytical managerial profile.
This enables him to conduct long term strategies meeting a company's vision and conversely he is able to delve into the details of a business or a project.
Over the course of his professional years, Dani had the opportunity to work with diversified groups of colleagues and business partners from many countries such as the US, UK, Belgium, Sweden, Germany, Holland, Japan, S. Korea, China, India, New-Zealand and Israel. With all of them, he successfully used his innate and acquired skills of presentation and negotiation.
While in the Israeli army reserves, he served as a Battalion Commander with the rank of
LTC, a position that reflected his innate ability to lead people to meet goals and effect missions.
Professionalism, excellence and customer satisfaction represent the most important core values which characterize his managerial philosophy.
Thus he is highly proficient at entrepreneurship and leading companies to achieve strategic goals.
During the last 4 years in Israel, apart from Eldan activities, Dani acted as Director of the Board in two start-up companies and in one mature company, and as Director of the Board at the Israeli Association of Car Rental and Leasing and led activities associated with the government, municipalities and multilateral activities among the association members.
Dani was raised and lived in Israel and has traveled worldwide extensively.
He is married to Hagit and they have four children.


Psalms 4:4
Stand in awe, and sin not: commune with your own heart upon your bed, and be still. Selah.


{% extends "base_generic.html" %} {% block content %}
Blog: {{ blogcomment.blog }}
Delete the comment: {{ blogcomment }}


--- layout: archive title: Zulip Chat Archive permalink: /stream/116395-maths/topic/topos.html ---
Dear all, in the growing Cambridge Lean User Group; @Bhavik Mehta , @Wojciech Nawrocki , @Thomas Read and I have started building a topos theory library which we now think might be worth mentioning.
https://github.com/b-mehta/topos
So far the highlights are: Grothendieck topologies, subobject classifiers, binary products implies finite products, cartesian closed categories and lemmas about pullbacks and the over category. Some of it might already be floating around in mathlib branches or hidden repos, so we ought to coordinate with everyone else to make sure we don't reprove the wheel. Some people who might be interested: @Scott Morrison @Reid Barton @Johan Commelin .
Oh wow, I was going to start working on a very similar list of things last week but then I got sick instead. Good timing I guess?
Should https://github.com/b-mehta/topos/blob/master/src/sieve.lean#L135 be called pullback
?
Or maybe comap
, if you want to be particularly mathlibby.
Yeah I wasn't sure what to call it.
I'm quite sure that https://github.com/b-mehta/topos/blob/master/src/to_mathlib.lean are in mathlib already
Yeah feel free to PR and fling issues at us
Ha, I'm really excited about this!
Johan Commelin said:
Should https://github.com/b-mehta/topos/blob/master/src/sieve.lean#L135 be called
pullback
?
Yeah this was my vote too!
Johan Commelin said:
I'm quite sure that https://github.com/b-mehta/topos/blob/master/src/to_mathlib.lean are in mathlib already
Ah damn, we do have some similar/duplicated work - https://github.com/leanprover-community/mathlib/blob/master/src/category_theory/limits/shapes/images.lean vs https://github.com/b-mehta/topos/blob/master/src/over.lean#L419
Let's hope that refactoring will be smooth
Yeah it doesn't seem too bad actually - it seems like my version should just form a nice instance of the new class
How many SLOC do you have already in this repo?
Please consider PRing the parts that you think have become reasonably stable.
(Assuming S means stable), my guess is that about a third to half of it right now
Johan Commelin said:
How many SLOC do you have already in this repo?
~3000 lines
SLOC = source lines of code
3000 lines * (1/3) = 1000. That's already 5 PR's that you have there.
More like 30
Oh, 1000 / 5, okay.
Renamed sieve.yank
to sieve.pullback
.
I'm sure the advice from the perfectoid crew would be: strongly consider starting to make PR's to mathlib right now. Stuff changes. As mathlib changes your code will begin to break, and then it's your problem to fix it. If it's in mathlib then it gets fixed by the person who broke it instead (and it's often much easier for them to fix it because they almost always know exactly how they broke it, and indeed they just fixed the ten other parts of mathlib which broke for the same reason).
@Bhavik Mehta, this is all great, and I would encourage lots of PRs to mathlib!
Let me know if you want to discuss coordination, or any advice on what size chunks to split things into.
I'm curious about your definition of image, however. Is this not the "regular coimage", rather than the image? (They often coincide, so this is more of a naming problem than a content problem.)
The naming scheme, at least on the wikipedia page, is that "regular image" is the dual of what you've written, i.e. the equalizer of the pair of maps from Y into the pushout of X mapping via f into two copies of Y.
There's then a theorem someone ought to prove about when image
and regular_image
coincide.
And separately a theorem about when image
and coimage
coincide.
And then further the easier formulas you can use in abelian categories, etc.
Scott Morrison said:
I'm curious about your definition of image, however. Is this not the "regular coimage", rather than the image? (They often coincide, so this is more of a naming problem than a content problem.)
The "image" as I defined it satisfies the "general definition" of image given on wikipedia - proved on lines 535 and below. My goal here was to get to the 'image' as would be useful in a topos (or in my case a locally cartesian closed category with (refl.) coequalizers), so I've used something more like the regular category definition
I wonder if we should just simplify matters; throw out mine and just use yours.
As far as I can tell they should be able to coexist - I've shown that a LCCC with coequalizers has_images
. I think the only real change that needs to be made to your code is to change the instance
on L195 to a def
I should also add to Ed's message that contributions from anyone are more than welcome!
@Bhavik Mehta, have you done anything more with your definition of image? I noticed it's disappeared from the spot in your repository it used to be, and I can't find it now.
I moved it to locally_cartesian_closed.lean
I haven't yet done much more with it
Looking back at the history, I'm not sure you actually proved everything yet that the coequalizer of pullbuck definition actually satisfies the general universal property.
Am I missing something?
I think you are - I'll find the line number
https://github.com/b-mehta/topos/blob/master/src/locally_cartesian_closed.lean#L287
Specifically I constructed the regular coimage, and proved that in a locally cartesian closed category with coequalizers it coincides with the image
mono_part_is_mono
establishes that my image is a mono_factorisation
, image_is_smallest_subobject
is the definition of is_image.lift
and smallest_subobject_factors
shows is_image.lift_fac'
Great. It would be nice to separate things out a bit, and identify explicitly at what point you're using the LCC condition.
Can you point me to where that is?
in mono_part_is_mono
In pullback_preserves_epi'
and prod_map_epi
near the end of that proof
Got it, thanks.
I should say that I wrote all this with the ultimate end-goal of getting to epi-mono factorisation in a topos, so I didn't care too much about what conditions were used where since we'd eventually have them all anyway
I think a better way of doing this would be to define a regular category and show that an LCC with refl. coeqs is regular
(and regular categories also generalise abelian categories which is I think what your end goal is?)
It may be interesting to translate some of the work on boolean valued models by @Floris van Doorn to topos theory, and perhaps generalize it to Heyting valued models.
E.g following the treatment in Maclane and Moerdijk
Yeah, I would like to get most of chapters 4-6 of MM
For those interested, we've effectively got the first milestone in this project! Pare's theorem: that a category with finite limits and power objects has finite colimits. Along the way, we've also now got the reflexive (or crude) monadicity theorem and creation of limits (it's sorry-free but still a bit messy, so it's in this branch)
PR, PR, PR, before it's too late. :-)
There's an art to keeping a bolus of development work going, making sure to balance the rates at which material enters and leaves (digested into mathlib).
{% endraw %}Last updated: Apr 24 2020 at 19:02 UTC


Cards
Cards are used to contain items or highlight a specific part of the user interface.
Some text in the card
Some text in the flat card
Cards are used to contain items or highlight a specific part of the user interface.
Some text in the card
Some text in the flat card