My Python Language Solution to Task 1: Beautiful Arrangement from The Weekly Challenge 300

1. Introduction

The Weekly Challenge, organized by Mohammad S. Anwar, is a friendly competition in which developers compete by solving a pair of tasks. It encourages participation from developers of all languages and levels through learning, sharing, and having fun.

Task 1: Beautiful Arrangement from The Weekly Challenge invites developers to find the number of beautifully arranged permutations from among all permutations generated from a positive integer.

In this post I discuss, and present my solution to, Task 1: Beautiful Arrangement, and end a brief conclusion.

The Weekly Challenge 300 deadline is Sunday, December 23, 2024 at 23:59 (UK Time). To avoid bias, consider reading this post after competing.

2. Task 1: Beautiful Arrangement

You are given a positive integer, $int.

Write a script to return the number of beautiful arrangements that you can construct from $int.

A permutation of n integers, 1-indexed, is considered a beautiful arrangement if for every i (1 <= i <= n) either of the following is true:

1. permutation[i] is divisible by i
2. i is divisible by permutation[i]

The Weekly Challenge 300, Task 1: Beautiful Arrangement

Examples 1 and 2 present the expected outputs from given inputs.

Example 1

Input: $n = 2
Output: 2

For n = 2 and with i integers such that (1 <= i <= n) there are two permutations (1, 2) and (2, 1). Output: 2 because both meet the beautiful arrangement requirements.

The permutation (1, 2) is a beautiful arrangement because all of its elements match the first condition:

• At i = 1, permutation[1] = 1 satisfies the first condition, since one is divisible by one.
• At i = 2, permutation[2] = 2 satisfies the first conditions, since two is divisible by two.

The permutation(2, 1) is also a beautiful arrangement because all of its elements match either the first or second condition:

• At i = 1, permutation[1] = 2 satisfies the first condition, since two is divisible by one.
• At i = 2, permutation[2] = 1 satisfies the second condition, since two is divisible by one.

Example 2

Input: $n = 1
Output: 1

Example 3

Input: $n = 10
Output: 700

3. My solution to Task 1

from itertools import permutations

def generate_permutations(n)
    iterable = list(range(1, n + 1))
    return permutations(iterable)

def count_beautiful_arrangements(perms):
    num_beautiful_arr = 0
    for perm in perms:
        is_beautiful_arr = True
        for value_index, value in enumerate(perm):
            if value % (value_index + 1) == 0:
                continue
            elif (value_index + 1) % value == 0:
                continue
            else:
                is_beautiful_arr = False
                break
        if is_beautiful_arr == True:
            num_beautiful_arr += 1
    return num_beautiful_arr

My inelegant and unsophisticated solution utilizes two functions generate_permutations and count_beautiful_arrangements.

generate_permutations returns, for the parameter n, all permutations for the set where 1 <= i <= n.

• iterable = list(range(1, n + 1)) generates a list of integers where 1 <= i <= n.
• permutations(iterable), imported from the itertools module, generates all permutations of iterable.

count_beautiful_permutations returns, for the permutations iterable perms parameter, the total number of permutations in perms that match the beautiful arrangement conditions.

• The outer loop for perm in... iterates through each permutation.
• It starts with the assumption that perm is a beautiful arrangement (is_beautiful_arr = True).
  • The inner loop for value_index, value in... checks if each element of perm matches either condition 1 or condition 2.
    • If all elements match either condition, perm is counted as a beautiful arrangement.
    • Otherwise, if any element matches neither condition 1 nor condition 2, then is_beautiful_arr is set to False, the loop breaks early and perm is not counted as a beautiful arrangement.

4. Conclusion

In this post I discussed Task 1: Beautiful Arrangement and I presented my solution. My 'inelegant and unsophisticated' solution works, but it has considerable room for improvement.