2
$\begingroup$

The following is a real world problem, for which I adjusted the explanation, such that it is easier to understand. In a very abstract form, the challenge is to find a group-sorting algorithm, that is only allowed to use queues.

Instance of the problem
Let’s assume we have people arriving in cars at the entrance of some festival.
Cars arriving at a festival queue

Several groups of friends are split up in different cars and, due to traffic, arrive at the entrance traffic jam at slightly different times.
When they arrive at the campsite, the friends in the different cars want to park and camp next to each other. However, only one car can enter the campsite at a time, and the organizers of the festival require that the cars park next to each other in the order in which they arrive at the campsite to avoid clutter.
Therefore, groups of friends will need to sort themselves out before arriving at the campsite. To avoid total chaos, the festival organizer sets up several intersections at the entrance traffic jam, so that the friend groups can use some algorithm to sort themselves.
The task is to find the optimal sorting algorithm for this problem.

More formally

Given an array of nominally scaled (i.e. they have no inherent order) elements $L = [x_1, x_2, …, x_N]$, where $x_i \in \{C_1, C_2, …, C_k\}$, and $C_i$ are cliques or groups of friends or colors (whatever suits you).

For ease of understanding, we stick to a binary split as in most sorting algorithms, i.e. we only have two lanes, see image. The extension to multiple splits should be straight forward. Abstract Sorting Flow

Let $(Q_1, Q_1’), …, (Q_M, Q_M’)$ be some pairs of queues, such that a queue $Q_1$ or $Q_1’$ can only put an element into the next queue $Q_{i+1}$ or $Q_{i+1}’$. The capacity of a queue is $n$ (number of elements we want to sort).

We call $Q_i$ and $Q_i’$ stage $i$ and require all $x_j$ to pass through stage $i$ before we continue doing anything in stage $i+1$. (At a festival people won’t accept a lot of empty space, they can get impatient and do unpredictable reshuffling. This means our queues will first sort some array $L_1$, then $L_2$, then $L_3$ and so on).

At the last stage, we merge $Q_M, Q_M’$ into the final array $L_{sorted}$.

Task: Find an algorithm, which uses as few stages as possible, such that in the final merge (on $L_{sorted}$) all friends / cliques / colors of one group are next to each other.

Some thoughts
In the classical sorting sense, we need to sort $n$ elements, with $k$ different properties.

A straight forward way to solve this is to use a radix-sort, which runs in $O(n \log k)$, thus we would have $\log k$ stages. However, we would have to assign numbers to the cliques, and thus ignore all permutations that could lead to a scenario where we can use less than $\log k$ stages.
If we wouldn’t be bound by queues, we could just use hash maps. However, people don't like being hashed and can't be teleported to a destination.
One could “just” try all permutations and see if there are solutions with less than $\log k$ stages. This is of course not tractable since there are $k!$ permutations.

$\endgroup$
1
  • 1
    $\begingroup$ I think the problem from this thread 1 is almost the same, except it is less constrained. Since [1] was shown to be NP-hard, this problem should also be NP-hard. $\endgroup$
    – luifire
    Commented Jan 4 at 10:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.