Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ordering]

The tag has no usage guidance.

2
votes
1answer
49 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 ...
3
votes
1answer
48 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 ...
0
votes
0answers
50 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-...
1
vote
1answer
20 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 ...
0
votes
2answers
34 views

Sort by typical position?

Lets say, we have a lot of lists (sequences of variable length) of some limited set of elements: ...
0
votes
1answer
35 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
1answer
401 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: ...
3
votes
1answer
76 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 ...
2
votes
2answers
91 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 ...
3
votes
0answers
39 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 ...
6
votes
4answers
373 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 <...
6
votes
1answer
69 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 ...
6
votes
2answers
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 ...