# Tag Info

## New answers tagged combinatorics

0

This is a variation of the assignment problem. You will find several algorithms on the Wikipedia page linked, although none makes use of dynamic programming. You can transform your formulation into an assignment problem by subdividing each project in $c$ projects of one student each, and creating phantom students with no preferences to fill the remaining ...

1

This sounds like it could be solved using a flow network. Define the graph $G=(V,E)$ such that: Add a starting node $s$. It will be the "source" node in the flow-graph. Add a node $v_{s_i}$ for every student $s_i$. Add a node $v_{p_j}$ for every project $p_j$. Add the final node $t$. It will be the "sink" node for the flow-graph. Now, start adding the ...

2

"Binary toggling games" are generally just arithmetic problems over GF(2). Your particular problem is equivalent to the following over GF(2): $$\sum_i V_iS_i = 1 + A_M$$ If we write $\vec{S} = [S_1, S_2, \dots]^T$ and $V = [V_1, V_2, \dots]^T$ we find that your problem is actually a simple matrix equation over GF(2): $$V\vec{S} = 1 + A_M$$ You can ...

0

Count (energy, clones, min_energy): If enregy < min_energy or clones == 0: return 0 If energy == min_energy or clones == 1: return 1 Else: cnt = 0 For every cur_energy from min_energy to energy: cnt += Count(energy - cur_energy, clones - 1, cur_energy) Return cnt I am pretty sure the algorithm ...

2

If $|S|=2N$, then the largest "partnering" is a $1$-factorisation of the complete graph, or a round-robin tournament schedule. There always exists a schedule that pairs all people exactly once in $2N-1$ rounds without repeating pairs. There are various algorithms to find such a schedule, see the previous link.

0

The solution to the coin counting problem uses memoization as a way to decrease the exponential nature into just polynomial time. The trick here, is that the amount, is always decreasing and can be computed from all of the smaller leftover amounts. this ensures that we need to compute up to amount values, that every next value is easy to compute from the ...

5

Suppose that your team contains $n$ people. Each round of discussions ("session") corresponds to a matching in the complete graph $K_n$. Therefore you want to partition into as few matchings as possible. The answer depends on the parity of $n$. Case 1: $n$ is even. In this case, $K_n$ contains $\binom{n}{2}$ edges, and a matching contains at most $n/2$ ...

2

You can use recursion. def recursive_generate(S): IF #S = 1: s <-- the single set in S return {{item} | item \in s} END IF S' <-- {} s <-- some selected set from S FOR item in s: For r in recursive_generate(S\{s}): S' <-- S' \union (r \union {item}) END FOR END FOR RETURN S' ...

3

If you have $n$ sets of $k$ elements, your problem is equivalent to that of generating all numbers with up to $n$ digits in base $k$ (where the $i$-th digit of a number represents the index of the element to select from the $i$-th group). This can easily be done by starting from the number $(00\dots000)_k$ and iteratively adding $1$. Let $d_i$ be the $i$-th ...

1

Sure. Such a function exists. You have specified it. Basically, you order the equivalence classes according first to number of vertices, and second by number of edges. There are countably many graphs, so countably many equivalence classes, so they can be enumerated. When you can enumerate them, they can be put into bijective correspondence with \$\mathbb{...

Top 50 recent answers are included