Simple greedy alternation
IntuitionIt is pretty obvious that each alternating permutation has numbers of same parity at odd positions, and at even positions numbers are also of same pari
# Intuition
It is pretty obvious that each alternating permutation has numbers of same parity at odd positions, and at even positions numbers are also of same parity. So, it can be constructed from two transpositions: one transposition of even numbers from range $$[1, n]$$, another of odd numbers from the same range.

Moreover, if $$n$$ is odd, alternating permutation always starts with odd number. If $$n$$ is even, it may start with any number.

Therefore, number of alternating permutations is:
- $$2*m!*m!$$ in case $$n == 2*m$$
- $$m!*(m + 1)!$$ in case $$n == 2*m + 1$$

The bigger $$n$$, the more alternating permutations.

Ok, let's calculate how many permutations of length $$n$$ which start with some number $$p$$.
- in case $$n == 2*m$$, there are $$m!*(m - 1)!$$ permutations starting with $$p$$, i.e. the same as number of alternating permutations of length $$n - 1$$
- in case $$n == 2*m + 1$$, $$p$$ must be odd, and the number of alternating permutations starting with $$p$$ is equal to $$m!*m!$$, i.e. half of number of permutations of length $$n - 1$$

This is not a coincidence, given some prefix of alternating permutation, the rest can be constructed from alternating permutation of length $$n - length(prefix)$$.

# Approach
Let's calculate the number of alternating permutations of length $$m$$ for every $$1 <= m <= n$$. Well, obviously, we cannot do so for big $$m$$, e.g. for $$m=50$$ the number has 24 zeroes at the end, i.e. it is divisible by $$10^{24}$$ which exceeds `int64`. But we can calculate numbers till the first one which is greater than $$k$$.

Once we have these numbers, we can easily construct the resulting permutation number by number since we can estimate number of permutations starting with already built prefix.

On every step we know the parity of the next number in the permutation, except of the first number in permutation of even length. Additionally, we know which number from range $$[1, n]$$ were already used. So the calculate the order number of the next elements, i.e. we calculate $$m$$, so we skip $$(m - 1)$$ multiplied by number of suffix permutations by taking $$m$$-th number of required parity from not used numbers.

# Complexity
- Time complexity: $$O(n^2)$$
- Space complexity: $$O(n)$$

# Code
```golang []
func permute(n int, k int64) []int {
    cnt := make([]int64, 2, n + 1)
    cnt[0] = 1
    cnt[1] = 1
    for i := 2; i <= n && cnt[i - 1] <= k; i++ {
        if i & 1 == 1 {
            cnt = append(cnt, cnt[i - 1] / 2 * int64(i + 1) / 2)
        } else {
            cnt = append(cnt, cnt[i - 1] * int64(i))
        }
    }
    if len(cnt) == n + 1 && cnt[n] < k {
        return nil
    }
    res := make([]int, n)
    v := make([]bool, n)
    i, p := 0, 0
    k--
    if n & 1 == 0 {
        m := int64(1)
        if len(cnt) >= n {
            m = k / cnt[n - 1] + 1
            k %= cnt[n - 1]
        }
        res[0] = int(m)
        v[m - 1] = true
        p = int(m & 1)
        i++
    }
    for ; i < n - 1; i++ {
        m := int64(1)
        if len(cnt) >= n - i {
            if (n - i) & 1 == 1 {
                m = 2 * k / cnt[n - 1 - i] + 1
                k %= cnt[n - 1 - i] / 2
            } else {
                m = k / cnt[n - 1 - i] + 1
                k %= cnt[n - 1 - i]
            }
        }
        for j := p; j < n; j += 2 {
            if !v[j] {
                m--
                if m == 0 {
                    res[i] = j + 1
                    v[j] = true
                    break
                }
            }
        }
        p ^= 1
    }
    for j := range v {
        if !v[j] {
            res[n - 1] = j + 1
        }
    }
    return res
}
```
['Greedy', 'Combinatorics', 'Go']