7
$\begingroup$

Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for any $i<k<j$. For example, $\{a,a,c,c,c,b,b\}$ is grouped, where as $\{a,b,a,c,c,c,b\}$ is not.

What is the minimum number of swaps needed to make a given sequence $s$ 'grouped'? Is the computational complexity (in terms of the length of the string and the size of character set) of this problem known in literature?

A practical motivation might stem from (not completely sure though) the process of "disk de-fragmentation", where 'pieces' of the same file are grouped together in contiguous memory segments. .

Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

The answers so far aren’t really addressing the question as asked. This is mainly a reformulation and a few simple observations.

First consider , for a fixed $N,k$ a graph with $\binom{N}k$ vertices labelled by the strings made of $k$ a’s and $N-k$ b’s. Each vertex has degree $k(N-k)$ with an edge to each string which results from swapping an a and a b. There are two distinguished vertices, $k$ a’s then $N-k$ b’s and the reverse.

Q: Given a particular vertex find the closest distinguished vertex and a path to it. The computational complexity matters but swaps are expensive. So it is really a question of finding the absolute minimum number of swaps.

In this case the distance between two strings is half the number of places they differ, i.e. half the Hamming distance. So find which of the two is closest and an optimal sequence of swaps should be clear.

I suppose the sequence $aaabbbaaa$ takes $3$ swaps and generalizes to $\frac{N}3$ swaps. Is that the worst case?

In case $N=2k$ is $ababab\cdots$ taking about $\frac{N}4$ swaps worst?

I general we have all length $N$ sequences resulting from a certain multiset with $M$ distinct characters. The number of these is given by a certain multinomial coefficient. There are $M!$ sorted sequences so we might not want to consider them all. The Hamming distance gives some bound on the distances but it might not be as simple as in the $M=2$ case.

Improve this answer
$\endgroup$
1
$\begingroup$

This is a sorting problem. The sorting algorithm that performs the minimum possible number of swaps in the worst-case scenario is selection sort, with $n-1$ swaps. Its time complexity is $O(n^2)$.

There are of course sorting algorithms that have lower time complexity, such as counting sort and merge sort, but they are irrelevant to the question because they do not rely on swapping items.

Improve this answer
$\endgroup$
5
  • $\begingroup$ There are $M!$ ways of ordering the characters, and post that one might want to do selection sort to figure out which worked the best. But the $M!$ factor is not very encouraging. Any workaround for that? And also, I would be interested in computing the minimum swaps for a given string (not the worst case scenario). $\endgroup$
    – DSM
    Commented Apr 29, 2020 at 10:31
  • $\begingroup$ Grouping the sequence might be easier than sorting it, though. $\endgroup$
    – smapers
    Commented Apr 29, 2020 at 12:20
  • $\begingroup$ @DSM, the minimum swap for a given string is likely to be very intractable. $\endgroup$
    – kodlu
    Commented Apr 30, 2020 at 1:24
  • $\begingroup$ @kodlu, thanks for the comment. That's my hunch as well. Not sure if there are good approximations. For example, say the string consists of $\{l_1,\cdots,l_M\}$ number of characters. Then if I choose an ordering (for selection sort) of the alphabets greedily based on the smallest Hamming distance between constant strings of character $c_k$ length $l_k$ and the sub-string $\{s_{{l_{j_1}+...+{l_{j_{k-1}}},..., s_{l_{j_1}+...+{l_{j_{k-1}}+l_k-1}\}$, how good would this approximation be? $\endgroup$
    – DSM
    Commented Apr 30, 2020 at 3:06
  • $\begingroup$ Not sure I get your suggestion right but wouldn't your proposal require computations for a large number of the $M!$ possible arbitrary orderings? (unless you have in mind a greedy approach with a Nemhauser-type guarantee on how close the outcome of a greedy approach would be to the true optimum) $\endgroup$
    – Mickybo Yakari
    Commented Apr 30, 2020 at 6:44
1
$\begingroup$

Well, obviously any sorting algorithm can achieve what you want, since if the entries in the sequence are sorted (under whatever arbitrary linear order you impose) they have the grouping property.

Given $N,$ there are sorting algorithms with complexity $O(N \log N).$ These algorithms make no assumptions about the values they are sorting.

However, you can do better, depending on the relationship of the alphabet size $M$ to list length $N$. In particular, you can map your alphabet to $\{1,2,\ldots,M\}$ and thus assume that the values to be sorted are all nonnegative and bounded by $M.$

In that case, the counting sort algorithm can sort your sequence with time complexity $O(N+M).$ Alternatively, you can use radix sort with complexity $O(w N),$ where $w$ is the number of bits required to store the values you are sorting, so $w=O(\log K).$

Improve this answer
$\endgroup$
1
  • $\begingroup$ The counting sort does not output a sequence of swaps though, does it? $\endgroup$
    – Federico Poloni
    Commented May 1, 2020 at 16:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .