Sorting a collection of tuples using merge rearrangements

7H3ju

Guest

Dec 5, 2022

7H3ju Asks: Sorting a collection of tuples using merge rearrangements
Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements $x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is sorted if $x_i \leq x_{i+1}$ and $y_i \leq y_{i+1}$ for all $i \in [n-1]$. Sorting $X$ is not always possible for instance if the given input has two tuples $(x_i,y_i), (x_j,y_j)$ such that $x_i > x_j $ and $y_i < y_j$ for some $i \neq j$. So we want to merge tuples in $X$ so that the resulting collection is sorted and the merge operation $\phi(i,j,k)$ is defined as $$\phi(i,j,k) := \Big\{\text{assign}~X[k] \gets \big\{(x_k,y_k) = \big(\frac{x_i+x_j}{2}, \frac{y_i+y_j}{2}\big)\big\} ~\text{and delete}~(x_i,y_i), (x_j,y_j)~\text{from collection}~X \big\}.$$

The problem always has an obvious solution with $(n-1)$ merge operations i.e, merging everything to a single tuple is always feasible. But we would like to find the minimum number of merge operations required to sort the collection.

Even though we suspect that finding the minimum number of merge operations is NP-hard, we do not have a hardness proof to support the claim. The problem looks like something which might have been already studied in the literature. If you are aware of any related or similar problems please guide us to relevant results. Any pointers or clues for hardness or algorithmic results are helpful.

Example: Given $X=\{(1,4),(2,2),(3,2),(4,1)\}$ with two merge operations i.e, $\phi(1,4,3)$ followed by $\phi(1,2,1)$ we can obtain $\{(2.5,2),(2.5,2.5)\}$, which is sorted.

$$\{(1,4),(2,2),(3,2),(4,1)\} \xrightarrow[]{\phi(1,4,3)} \{(2,2),(3,2),(2.5,2.5)\}$$ $$\{(2,2),(3,2),(2.5,2.5)\} \xrightarrow[]{\phi(1,2,1)} \{(2.5,2),(2.5,2.5)\}$$

Note: If the merge operation is restricted to operations of the form $\phi(i,i+1,i)$, then the minimum number of operations can be found in polynomial time using a dynamic programming algorithm.

Thanks in advance.

You must log in or register to reply here.

Unreplied Threads

How to combine nlp and numeric data for a linear regression problem

davidm
22 minutes ago
Computer Science
Replies: 0

davidm Asks: How to combine nlp and numeric data for a linear regression problem
I'm very new to data science (this is my hello world project), and I have a data set made up of a combination of review text and numerical data such as number of tables. There is also a column for reviews which is a float (avg of all user reviews for that restaurant). So a row of data could be like:

Code:

{ 
    rating: 3.765, 
    review: `Food was great, staff was friendly`, 
    tables: 30, 
    staff: 15, 
    parking: 20
    ... 
}

So following tutorials, I have been able to do the following:

Created a linear regression model to predict rating with the inputs being all the numerical data columns.
Created a regression model to predict rating based on review text using sklearn.TfidfVectorizer.

But now I'd like to combine models or combine the data from both into one to create a linear regression model. So how can I utilize the vectorized text data in my linear regression model?

[Solved] Trimble Data Transfer won't convert files

Tiago Cavalcante
22 minutes ago
Geography
Replies: 0

Tiago Cavalcante Asks: Trimble Data Transfer won't convert files
I was importing files from Trimble Recon for over 3 years and this never happened with me.

When I conect my controller and select the file to import, the file load 100% and when start to convert appear this error. I tried in 5 computers and 4 controllers recon too.

Asked to local support but they can't find the solution.

Is there an equation depicting a compressible fluid flowing into a cone, increasing in pressure and velocity as the cone narrows?

Aneikei
22 minutes ago
Physics
Replies: 0

Aneikei Asks: Is there an equation depicting a compressible fluid flowing into a cone, increasing in pressure and velocity as the cone narrows?
I'm trying to write an equation which shows a compressible fluid entering a cone with radius R and length L, where the pressure (density) and velocity of the compressible fluid increases as the exit radius R' narrows, a huge bonus would be given the mass of the fluid to also be able to calculate the overall mass of the fluid based on the volume of the cone.

Thank you so much in advance. Also, this is not for homework. It's for a pet project I'm working on.

Multiplicity of a holomorphic map at every point is one

Spectrum
22 minutes ago
Mathematics
Replies: 0

Spectrum Asks: Multiplicity of a holomorphic map at every point is one
Let $F$ be a holomorphic map between two compact Riemann surface $X,Y$. Assume for each point $p\in X , mult_p(F)=1$. Then ,what can we say about the degree of that map (deg(F))?

Locally $F$ looks like a coordinate chart function. Can we say $F$ is an isomorphism? I am reading "Riemann Hurwitz formula " this question came in my thought but unable to get answer.

Prime Ideal Theorem implies Hahn Banach Theorem

mathlearner98
22 minutes ago
Mathematics
Replies: 0

mathlearner98 Asks: Prime Ideal Theorem implies Hahn Banach Theorem
I am reading Jech's Axiom of Choice, and there is this exercise: chapter 2 Problem 19:

I came up with a (possibly wrong) proof, and my idea is essentially to mimic the proof of the implication "Prime Ideal Theorem $\implies$ Consistency Principle for Binary Mess" (the proof of this implication is in Jech's book chapter 2). Because I am a novice in this field, I really am not sure whether or not I am missing something, so I would really appreciate if you can point out if I am missing something.

Let $V$ be a real vector space and $X\subset V$ be a subspace. Let $p$ be a sublinear functional on $V$ and let $f$ be a linear functional on $X$ such that $f(x)\leq p(x)$ for all $x\in X$. Using Ultra Filter Theorem (which is equivalent to the Prime Ideal Theorem) we will show that there is a linear functional $F$ on $V$ such that $F(x)\leq p(x)$ for all $x\in V$ and $F\restriction_X=f$. We will use this lemma without proof (proof can be found at page 158 Folland):

Let $I$ be the set of all finite dimensional subspaces of $V$. Let $$M:=\{g:g\text{ is a linear functional on some }P\in I\text{ compatible with }f\text{ and }g(x)\leq p(x)\text{ for all }x\in P\}$$ From Lemma A, for each $P\in I$, there is some $g\in M$ with $\text{dom}(g)=P$. For each $P\in I$, let $M_P$ denote the set of all $g\in M$ such that $\text{dom}(g)=P$. We take $Z$ be the set of all functions $z$ such that:

a) $\text{dom}(z)\subset I$;

b) $z(P)\in M_P$ for each $P\in \text{dom}(z)$;

c) for any $P,Q\in \text{dom}(z)$, the functions $g_1=z(P)$ and $g_2=z(Q)$ are compatible.

Let $\mathbb{F}$ be the filter over $Z$ generated by the sets $$N_P=\{z\in Z

\in \text{dom}(z)\}$$ $N_P$'s indeed do generate a filter over $Z$ because for $P_1,...,P_n\in I$, we know $N_{P_1}\cap \cdots\cap N_{P_n}$ is non-empty, as $P_1+\cdots+P_n$ is still a finite dimensional subspace of $V$, and hence there is some linear functional $g$ on $P_1+\cdots+P_n$ such that is compatible with $f$ and $g(x)\leq p(x)$ for all $x\in P_1+\cdots+P_n$. Then $z:=\{(P_i\to g\restriction_{P_i}):1\leq i\leq n\}$ is inside $N_{P_1}\cap\cdots\cap N_{P_n}$.

By the Ultra Filter Theorem, we may let $U$ be an ultra filter over $Z$ that extends $\mathbb{F}$. Now, fix $P\in I$. For each $g\in M_P$, denote $O_g:=\{z\in Z:z(P)=g\}$. Then note that $N_P=\bigcup_{g\in M_P}O_g$ and that $O_g$'s are pair-wise disjoint. Also, each $O_g$ is non-empty. So from the fact that $U$ is an ultra filter, there exists a unique $g\in M_P$ such that $O_g\in U$. Hence, for an arbitrary $P\in I$, we found a unique choice of a linear functional (which we denote by) $g_P$ defined on $P\subset V$.

We claim that $g_P$'s for $P\in I$ are pair-wise compatible. For $P,Q\in I$, we know $O_{g_P},O_{g_Q}\in U$. Hence, $O_{g_P}\cap O_{g_Q}\neq\emptyset$. This means $g_P$ and $g_Q$ are compatible. Now, if we take $F:=\bigcup_{P\in I}g_P$, then $F$ is the desired linear functional on $V$.

Thank you in advance for any help!

Confusion Between Event Space and Probability

stats_noob
22 minutes ago
Mathematics
Replies: 0

stats_noob Asks: Confusion Between Event Space and Probability
I am having difficulty understanding the difference between Event Space and Probability.

Initially, I had always thought the following. Consider rolling a 6-sided die once:

The Event Space : 1,2,3,4,5,6
The Probability : All Events have a Probability of 1/6

I thought everything made sense until I read the following passage:

" In frequentist theory probability of an event is relative frequencies of that event over a large number of repeated trials of the experiment in question. Therefore, the parameters of a distribution are fixed because they stay the same in all the repetitions of the experiment. In Bayesian theory, the probabilities are degrees of belief in that an event would occur for in a single trial of the experiment in question. The problem with frequentist definition of probability is that it cannot be used to define probabilities in many real world applications. As an example, try to define the probability that I am typing on an android smartphone. Frequentist would say that the probability is either 0 or 1 . While the Bayesian definition allows you to choose an appropriate number between 0 and 1."

The above passage claims that using the Frequentist definition of Probability, the probability of someone typing on an Android Smartphone is either 0 and 1 - whereas the Bayesian definition of Probability allows for the probability of someone typing on an Android Smartphone being between 0 and 1.

This is very confusing for me - in this question:

I would have initially believed that the "Event Space" is "either 0 or 1" whereas the Probability could be a number "between 0 and 1".
Furthermore, I am confused as to why the Frequentist definition forces you to believe that the probability is either 0 and 1, whereas the Bayesian definition allows you to believe that the probability is between 0 and 1.

To illustrate my logic - here is what is going on in my mind:

Suppose there are 1000 people in a room. We take a survey and find out that 543 people are using Android Smartphones and 457 people are using Apple Smartphones.
Now, we realize that there were actually 1001 people in this room and we had forgotten to survey one person. As an experiment, we would like to estimate the probability whether this person has an Android phone or an Apple phone. As a key and fundamental assumption, we assume that this new person is representative of the 1000 people we just surveyed.
A Frequentist would estimate that there is a 0.543 probability that this new person is using an Android Phone and could calculate a 95% Confidence Interval on 0.543. This Confidence Interval would tell the Frequentist that "if he could magically walk into 20 such similar rooms in different parallel universes and if he were to estimate the proportion of Android users - in 19 of these cases, the true proportion of Android users in each room would be contained in the corresponding 95% Confidence Intervals".
Regarding this new person that was not surveyed, the Frequentist could say that "if 100 new people were there, roughly 54 of them would be Android users - however, in the case of this single new person, this new person can either be an Android user or not: since 0.54 is technically closer to 1 compared to 0, I will guess that this new person is an Android user and I am 54% confident in my guess".
Now, suppose a Bayesian observes the same 543 people but is given some additional Prior information that "in larger populations similar to the people sitting in the room they are in, 71% people of such people are believed to be Android users". The Bayesian can incorporate this Prior information through the form of a Beta (alpha,beta) Probability Distribution and estimate the proportion of people to "truly" be Android users (e.g. based on his MAP calculations, he might get an estimate of 0.65). He can also use this information to estimate the probability that this new 1001th person is an Android user is actually 0.64.
However, this 1001th person is either an Android user not - the Bayesian can still believe that in 100 new people, 65 of them will be Android users, but he is still forced to make a choice whether this new person is an Android user or not. Since 0.65 is closer to 1 compared to 0, the Bayesian might also believe that this new person is Android user and might (falsely) feel more confident about his estimate.
The Bayesian can also create a 95% Credible Interval but it will have a slightly different interpretation - The Bayesian can believe that there is a 0.95 probability that the true proportion of Android users in a similar population is contained within the 95% Credible Interval that he calculated. However, the Bayesian has no means of walking into parallel universes and repeating this experiment many times.

After this lengthy (and likely incorrect) summarization of my understanding - I reached the following conclusions:

In this Android Phone problem, the Event Space is either "1 or 0" (yes or no), but the Probability of these events is between "1 or 0" - regardless of the Frequentist or the Bayesian Interpretation of probability.
Assuming I am correct (which I am not) - how is the Bayesian definition of Probability any more flexible and versatile compared to the Frequentist definition of Probability?

Thanks!

Notes:

https://en.wikipedia.org/wiki/Maximum_a_posteriori_estimation

The points of inflection are of order $1$ or $3$

Frederick Manfred
22 minutes ago
Mathematics
Replies: 0

Frederick Manfred Asks: The points of inflection are of order $1$ or $3$
I'm currently working on the book of Kirwan about "Complex algebraic curves" I don't understand this part of chapter 6.2:

I don't understand, why we can conclude that the point of inflection on $C_{\Lambda}$ are precisely the points of order $1$ or $3$. I guess, that order $3$ comes from the fact, that $p+p+p=0$ iff $p$ is an inflection point but what about order $1$? There we know nothing or do I oversee something?

Facebook Twitter Reddit Pinterest Tumblr WhatsApp Email Link