嵌套之美

每周挑战 300

穆罕默德·s·安瓦尔 (mohammad s. anwar) 每周都会发出“每周挑战”，让我们所有人都有机会为两周的任务提出解决方案。我的解决方案首先用python编写，然后转换为perl。这对我们所有人来说都是练习编码的好方法。

挑战，我的解决方案

这是第三百次挑战，让我个人感谢穆罕默德代表普华永道团队的每个人每周所做的所有工作。

任务一：美丽的布置

任务

给你一个正整数，$int。

编写一个脚本来返回您可以构建的精美排列的数量。

n 个整数的排列（1 索引）如果对于每个 i (1

1. perm[i] 能被 i 整除
2. i 可以被 perm[i]整除

我的解决方案

对于此任务，我使用 itertool 模块中的排列函数来完成所有排列。

那么只需确定该排列是否满足指定条件即可。如果没有，我将转向下一个排列。如果是，我会向 count 变量加一。

def beautiful_arrangement(n: list) -> str:    count = 0    for p in permutations(range(1, n+1)):        for i in range(n):            if p[i] % (i+1) != 0 and (i+1) % p[i] != 0:                break        else:            count += 1    return count

可能有一种更有效的方法来计算结果，而不涉及暴力。我的代码在处理较大的数字时会变得非常低效。我没有花任何时间调查这个。

示例

$ ./ch-1.py 11$ ./ch-1.py 22$ ./ch-1.py 10700

任务 2：嵌套数组

任务

给你一个整数数组，@ints 长度为 n，包含 [0, n - 1] 范围内数字的排列。

编写一个脚本来构建一个集合，set[i] = ints[i], ints[ints[i]], ints[ints[ints[i]]], ...，遵循以下规则：

1. set[i] 中的第一个元素以元素 ints[i] 的选择开始。
2. set[i] 中的下一个元素应该是 ints[ints[i]]，然后是 ints[ints[ints[i]]]，依此类推。
3. 我们在 set[i] 中出现重复元素之前停止添加。

我的解决方案

这相对简单。我从一个名为longest_set 的变量开始，设置为0。然后迭代每个起始位置并将this_set 列表设置为集合的第一项（即ints[i]）。我不断添加到这个集合，而 ints[this_set[-1]] 没有出现在 this_set 列表中。完成此操作后，我将 this_set 列表的长度与longest_set 值进行比较。如果它更大，我会更新longest_set值。

def nested_array(ints: list) -> int:    longest_set = 0    for start in range(len(ints)):        this_set = [ints[start]]        while ints[this_set[-1]] not in this_set:            this_set.append(ints[this_set[-1]])        if longest_set < len(this_set):            longest_set = len(this_set)    return longest_set

示例

$ ./ch-2.py 5 4 0 3 1 6 24$ ./ch-2.py 0 1 21$ ./ch-2.py 1 2 0 4 5 25