The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged

1

Let $\Sigma$ be your alphabet, and $w \in \Sigma^*$ be your word. Let $w_i$ be the word consisting of the first $i$ characters of $w$ (for $i \le 0$, $w_i$ is the empty word $\varepsilon$). For $c \in \Sigma$, let $S[i,k,c]$ be the number of subsequences of $w_i$ that end with character $c$ and have length $k$. Moreover, for a word $w'$, let $\ell_c(w')$ be ...


2

Let's solve your example question first. Say, we want to know the number of combinations of size 2 possible from $A, B, C$. This would be equal to for each element in $A$, pair it with each element in $B$. This gives us $|N_A||N_B|$ combinations of size 2. for each element in $A$, pair it with each element in $C$. This gives us $|N_A||N_C|$ combinations of ...


2

If I understand the question, your problem is the following: Given a regular language $L$ over alphabet $\Sigma$ and a positive integer $n$, compute the probability that a word chosen uniformly at random from $\Sigma^n$ will be in $L$. That's equivalent to computing $|L \cap \Sigma^n|$, i.e., the cardinality of the language $L \cap \Sigma^n$. Note that $...


1

Every $m$-ary tree is a node together with up to $m$ children, which are also $m$-ary trees. Let $T(x,y)$ be the generating function in which the coefficient of $x^ny^k$ is the number of $m$-ary trees with $n$ nodes and $k$ full nodes. Then $$ T(x,y) = x(1 + T(x,y) + \cdots + T(x,y)^{m-1} + yT(x,y)^m). $$ The generating function of the total number of $m$-...


1

Your problem is related to the balanced tournament design problem. Suppose that you have $2n$ tennis players, there are $n$ tennis courts, and you need to play a round robin tournament in $2n-1$ rounds. The courts aren't the same, to to balance the effect of the different courts, you want to ensure that no player competes more than twice on any one court. ...


1

As pointed out by @Pseudonym, this problem is identical to finding a round robin tournament schedule. A straightforward implementation would be the following: def get_sets(a: list): # Simple implementation of # https://nrich.maths.org/1443 center, *rest = a for _ in range(len(rest)): rest = rest[1:] + rest[:1] # put 1st element to ...


Top 50 recent answers are included