Questions tagged [ordering]
The ordering tag has no summary.
38 questions
1
vote
1
answer
75
views
Find rank of vector of length $k$ with elements up to $n$ in graded lexicographic order (grlex)
Let $v = (a_1, a_2, …, a_k)$ be a vector of length $k$, such that $0 \leq a_i < n$. Also let $|v| = a_1 + a_2 + \dots + a_k$ be a total degree of $v$. There is finite number of such vectors.
We can ...
- 133
0
votes
1
answer
110
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
165
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
59
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,194
1
vote
1
answer
94
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
1
answer
63
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. ...
- 652
2
votes
3
answers
310
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
83
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&...
- 310
3
votes
1
answer
593
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
170
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.
...
- 181
3
votes
1
answer
282
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
89
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
71
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
726
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