Questions tagged [enumeration]
This tag covers algorithms that enumerate some set, whether finite or infinite. Do not use it for questions about computability classes, such as recursively enumerable (RE) sets; use tags [computability] and [semi-decidability] for these.
178 questions
4
votes
1
answer
100
views
How to find all maximal rectangles contained in a rectilinear shape on a discrete grid
I would like to find all the maximal rectangles contained in a rectilinear shape on a discrete grid. That is, every rectangle such that, if it were to grow by one cell in any direction, it would no ...
- 41
0
votes
0
answers
32
views
A simple machine that enumerates strings
I can get ChatGPT to write a Python program that does various enumerations for me, but I'm trying to understand this from an abstract, theoretical viewpoint.
The first thing that occurs to me in ...
- 182
0
votes
0
answers
40
views
Properties of the sequence and its generators listing Gödel numbers of programs with a particular syntactic property
Given a Gödel numbering of programs in a Turing complete language, consider a sequence of the Gödel numbers of programs that have a particular syntactic property (or more generally, non-(non-trivial ...
- 213
0
votes
1
answer
103
views
What are typical real-world applications of enumeration or random order enumeration algorithms?
I'm currently studying enumeration algorithms and random order enumeration algorithms (enumeration results in random order) and trying to understand their downstream applications in real-world ...
1
vote
1
answer
69
views
What is the fastest algorithm for generating all non-isomorphic unlabeled free trees for n-vertices, and also for caterpillar trees of n-vertices?
I'm aware of some algorithms for each problem such as the WROM algorithm for unlabeled free trees and the algorithm from this page for all caterpillar trees of n-vertices.
However, I haven't been able ...
- 11
1
vote
1
answer
130
views
Constraints on the order of program semantics given by an enumeration of turing-complete system programs
There are Turing-complete systems like Jot where every natural number can be mapped to a valid program. This results in a Gödel numbering.
Now, if the semantics of the programs were, say
...
- 213
1
vote
1
answer
85
views
Generating all unique (tape content, head position) possibilities for a Turing Machine
Assuming a single tape (which extends infinitely in both directions) Turing Machine,
If its head and tape contents start at position $0$ and the tape contents are only extended to the right, then it ...
- 213
0
votes
1
answer
50
views
How can I estimate the time and cost (in relation to the machine and vocabulary) to enumerate sentences of English of n words?
I want to consider:
a vocabulary $V$ of $n$ distinct English words
a sequence of $m$ words, selected from $V$ (with repetition allowed)
a function $a$ which enumerates all unique sequences of $m$ ...
- 182
5
votes
0
answers
121
views
Rank and unrank for Heap's Algorithm
I am looking for an unranking (and ranking) algorithm for permtuations that is consistent with the order that Heap's Algorithm generates permutations.
I have been researching a bit on ranking and ...
- 151
0
votes
1
answer
67
views
Enumerating proper intersections
Let
$U \subset \mathbb{N}$ be a finite universe set;
$B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
1
vote
0
answers
67
views
Code to list all maximal bicliques of a bipartite graph
We are looking for a code to list all maximal bicliques in bipartite graphs efficiently, as we want to run it on (large and sparse) graphs, with up to roughly a million nodes and edges in no more that ...
- 11
2
votes
1
answer
113
views
Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"
I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is ...
- 1,081
1
vote
1
answer
356
views
Enumerator for $L=\{0^{3^n}| n\ge 0\}$
I need to build an enumerator for $$L=\{0^{3^n}| n\ge 0\}, \Sigma = \{0\}, \Gamma = \{0, x, \sqcup\}$$ that has at most 10 states, including print and halt states. I can ignore the halt state and any ...
- 261
1
vote
1
answer
218
views
Iterating over combinations of 4 timestamps from 2 timelines *efficiently*
I need help in finding a more performant algorithm.
I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list ...
- 11
0
votes
0
answers
119
views
Iterate through all values of a certain subset of all permutations
Let's say we've got $n$ numbers to multiply together. But the multiplication operation, like in computer floating-point arithmetics, is not associative. Thus the order of multiplication matters.
...
- 201