Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 [tag:computability] and [tag:semi-decidability] for these.

2
votes
1answer
82 views

Which one of these two sets is computably enumerable?

M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language. {M : |L(M)| <= 330} {M : |L(M)| >= 330} I don't quite understand what this question is asking. ...
1
vote
2answers
22 views

Turing machine to output enumeration of a language

I am trying to write a Turing machine enumerator that enumerates the language where $w = 0^n1^n$ and $n ≥ 0$. So for example it should output the following to the first tape: ...
-1
votes
0answers
47 views

Finding all subsets of a set

I have a set, and i want to find all its subsets. what is the best time complexity to find it? What is the most efficient algorithm to find all subsets of a set?
0
votes
1answer
24 views

What is the optimal algorithm for finding all sets of overlapping ranges?

I have a set of (integer) ranges and want to compute the (possibly non-disjoint) set of all subsets of overlapping ranges. The data structure used for the output is not of particular importance to me; ...
0
votes
3answers
136 views

Proof that total computable functions are not enumerable

In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made: Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all ...
1
vote
1answer
26 views

Testing graph property on enumerated graphs

I wanted to verify some graph properties on all possible graph enumerations (or graphs satisfying certain properties). There is a list of all the graphs upto 10 vertices here, but that is not ...
1
vote
2answers
55 views

Generate all sub paths

I have a path from node 1 to node n, which I can represent as a set: S = {1, 2, ..., n-1, n}. I want to efficiently generate the set of all subpaths from 1 to n. For instance, for n=5, we have S={1,2,...
0
votes
1answer
92 views

All possible Red Black Trees with this set {1,2,3,4,5}

I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}. Now we have 120 ways to write 1,2,3,4,5 ...
2
votes
1answer
97 views

Generating all words of length n in a CFG

Given a CFG for a (infinite) language $L$, is there an efficient algorithm that generates all possible words of length $n$ in $L$? Preferably efficient in time, and with low memory usage. I'm only ...
1
vote
0answers
43 views

How to enumerate all partitioning of a set to k-subsets of size at most b

I'm looking for an algorithm to generate/enumerate all possibilities for partitioning a set of size $n$ to $k$ non-empty subsets, each with size at most $b$. More specifically, given a set $V$ where $...
2
votes
1answer
175 views

Bipartite Perfect Matching “Assignment Problem” - finding an assignment of a particular weight

The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to ...
4
votes
1answer
145 views

How to compute all primes between upto $n$ in time $O(n)$ time?

Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$. For $j=2$ ...
1
vote
1answer
40 views

Checking if the mimimum is unique

We have a finite poset and its subset $S$. We can enumerate elements of $S$ using an iterator. I need to check if there are more than one minimal elements of $S$ (regarding the above poset). The ...
0
votes
1answer
61 views

An algorithm to generate all connectible pair combinations

In this thread I am seeking for an advice or a starting point on how to solve the following riddle. I need to come up with an algorithm which will generate all possible combinations, but I don't know ...
0
votes
0answers
82 views

Enumerating path variations

I have a graph and I'm trying to enumerate all paths that start at node $S$, end at node $E$, uses each edge, and minimizes the number of edges used (i.e. it can only re-use an edge if strictly ...
4
votes
1answer
548 views

Using reduction to prove that a given language is not recursively enumerable

Let the language $L$ be as follow ; $$L=\{\langle M_1 \rangle \langle M_2 \rangle \mid L(M_1) \cap L(M_2)=\emptyset \}$$ $\langle M_1 \rangle$ and $\langle M_2 \rangle$ are the encoding of the ...
2
votes
1answer
190 views

Algorithm for computing partitions of a set of n elements into subsets of size m

I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m. For example for $n=4$ for the set $\{a,b,c,d\}$ and $m=2$ the output should be $\{\{\{...
3
votes
1answer
91 views

Counting Colorings of a Grid

Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent ...
0
votes
1answer
28 views

Enumerate all maximal subset of a weighted knapsack

Given a knapsack $A$ composed of $(u_i, v_i)$-item where $u_i$ is the item identifier and $v_i$ is the weight of the item. I call a maximal subset when you consider a subset $S$ of $A$ where the sum $...
1
vote
0answers
50 views

Generating all legal starbattle grids

I am trying to generate a type of logic puzzle called starbattles. The puzzles consist of an nxn grid that is divided into n distinct regions. The rules of the puzzle are to place stars in the grid ...
1
vote
1answer
90 views

Fitness model for scale free networks

In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model: 1) we assign every node a "weight" $\theta_i$ (or two in the direct case). 2) we place $m$ ...
0
votes
2answers
234 views

Is it possible to prove closure of decidable languages under union and intersection, using enumerators?

We can use multi-tape enumerators. (Of course it is not valid to use turing machines albeit the fact that any enumerator has an equivalent TM) What we need is to prove that if $A$ and $B$ are ...
1
vote
1answer
244 views

What's the most efficient way to print all paths from root to leaves in a directed graph?

I have a directed graph created in matlab. I am trying to print all paths from root to leaves. I used stack to implement my algorithm but it seems very slow when I have large number of nodes and edges....
1
vote
0answers
32 views

What do you call a set which has the following enumeration-related machine?

A set $S$ of natural numbers is Recursively Enumerable if there exists a Turing machine which enumerates them, i.e. given no input, outputs the elements of $S$ in increasing order (never halting if $...
0
votes
1answer
31 views

Function that enumerates a recursively enumerable language

I have an exercise where one is supposed to give a function that will enumerate the following language: $L_1 = \{ a^pb^p \hspace{1mm} |\hspace{1mm} p \in \mathbb{N} \hspace{1mm} \wedge \text{ (P is ...
1
vote
1answer
55 views

How to write program to list all the function values without repeating?

Suppose I have a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ whose range is infinite, and I want to list all the function values without repeating. That is, if $f(0)=1,f(1)=1,f(2)=5,f(3)=6,f(4)=...
0
votes
0answers
210 views

Finding all paths from s to t in linear time

I was looking at the following algorithm which prints all the paths from node s to node t and I have some questions I don't ...
1
vote
2answers
66 views

Generating words in given format

i am looking for an algorithm that will generate all possible combinations of words from given dictionary that satisfy given format. Let me explain what i mean with format: For example, if the ...
0
votes
1answer
107 views

$f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable? [closed]

I have known that: A function $\Bbb N → \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$. Now I am considering about the partial functions. Is it the fact that: ...
5
votes
3answers
150 views

Why aren't computables used for numerical calculations?

In programming languages like Haskell you can use lazy evaluation to delay calculations. Why isn't a similar approach being used for numerical methods (I understand that there would be memory ...
1
vote
1answer
44 views

Is there a known algorithm for computing the n-th Turing machine directly? [duplicate]

Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M_1$ can be represented by 9,900,599 ([0 0 halt],...
1
vote
1answer
45 views

Smallest number with in a larger number with a certain length

I have a number with $n$ digits. I want to keep only $m$ digits out of it. What is the smallest possible $m$ digit number which can be generated from the larger number so that order of digits is ...
0
votes
0answers
49 views

Adapting Dijkstra to list all shortest paths [duplicate]

I found a code in the internet for Dijkstra's shortest path algorithm in PHP. The problem is it only shows one possible path. If there are several paths having the same distance, it only outputs one ...
1
vote
2answers
83 views

How to generate all $n$-bit numbers with certain bits fixed?

Consider the example where $n = 4$, bit 0 is fixed at 1, and bit 2 is fixed at 0. I would like to generate all $n$-bit numbers with those bits fixed. Essentially, everything I generate would have the ...
8
votes
0answers
123 views

What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?

Lets consider two node-labeled rooted trees Q and D. According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
3
votes
0answers
205 views

Find all rooted subgraphs of a DAG

I searched the exchange and couldn't seem to find an answer to this. I am trying to find an algorithm that, given a directed acyclic graph (DAG) $G = (N,E)$ with a single root node $r\in N$, finds ...
0
votes
1answer
104 views

Creating a decision tree?

So I'm trying to split on an attribute "Color" that has possible values (Blue,Green,Red,Orange,Pink). I'm splitting on entropy values, and the best split can either be Multi-Way 5, Multi-Way 4, ...
4
votes
1answer
261 views

Enumerating sets in a random order

I have multiples arrays. I'd like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets. Any solution, even ...
4
votes
1answer
31 views

# of permutations satisfying special inequalties of each element0

Recently I was solving a counting problem, which needed this subproblem to be solved: Given integers $n$ and $t$ (where $1 \le t \le n$) and a decreasing function $f$, find the number of permutations ...
15
votes
1answer
269 views

Complexity classes pertaining to listing all solutions?

I was reading a question over at Stack Overflow asking whether it was NP-hard to list all simple cycles in a graph containing a particular node and it occurred to me that I couldn't think of any ...
2
votes
3answers
78 views

Enumerate all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers

I want an algorithm to list all possible ways to map a series of integers $M = \{1,2,3,...,m\}$ to another series of integers $N = \{1,2,3,...,n\}$ where $m > n$, subject to the constraint that ...
3
votes
1answer
473 views

Finding all faces in a wireframe mesh

I'm trying to find an algorithm for finding all faces in a wireframe mesh. Wireframe means only the vertices and edges are given as input. There is no restriction on the number of edges a resulting ...
4
votes
2answers
109 views

Find a string that covers many sets of binary strings with don't-cares

Consider $N$ sets $S_1,S_2,....,S_{N}$ of binary strings with don't-cares ($X$) with $|S_i| = n$ and the length of all strings is $m$. In my application, $N=1000$, $n=100$ and $m=500$. I have to find ...
1
vote
0answers
210 views

Greedy Algorithm to return multiple optimal solutions

How would one go about enumerating all the optimal answers for interval scheduling? Not sure what to begin with, my guess is to use the other approaches i.e. earliest start time, shortest interval ...
4
votes
1answer
860 views

Find all cycles through a given vertex

Given a directed graph $G$ and a vertex $v$, how can we enumerate all simple cycles that pass through $v$? I found a question that describes how to enumerate all simple cycles in $G$, but I want only ...
2
votes
1answer
180 views

Linear time algorithm for finding $k$ shortest paths in unweighted graphs

Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the ...
8
votes
1answer
700 views

Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
2
votes
1answer
135 views

Term for open-ended algorithms

There are some enumeration problems which have little input, except for some termination criterion. Examples for the question at hand would be enumeration of prime numbers in ascending order ...
-2
votes
2answers
523 views

Count all numbers up to X that are divisible by at least two of their digits

I want to count how may numbers are there in range [1,X] which are divisible by at least two of their digits, different and >1. I found a sequence on OEIS, but this will take lot of time to generate ...
0
votes
0answers
54 views

How to see if P is decidable semi-decidable, undecidable?

I've been trying to figure out a practice exam question, about if a given $P$. $P$ is the characteristics of recursive enumerable set given as: $$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\ ...