All Questions
Tagged with ordering algorithms
15 questions
1
vote
1
answer
57
views
Efficient ways to sort pairwise distances for set of points in Euclidean space?
Consider a Euclidean space $\mathbb{R}^d$. Consider $ X \subset \mathbb{R}^d$ where $X$ is a finite set with $|X|=n$. Consider the set of line segments $\{xy | x,y \in X\}$ . I have a process $Z$ that ...
- 13
2
votes
3
answers
223
views
Partition an array in two groups while keeping the relative order within both groups
I came across the following problem in the book "Elements of Programming Interviews in Python".
Given an array A of n objects with Boolean-valued keys, reorder the array so that objects ...
- 173
1
vote
1
answer
40
views
Is there a sub-NP algorithm to satisfy or prove unsatisfiable a set of a<b<c OR c<b<a constraints
This problem's been stumping me for the better part of a week:
You're given a set of triplets of variables. The variables are all distinct and ordered. Each triplet $a,b,c$ means that either $a<b&...
- 300
2
votes
1
answer
40
views
Optimal order to minimise time until first success
Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t_i$ time to talk to and there is $p_i$ probability to make the sale to that customer - ...
- 23
1
vote
1
answer
43
views
Interactive sort for only top elements
I have a set of objects and a set of comparison results for some of them.
I want an algorithm that returns the next comparison I should make to two objects towards having a way to know the full order ...
- 111
2
votes
1
answer
557
views
Generating Unique Ids for Objects
I have an Object Pool and I will be using it to create Objects. I want to generate an unique id for each object. id should be an integer starting from 0. Ids should be continuous. When an object is ...
- 125
3
votes
1
answer
294
views
Producing a total or partial order from an inconsistent relation
Imagine I want to construct a total order from a set of elements, $E$, but the comparison function produces results that are non-deterministic. I produce a list of element pairs (e, e) through ...
- 105
-1
votes
1
answer
56
views
Black-Box Machine
Suppose we have mysterious machine which return median $m$ of given set $S$ and set $S/\{m\}$ in constant time, where $S/\{m\}$ denotes the difference of $S$ and element $m$. Prove that we can sort ...
- 109
1
vote
0
answers
52
views
Algorithm suggestion to order data with specific condition
Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller hamming distance should be placed as ...
- 141
0
votes
1
answer
76
views
How to sort objects based only on "less than" relationships?
Say I have n objects, each with an unknown value, and a n by n matrix Z. Such that Z(i,j)=1 if the value of object i is less than the value of object j, and Z(i,j)=0 otherwise. How can I sort these n ...
- 111
0
votes
0
answers
32
views
Algorithm to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$
We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of ...
- 145
0
votes
0
answers
10
views
How to define the stability (or convergence) of a ordering of a list of node
I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling ...
3
votes
2
answers
544
views
Algorithm for detecting overlaps
This is a real-world application, not a student assignment.
Suppose a list of events of that have startTime and endTime, and ...
1
vote
1
answer
33
views
Extend reachability to total ordering
Given a finite DAG $G = (V, E)$ with $|E| \in \mathcal{O}(|V|)$, I want to compute a total ordering $<$ over $V$ that is compatible to reachability: If there is a transition $(u, v) \in E$, then $u ...
- 635
6
votes
2
answers
2k
views
Algorithm: ordering non-overlapping intervals
Assume we have a (multi)set of nontrivial intervals $\mathcal{I} = \{I_1,...,I_n\}$ and for any two $I_i, I_j \in \mathcal{I}$, we have that $I_i \cap I_j$ is trivial (that is: contains at most one ...
- 2,019