# 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.

113 questions
44 views

### Enumerate all paths in a given series-parallel graph

Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition. I have a graph ...
39 views

288 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 ...
154 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$ ...
44 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 ...
92 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 ...
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 ...
749 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 ...
317 views

58 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 ...
100 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$ ...
294 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 ...
337 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....
32 views

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 $... 1answer 33 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 ...
Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$? In The art of computer programming (Fascicle 3B) by Knuth, there's ...