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

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.

The above is the detailed content of My Python Language Solution to Task Beautiful Arrangement from The Weekly Challenge. For more information, please follow other related articles on the PHP Chinese website!