Start learning free

LESSON 269 OF 347 · BACKTRACKING

Generate Valley Permutations in C#: Bitmasks and Sorting

Practice O(n!) Read the full explanation

Given a non-negative integer n, return all the valley permutations of length n.

A valley permutation is defined as a permutation that is a concatenation of two parts: a monotonically decreasing sequence and then a monotonically increasing sequence.

E.g. valley permutations follow this format: [p[0] < p[1] < p[2] < ... < p[k] > p[k+1] > p[k + 2] > ... > p[n]].


Example:

Input: n = 4

Output:[
    [1, 2, 3, 4],
    [2, 1, 3, 4],
    [3, 1, 2, 4],
    [3, 2, 1, 4],
    [4, 1, 2, 3],
    [4, 2, 1, 3],
    [4, 3, 1, 2],
    [4, 3, 2, 1]
]

Explanation:
Permutations suchs as [1, 4, 2, 3] are not valley because 1 < 4 > 2 < 3

Notes: n <= 10


STEP 1 OF 9
    Ctrl + Enter to check

    C# · BACKTRACKING

    Generate Valley Permutations in C#, explained

    Problem overview

    The method GenerateValleyPermutations receives a non-negative integer n and must return every valley permutation of the numbers 1 to n, as a List<int[]>. A valley permutation goes down and then goes up: its values decrease to a lowest point and increase afterwards, like the profile of a valley. The decreasing part or the increasing part may be empty.

    For n = 4 there are eight of them:

    [1, 2, 3, 4]
[2, 1, 3, 4]
[3, 1, 2, 4]
[3, 2, 1, 4]
[4, 1, 2, 3]
[4, 2, 1, 3]
[4, 3, 1, 2]
[4, 3, 2, 1]

    A permutation such as [1, 4, 2, 3] is not a valley, because it goes up, then down, then up again. The lesson limits n to 10.

    Approach: decide a side for every value except 1

    The shape of a valley fixes a lot. The smallest value, 1, must sit at the bottom, because values only decrease towards it and increase after it. Every other value from 2 to n is either to the left of 1, in the decreasing part, or to the right of 1, in the increasing part. Once each value has a side, the order is forced: the left side must be sorted from largest to smallest, and the right side from smallest to largest.

    So a valley permutation is completely described by one binary choice for each of the n - 1 values 2 to n. That means there are exactly 2^(n - 1) of them, which for the limit n = 10 is 512.

    A counter does the enumeration neatly. Count mask from 0 to 2^(n - 1) - 1. Every integer in that range, written in binary, is a different pattern of n - 1 bits, so the loop visits every combination of choices exactly once. Bit i of the mask decides the side of the value i + 2: a 1 sends it left and a 0 sends it right.

    Take n = 4 and mask = 6, which is 110 in binary. Bit 0 is 0, so the value 2 goes right. Bits 1 and 2 are 1, so the values 3 and 4 go left. The left side, sorted from large to small, is 4, 3, then comes 1, then the right side 2. The permutation is [4, 3, 1, 2].

    Step by step

    1. Create the result list. It is a List<int[]> named result, holding one array per permutation.
    2. Loop over the masks from 0 up to but not including 1 << (n - 1). Shifting 1 left by k places gives 2^k.
    3. Create two fresh lists for each mask, left and right. Declaring them inside the loop gives every mask empty lists.
    4. Loop over the bits, with i from 0 to n - 2: one iteration for each value from 2 to n.
    5. Compute the value that this bit controls, val = i + 2. The offset is 2 because 1 needs no bit.
    6. Read the bit. If ((mask >> i) & 1) == 1, add val to left; otherwise add it to right. The shift moves bit i to the lowest place, and & 1 keeps only that bit.
    7. Order the sides. Sort left in descending order and right in ascending order.
    8. Assemble the permutation. Create an int[] of size n with an index idx at 0. Copy left into it, then store 1, then copy right, advancing idx after each write. Add the array to result.
    9. Return result after the outer loop has finished.

    The solution in C#

    class Solution {
    public List<int[]> GenerateValleyPermutations(int n) {
        List<int[]> result = new List<int[]>();
        for (int mask = 0; mask < (1 << (n - 1)); ++mask) {
            List<int> left = new List<int>();
            List<int> right = new List<int>();
            for (int i = 0; i < n - 1; ++i) {
                int val = i + 2;
                if (((mask >> i) & 1) == 1) {
                    left.Add(val);
                } else {
                    right.Add(val);
                }
            }
            left.Sort((a, b) => b - a);
            right.Sort();
            int[] perm = new int[n];
            int idx = 0;
            foreach (int v in left) {
                perm[idx++] = v;
            }
            perm[idx++] = 1;
            foreach (int v in right) {
                perm[idx++] = v;
            }
            result.Add(perm);
        }
        return result;
    }
}

    The C# details worth a closer look:

    • Bit operators. << and >> shift the bits of an int, and & keeps the bits set in both operands. In (mask >> i) & 1, bit i of mask ends up as 0 or 1. For mask = 5 (binary 101), bits 0, 1 and 2 read 1, 0 and 1.
    • The parentheses are required. In C#, == binds tighter than &. Without the parentheses, (mask >> i) & 1 == 1 would try to apply & to an int and a bool, which is a compile error. An if condition must also be a bool, so a bare & 1 can't stand in for == 1, unlike in C.
    • Sorting with a lambda. List<T>.Sort accepts a comparison that returns a negative number, zero or a positive number. (a, b) => b - a is negative when a is larger, which puts larger values first. The numbers are small here, so the subtraction can't overflow. Sort() without arguments sorts ascending.
    • Post-increment as an index. perm[idx++] = v writes at the current idx and then adds one to it.
    • A fresh array each time. perm is created inside the loop, so each entry of result is its own array and later iterations don't overwrite earlier ones.
    • Two loops, same name. Both foreach loops declare v. That is legal because the first loop's scope ends before the second begins.

    Complexity

    Time: O(2^n * n log n). The outer loop runs 2^(n - 1) times. Each iteration sorts lists totalling at most n - 1 values and then fills an array of size n, which costs at most O(n log n). The sorts are not strictly needed, because the values were added in increasing order, so right is already ascending and left only needs reversing. They make the intended order explicit and cost little for n up to 10.

    Space: O(2^n * n), because the result holds 2^(n - 1) arrays of n numbers each. Apart from the output, the working lists need only O(n).

    Edge cases and common mistakes

    • n = 1. The loop runs once with an empty mask, both sides are empty, and the result is the single permutation [1].
    • n = 0. The shift count n - 1 is -1, and C# uses only the low five bits of a shift count for an int, so 1 << -1 becomes 1 << 31, which is a negative number. The loop never runs and the method returns an empty list.
    • Counting results. The answer has 2^(n - 1) arrays. If your count is different, a mask or a bit position is wrong.
    • Treating 1 as a choice. The value 1 is always the bottom of the valley. Giving it a bit would produce duplicates.
    • Reusing the lists. Creating left and right outside the outer loop would carry the values of one mask into the next.
    • Wrong side order. The left side must decrease towards 1, so it is sorted in descending order. Sorting it ascending produces mountains and other shapes instead of valleys.
    • Using i as the value. The loop variable starts at 0, but the first value is 2, hence val = i + 2.

    Testing

    • n = 4 gives the eight arrays listed above, in the same order.
    • n = 1 gives one array, [1].
    • n = 3 gives [1, 2, 3], [2, 1, 3], [3, 1, 2] and [3, 2, 1].
    • n = 10 gives 512 arrays.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free