Tag Info

1

Okay I'm writing another answer for the sake of tidiness. I suppose that the elements of your sets are integers. Otherwise one could just use pointers to the items. // INPUT sets := vector of your sets // BUILDING INVERTED INDEX sets_of := map of int (an item) to vector of int (indices of all sets containing it) for i, set in enumerate(sets): for item ...

1

I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive. From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \sim c$. For our undirected graph this implies that every node in a connected component is connected to every other node. This yields following simple algorithm: ...

0

Okay let's say you got $n$ matrices $M_1,M_2,...,M_n$ with dimensions $a_1\times b_1,...,a_n\times b_n$. Now we look at what happens to the dimension when we multiply two matrices $M_i, M_j, i\neq j$: $$(a_i\times b_i)(a_j\times b_j) = a_i \times b_j$$ Notice that you can only multiply the two matrices iff $b_i = a_j = p$: (a_i\times p)(p\times b_j) = a_i \...

1

This is a comment There is a confusion when you say that sorting is creating the correct total order. When sorting, the total order is input as the relation $\geq$. What sorting does is output the order-preserving map from the natural numbers $0,1,2,...$ to the totally ordered set (or multiset) that was input. Typically, when this is implemented the map is ...

1

This is a very well-known problem, known as topological sorting. Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.

1

For a binary tree, let $H(T)=\min_AH_A(T)$, where $A$ ranges over all favored-child assignments of $T$. Call $H(T)$ the skew height of $T$. Here is a simple observation. The skew height of a perfect binary tree of (ordinary) height $n$ is $n$, too. For a binary tree $T$, an edge is called a passing edge if one of the endpoints has exactly one child. We call ...

Top 50 recent answers are included