Questions tagged [ordering]
The ordering tag has no usage guidance.
37 questions
0
votes
1
answer
54
views
Binary subset rank and unrank
Let there be "N" bits.
We want to rank and unrank a specific subset of bit combinations based on the following criteria -
...
- 25
1
vote
1
answer
110
views
What happens when two different nodes have the same Lamport clock ID
With Lamport clocks, each node keeps its own counter. Before sending a message, a node increments its counter by one: LC(A)=LC(A)+1, and sends ...
- 123
1
vote
0
answers
18
views
What simple constructions / algorithms for sorting and selection networks from k-sorters (k>2) are known?
There are simple algorithms to construct sorting networks from 2-sorters, e.g. Batcher's bitonic sorters and Pairwise sorting networks.
How can one construct general sorters with a low number of $k$-...
- 1,126
1
vote
1
answer
56
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
1
vote
1
answer
28
views
Ranked voting method where unranked candidates on a preference list aren't taken to be the least preferred?
Say there are 5 candidates, A, B, C, D, and E. An election is held using a ranked voting method. That is to say, each voter submits a preference list (the order in which they prefer candidates). E.g. ...
- 542
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
3
votes
1
answer
480
views
Lamport Timestamps and Causality
I'm having trouble understanding lamport timestamps in practice and how they guarantee causal ordering.
Definitions
Lamport defines the "happens before" relationship in his paper. He states ...
- 133
2
votes
0
answers
135
views
A total order of rectangles related to containment
Suppose you have a set of rectangles $R_1,\dots,R_n$ in the plane, each described by an upper left point $p_1 \in \mathbb R^2$ and a lower right point $p_2 \in \mathbb R^2$, all pairwise different.
...
- 161
3
votes
1
answer
228
views
Designing a Queue that efficiently tracks position
Suppose we want to construct a queue with the following properties:
The priority of each member of the queue must be known. For example, for the head node, their priority is 1, for the next node, ...
- 314
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
0
votes
2
answers
2k
views
How come the set of all binary strings is uncountable?
Sorry for bumping this very old problem which already has answers on multiple SE sites, but I just cannot understand any of the answers.
Let $\Sigma_{bool} = \{0, 1\}$.
Then, $(\Sigma_{bool})^*$ is ...
- 127
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
2
votes
1
answer
299
views
Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$
In a hypothetical world, we have a machine that can find median of $n$
numbers in $O(\sqrt{n})$. (Of course this machine is not real).
Can we use this machine to sort an array in $O(n)$?
I don'...
- 145
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
2
votes
1
answer
72
views
totally ordered semigroups
Given a semigroup is it possible to give a total order to it?
If not possible in the general case then what about the case of finitely generated finite semigroups?
Does there exist a natural ...
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
590
views
Which order is "lexicographic order"?
To choose 3 items out of 5 items [1, 2, 3, 4, 5], Donald Knuth's lexicographic algorithm (The Art of Computer Programming, Vol 4A, 2011, p. 358, Algorithm L (...
- 413
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 ...
2
votes
1
answer
154
views
How to reduce number of move operations in an array?
Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...
- 133
3
votes
1
answer
82
views
Random observations of a total ordering, how much they tell us?
Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know ...
- 531
0
votes
0
answers
189
views
Sorting binary string in colex order
Do you know where Can I find an algorithm to sort a set of binary strings in colex order?
Recall, that two k−element subsets A and B
of a set with strict linear ordering $<$ are said to be in co-...
- 503
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
0
votes
2
answers
44
views
Sort by typical position?
Lets say, we have a lot of lists (sequences of variable length) of some limited set of elements:
...
- 283
0
votes
1
answer
39
views
Creating a numbered list, divided into types, without need for shifting or re-ordering - is this a re-occuring problem
My question is not for a solution to the problem, though I do need to put thought into it but rather my question is if this conceptual problem has a name or has been addressed at already in computer ...
3
votes
1
answer
1k
views
Understanding the bandwidth problem on graphs
I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list:
...
- 31
3
votes
1
answer
137
views
existence of a permutation that satisfies order-constraints
I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints.
For example, suppose we have a set (1, 2, 3, 4, 5) and a ...
- 31
2
votes
2
answers
137
views
Functional programming with branches that have no order?
I was wondering if there is any programming style in which the outcome does not depend on the order of statements or groups of statements such as guards. Vaguely, I imagine this would leave room for ...
- 165
3
votes
0
answers
45
views
Original proof that orders eliminate deadlocks?
A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested.
Which ...
- 157
6
votes
4
answers
469
views
Order-preserving update of a sublist of a list of mutable objects in sublinear time
Description
Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to <...
- 173
6
votes
1
answer
78
views
Rating elements via partial orders
I would like to rate a set of $n$ elements, with each element assigned a rating from ${0,\dots, 10}$.
The way in which I want to rate is by repeatedly selecting subsets of $k$ elements and querying a ...
- 163
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