Faster jump number for posets

[jm58660]

Every poset has at least one greedy linear extension with optimal number of jumps. Use this to make a faster function.

CC: @tscrim @fchapoton

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: 1306d1f

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/24631

[jm58660]

Branch: u/jmantysalo/faster_jump_number_for_posets

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

bcd3f04

Explain algoirthm.

[sagetrac-git]

Commit: bcd3f04

[jm58660]

comment:3

The speedup is enormous, try to compute the jump number of posets.BooleanLattice(4) or something similar.

[tscrim]

comment:5

Isn't this just a backtracking algorithm? I think you should put a little more into the algorithm description (essentially explaining what "greedy" means in this context).

Instead of your nonlocals, why not just return the result, which will propagate up? In a similar vein, it is usually better to manually do the backtracking rather than use recursion (faster, and in Python, no [artificial] depth limit), but that is not something I will hold this ticket up for.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

1306d1f

Explain algorithm.

[sagetrac-git]

Changed commit from bcd3f04 to 1306d1f

[jm58660]

comment:7

Replying to @tscrim:

Isn't this just a backtracking algorithm? I think you should put a little more into the algorithm description (essentially explaining what "greedy" means in this context).

Added that.

Instead of your nonlocals, why not just return the result, which will propagate up? In a similar vein, it is usually better to manually do the backtracking rather than use recursion (faster, and in Python, no [artificial] depth limit), but that is not something I will hold this ticket up for.

Recursion depth can not be a problem here; we can propably never compute jump number of 100-element posets, unless it has very small width (and if so, we should optimize by doing series-parallel decomposition). But yes, it would be faster not to use recursion.

Returning a result is not enought if we want to cut the computation based on earlier result.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:8

Okay. LGTM.

[jm58660]

comment:9

Thanks × 3.

[vbraun]

Changed branch from u/jmantysalo/faster_jump_number_for_posets to 1306d1f