Beautiful Arrangement

Problem Statement

Suppose you are given a set of integers ranging from 1 to n. Your goal is to find all permutations of this integer set such that the permutation meets a specific criterion to qualify as a "beautiful arrangement". A permutation is only considered beautiful if for every position i in the permutation, at least one of the following conditions is met:

• The integer at the i-th position of the permutation, denoted as perm[i], is divisible by i.
• The position i itself is divisible by the integer perm[i].

The task is to compute the total number of such beautiful arrangements that can be obtained for a given integer n.

Examples

Example 1

Input:

n = 2

Output:

2
**Explanation:**
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1

Example 2

Input:

n = 1

Output:

1

Constraints

• 1 <= n <= 15

Approach and Intuition

The core of solving this problem lies in understanding the properties of divisibility and permutations. Our approach will involve exploring all permutations to count how many meet the beautiful arrangement criteria. Here's how we can intuitively think about solving this:

1. Brute Force with Optimization: We could use a backtracking algorithm which tries to build each permutation step by step.

   • Start by placing each number in each position and check if placing the number in the current position keeps the arrangement beautiful.
   • If the position division property holds (either position divides the number or the number divides the position), continue to the next position. Otherwise, backtrack.

2. Pruning using Constraints:

   • If at any point a condition is violated, we can stop further exploration down that path. This pruning helps in reducing the number of permutations we need to explore.

3. Caching Results (Memoization):

   • For bigger values of n, it might be beneficial to remember results for smaller sub-problems. This can significantly speed up the solving process as it prevents redundant calculations.

4. Using Bit Manipulation:

   • We can represent the permutation as a number in binary format. This will help in quickly checking which elements have been used in the permutation so far.

This problem is a good example of using combinatorial methods coupled with algorithmic optimizations such as backtracking and bit manipulation to handle permutations and divisibility checks efficiently. Given the constraints of n being at most 15, such an approach should be computationally feasible.

Solutions

class Solution {
public:
    int countArrangement(int num) {
        vector<bool> marked(num + 1, false);
        arrange(num, 1, marked);
        return arrangements;
    }
    
private:
    int arrangements = 0;
    void arrange(int num, int position, vector<bool>& marked) {
        if (position > num)
            arrangements++;
        else
            for (int idx = 1; idx <= num; ++idx)
                if (!marked[idx] && (position % idx == 0 || idx % position == 0)) {
                    marked[idx] = true;
                    arrange(num, position + 1, marked);
                    marked[idx] = false;
                }
    }
};