题目描述补充

题目：美丽的排列

给定一个正整数 n，要求生成所有长度为 n 的排列，并找出其中满足以下条件的“美丽排列”：

• 在这个排列中，对于任意 i < j < k，如果 arr[i] < arr[j] 且 arr[j] > arr[k]，则称这种排列为“美丽排列”。

换句话说，一个排列是“美丽”的，如果它不存在长度为3的递减子序列 arr[i] > arr[j] > arr[k]，其中 i < j < k。

示例

假设 n = 3，则所有可能的排列为：

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

其中，[1, 2, 3] 和 [3, 2, 1] 是“美丽排列”，因为它们都不包含长度为3的递减子序列。

PHP 示例代码

<?php
function generatePermutations($n) {
    $result = [];
    backtrack([], $n, $result);
    return $result;
}

function backtrack($current, $n, &$result) {
    if (count($current) == $n) {
        $result[] = $current;
        return;
    }
    for ($i = 1; $i <= $n; $i++) {
        if (!in_array($i, $current)) {
            $current[] = $i;
            backtrack($current, $n, $result);
            array_pop($current);
        }
    }
}

function isBeautiful($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 2; $i++) {
        for ($j = $i + 1; $j < $n - 1; $j++) {
            if ($arr[$i] < $arr[$j]) {
                for ($k = $j + 1; $k < $n; $k++) {
                    if ($arr[$j] > $arr[$k]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

function findBeautifulPermutations($n) {
    $permutations = generatePermutations($n);
    $beautiful = [];
    foreach ($permutations as $perm) {
        if (isBeautiful($perm)) {
            $beautiful[] = $perm;
        }
    }
    return $beautiful;
}

// 示例
$n = 3;
$beautifulPermutations = findBeautifulPermutations($n);
print_r($beautifulPermutations);
?>

Python 示例代码

def generate_permutations(n):
    def backtrack(current, n):
        if len(current) == n:
            result.append(current[:])
        else:
            for i in range(1, n + 1):
                if i not in current:
                    current.append(i)
                    backtrack(current, n)
                    current.pop()
    
    result = []
    backtrack([], n)
    return result

def is_beautiful(arr):
    n = len(arr)
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            if arr[i] < arr[j]:
                for k in range(j + 1, n):
                    if arr[j] > arr[k]:
                        return False
    return True

def find_beautiful_permutations(n):
    permutations = generate_permutations(n)
    return [p for p in permutations if is_beautiful(p)]

# 示例
n = 3
beautiful_permutations = find_beautiful_permutations(n)
print(beautiful_permutations)

JavaScript 示例代码

function generatePermutations(n) {
    const result = [];
    function backtrack(current, remaining) {
        if (remaining.length === 0) {
            result.push(current.slice());
            return;
        }
        for (let i = 0; i < remaining.length; i++) {
            current.push(remaining[i]);
            backtrack(current, remaining.slice(0, i).concat(remaining.slice(i + 1)));
            current.pop();
        }
    }
    backtrack([], Array.from({length: n}, (_, i) => i + 1));
    return result;
}

function isBeautiful(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            if (arr[i] < arr[j]) {
                for (let k = j + 1; k < n; k++) {
                    if (arr[j] > arr[k]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

function findBeautifulPermutations(n) {
    const permutations = generatePermutations(n);
    return permutations.filter(p => isBeautiful(p));
}

// 示例
const n = 3;
const beautifulPermutations = findBeautifulPermutations(n);
console.log(beautifulPermutations);

码小课网站中有更多相关内容分享给大家学习，包含但不限于算法题解、数据结构、面试技巧等，帮助大家提升编程技能。