Beautiful arrangements


  • 1
    M

    Lucy has N numbers from 1 to N. Her arrangement of those numbers is called a beautiful arrangement if any of the following is true:

    The number present at the ith position is divisible by i.
    i is divisible by the number present at the ith position.

    For a given N, how many beautiful arrangements are possible?

    Constraints

    1 < N < 20

    Function

    You are given a function arrangement that takes N as its argument and will return the total number of all possible beautiful arrangements.

    Sample Input

    2
    Sample Output

    2
    Explanation

    The number of possible beautiful arrangements for N=2 will be:
    1 2
    2 1

    Consider the arrangement [1, 2] then:

    number present at 1st position (i = 1) is 1, and 1 is divisible by i.
    number present at 2nd position (i = 2) is 2, and 2 is divisible by i.

    Consider the arrangement [2, 1] then:

    number present at 1st position (i = 1) is 2, and 2 is divisible by i.
    number present at 2nd position (i = 2) is 1, and i is divisible by 1.


  • 0

    A naive thought, buckets[i] to store all divisors and multiples of index i,
    then do backtrack to accumulate the number of the beautiful arrangements.

    can be improved in time by memorization, by cost of space.
    for example, use a N-bit integer K to denote the appearance of numbers. and a map
    (K, L)->count
    where count is the number of beautiful arrangements of length L from numbers that appear in K.


  • 0

    I am thinking in a similar solution. Just go over all permutations following the position restrictions. For that you need the list of numbers allowed in each position:

    def generate(N, pos=1, used=None, allowed_numbers=None):
        if not used:
            used = [False]*(N+1)
        if not allowed_numbers:
            allowed_numbers = [[] for _ in range(N+1)]
            for i in range(1, N+1):
                for j in range(1, N+1):
                    if i % j == 0 or j % i == 0:
                        allowed_numbers[i].append(j)
        if pos > N:
            return 1
        ans = 0
        for i in allowed_numbers[pos]:
            if used[i]:
                continue
            used[i] = True
            ans += generate(N, pos+1, used, allowed_numbers)
            used[i] = False
        return ans
    
    print(generate(20))
    

    The trick here is that the number is much smaller than 20!.


  • 0

    I think combinatorics can be applied here and number of arrangements could be computed in linear time with no extra space. For input number N imagine an array of free positions (or cells) [1..N], where each position 1 <= k <= N could be potentially occupied by some number <= k. The task is allocate N numbers in those N positions. Start scanning from left to right. Number 1 can occupy any of N cells, number 2 could potentially be in (N/2) + 1 (1 stands for the very first cell, as 2 is divisible by 1) positions, but given that first cell might have already been taken by number 1, the number of available cells for 2 is N/2. Same logic applies for next numbers up to N.

    public static int count(int n){
            int total = 1;
            for (int i = 0; i < n; ++i){
                int availablePositions = n / (i+1);
                total *= availablePositions;
            }
            return total;
        }
    

  • 0

    @pooh sorry, but I don't follow your math. For example, 18 can be in positions 1, 2, 3, 6, 9 and 18. But 19 can only be in 19 and 1. So going from n=17 to n=18 adds a lot of new available positions but going from n=18 to n=19 not that many.

    You can compare your solution with a pure brute force solution (for smaller numbers of n it will work) and discrepancies will start to appear after n=7.

    I would like to find a o(1) solution. I tried several times to derivate the relationship but so far I failed.


  • 0

    @pbg yes, my approach is wrong, tried to figure out the relationship as well.


  • 0
    I

    Generate permutation with skip

    static int countArrangements(int n,int[] data){
        if(n<=0){
          return 1;
        }
        int count = 0;
        for(int i=0;i<n;++i){
          if(data[i]%n == 0 || n%data[i] ==0){
            swap(data,i,n-1);
            count += countArrangements(n-1,data);
            swap(data,i,n-1);
          }
        }
        return count;
      }
    
      static void swap(int[] data,int i,int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
      }
    
      static int arrangements(int n) {
        int[] data = new int[n];
        for(int i=0;i<n;++i){
          data[i] = i+1;
        }
        return countArrangements(n,data);
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.