Find an alternating permutation of a list

Question

Given a list, I want to generate a permutation of the list that is alternating: the first element must be greater than the second, which must be lower than the third, which must be greater than the second, etc.

I have tried the following code:

li=[10,2,11,13,21,12,6,7,8,9]
#  condition = a1>a2<a3>a4.....>an

li = sorted(li)
print(li)

for i in range(len(li)-1):
  li[i], li[i+1] = li[i+1], li[i]
  print(li[i],li[i+1])
print(li)

But it doesn't satisfy the condition. It gives the Output as below- 👇

'[2, 6, 7, 8, 9, 10, 11, 12, 13, 21]'
'[6, 7, 8, 9, 10, 11, 12, 13, 21, 2]'

Answer 1

This problem can be solved rather efficiently with only a few steps:

>>> li=[10,2,11,13,21,12,6,7,8,9]
>>> # sort from smallest to largest
>>> li.sort()
>>> result = [None] * len(li)
>>> # use first/smallest half for a2, a4, a6, ...
>>> result[1::2] = li[:len(li)//2]
>>> # use second/largest half for a1, a3, a5, ...
>>> result[::2] = li[len(li)//2:]
>>> result
[10, 2, 11, 6, 12, 7, 13, 8, 21, 9]

The [::2] and [1::2] are a "slice from 0/1 with step 2", i.e. the odd/even positions.

---

Now why does this work?

Let's look at a small case first:

a1 > a2 < a3 > a4

We can rewrite this to separate criteria for each element:

• a1 > a2
• a3 > a2 and a3 > a4
• a2 < a1 and a2 < a3
• a4 < a3

These are only between each odd element and several even elements, and likewise between each even element and several odd elements. There are no relations between odd elements and no relations between even elements. This means there are several possible solutions and we can pick the one that works easiest:
Instead of worrying about the many triples of elements – like a2 a3 a4 – and how they relate to each other, it would be simpler if we could look at the two even/odd element groups at once.

We can do this by extending our relation between each odd element to all even elements and vice versa:

• a1 > a2 and a1 > a4
• a3 > a2 and a3 > a4
• a2 < a1 and a2 < a3
• a4 < a1 and a4 < a3

This still satisfies the initial criteria, it just excludes some possible solution.
Now, if we compare the rules for all odd elements, we can see that they are exactly the same and likewise for all even elements:

• ai > a2 and ai > a4 for all i in {1, 3}
• aj < a1 and aj < a3 for all i in {2, 4}

In fact, both are just a single rule for all elements:

• ai > aj for all i in {1, 3} for all i in {2, 4}

At this point, it should be obvious¹ that this does not just apply to the case of 4 elements but in fact to every number of elements:

• ai > aj for all i in {1, 3, ...} for all i in {2, 4, ...}

In words, this means a possible solution is to have all odd elements larger than all even elements. This can be achieved by splitting the sorted input to get the largest/smallest elements, then assigning each of these groups to the even/odd positions.

---

¹The proof is left as an exercise to the reader.