3-liner DFS with "Trie" perspective (detailed explanation with picture illustration)


  • 1

    The basic idea is to try each value in range [1, N] at every possible position 1, 2, .. N. However, if simply brute force to go though all possible N! permutations, you will get TLE since 15! is in huge magnitude of 10^12.

    So the key is to skip a group of permutations as early as possible if they cannot form a beautiful arrangement at all.

    Trie "Construction": (no need to actually contruct the trie)
    Imagine all permutations form a trie

    • The trie is rooted at a dummy level-0 node which has N level-1 child nodes: 1, 2, ...N;
    • Each level-L (1<=L<=N) node has exactly N-L child nodes;
    • Each node's value is distinct from any of its ancestor's value (i.e., permutation).
      0_1487889317409_Trie.JPG

    Key Properties:

    1. Each path from root to a leaf forms a permutation of [1, N].
    2. A path is a beautiful arrangement iff level-L node value i satisfies condition
      • (i%L)*(L%i) == 0 for all nodes on the path.

    Algorithm:
    The algorithm is simply to pre-order traverse the trie and:

    1. Skip a sub-tree if condition (i%L)*(L%i) == 0 is violated at any point.
    2. Increment final count count whenever reaches a leaf (i.e., level-N).

    Note: since N <= 15, int used is enough to be used as a bit array to record if value i (i.e., i-bit position of used) in [1, N] has been used in permutation.

        int count = 0; // count of beautiful arrangement
        
        int countArrangement(int N, int used = 0, int L = 1) {
            for (int i = 1; max(i,L) <= N ; i++)
              if ((used & 1<<i)+(i%L)*(L%i) == 0) countArrangement(N, used^(1<<i), L+1);
            return count += (L > N);
        }
    

    Here is an improved version inspired by @dreamchase to eliminate unnecessary index check in the loop (which speeds up frm ~200ms to ~60ms):

        int nums[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; // natural ascending order
        
        int countArrangement(int N, int s = 1) { // s: start index to swap
          for (int i = s; i <= N; i++) 
            if ((nums[i]%s)*(s%nums[i]) == 0)
              swap(nums[i],nums[s]), countArrangement(N,s+1), swap(nums[i],nums[s]);
          return nums[0] += (s>N); // nums[0] used as place holder for count
        }
    

Log in to reply
 

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