1
$\begingroup$

Given the array of frequencies, say $A = \{a_1,a_2, \dots, a_n\}$, $0 < a_i \in \mathbb{N}$. We can create sequence which contains numbers from $1$ to $n$ such that each number's $i$ appears $a_i$ times in sequence, and there is no adjacent element are alike.

We would like the algorithm to generate minimum sequence in lexicographic order.

For example, if we have $A = \{2,1,1,3\}$. It means that we have sequence which has 2's $1$, 1's 2, 1's 3 and 3's 4. Then we can create some sequence as below.

$$4,1,4,3,4,2,1$$ $$4,1,4,1,4,2,3$$ $$4,1,4,2,4,3,1$$ $$4,2,4,1,4,3,1$$ etc.

But the minimum sequence in lexicographic order we have to find is $$1,2,4,1,4,3,4.$$

My observation.

  1. If the most frequency is more than (total number plus 1)/2 (sum of $a_i$) then there is no solution (trivial).
  2. If the most frequency is equal to total number/2 (even) or (total number plus 1)/2 then we can construct solution by fill all element of most frequency by index $0,2,\dots$ then fill out the rest by minimum order. For example, $$4,1,4,2,4,3,4.$$

I know we can generate one of such sequence but it is not minimum as expectation.

$\endgroup$

1 Answer 1

2
$\begingroup$

Lemma: Given $(a_1,\dots,a_n)\in \mathbb N^n$, there exists a sequence of integers where $i$ appears $a_i$ times for all $i\in \{1,\dots,n\}$ and adjacent entries are different if and only if $a_i\le \tfrac12(1+ \sum_{i=1}^n a_i)$ for all $i\in \{1,\dots,n\}$.

You stated the "only if" part in your question. The "if" part requires constructing a valid sequence for a given list of frequencies, for which you can see my answer to another question.

This lemma implies the following simple algorithm to find the lexicographically first valid sequence, provided $(a_1,\dots,a_n)$ satisfied the conditions of the lemma.

Start with an "urn" filled with numbered balls, where there are $a_i$ balls labeled $i$ times in the pool for each $i\in \{1,\dots,n\}$. We will build the sequence one entry at a time from left to right. At each step of the process, you remove the smallest numbered ball from the urn which is different from the last ball you placed, and place it in the next spot. The only exception to this rule is if there are currently an odd number of balls in the urn, and one number is on a strict majority of balls. In that case, you must remove that number.

Here is an example with the frequency list $(2,3,2)$. Imagine a basket with eight balls in it, where two are labeled "1", three are labeled "2", and two are labeled "3".

  1. The smallest ball in the basket is "1", so remove one of the "1" balls, and place it at the beginning. The current sequence is [1]. The remaining balls are [1,2,2,2,3,3].

  2. The smallest ball remaining in the basket is "1", but we cannot grab "1" since no two ones can be adjacent. The second smallest is "2", so we grab that. The current sequence is [1,2]. The remaining balls are [1,2,2,3,3].

  3. The smallest ball remaining in the basket is "1", so we grab that. The current sequence is [1,2,1]. The remaining balls are [2,2,3,3].

  4. The smallest ball remaining in the basket is "2", so we grab that. The current sequence is [1,2,1,2]. The remaining balls are [2,3,3].

  5. Since there are three balls remaining, and more than half of those balls are "3", we invoke the exception, and grab a ball labeled "3". The current sequence is [1,2,1,2,3]. The remaining balls are [2,3].

  6. The smallest ball remaining in the basket is "2", so we grab that. The current sequence is [1,2,1,2,3,2]. The remaining balls are [3].

  7. The final ball in the basket is "3", so we grab that. The completed sequence is [1,2,1,2,3,2,3].

$\endgroup$
3
  • $\begingroup$ Sorry. Can you please clarify the step in your algorithm? $\endgroup$
    – GAVD
    Apr 30, 2022 at 17:48
  • $\begingroup$ @GAVD I added a fully explained example, let me know if anything else is unclear. $\endgroup$ May 1, 2022 at 15:53
  • $\begingroup$ many thank for very detail explanation. $\endgroup$
    – GAVD
    Jun 15, 2022 at 8:13

You must log in to answer this question.

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