C++ Alexander Bogomolny 的无序排列算法

Alexander Bogomolny 的无序排列 算法生成前 'n' 个自然数。此方法将按字典顺序给出所有排列，这意味着所有生成的排列都以非递减顺序排列。当 'n' 值非常大或输入集非常大时，使用此方法。它不使用递归来避免与递归深度相关的问题。

使用 Alexander Bogomolny 算法的优点

Alexander Bogomolny 的无序排列 算法有以下几个优点：

• 它不使用递归，因此效率很高。
• 它将按字典顺序生成排列。
• 它易于实现和理解。

日常生活应用

此方法在计算机科学、密码学和组合数学中生成排列。此算法还用于生成加密密钥。

Alexander Bogomolny 无序排列算法的实现

输出

说明

• 上述程序演示了 Alexander Bogomolny 的 生成排列的方法。上述程序中使用的变量是 n，即用户作为输入给出的数组大小。声明了一个名为 arr 的数组，并将 1 到 n 的值添加到该数组中。变量 is_sorted 用于检查数组是否按升序排列。
• 上述程序中使用的函数是 nextPermutation，它生成给定排列的下一个字典序排列。swap 函数用于交换任意两个变量，reverse 函数用于反转整个数组。这里，swap 和 reverse 是内置函数。
• 首先，从用户那里获取 n 的值，然后创建一个数组。之后，将 1 到 n 的值添加到该数组中。数组和 n 值作为参数发送到 nextPermutation 函数。此函数将找到最大的索引 'i'，使得 arr[i ] < arr[i+1]。
• 如果未找到索引，则表示是最后一个排列。数组被反转以获得第一个排列。例如，如果最大索引是 'j'，则在 arr[j] > arr[i] 条件为真时，它将 arr[i] 与 arr[j] 交换。此过程重复进行，直到生成所有排列。此函数在 while 循环中调用，直到 is_sorted 函数返回 true。通过这种方式，所有排列都按升序生成。

生成排列的另一种方法

输出

说明

• 此程序使用回溯法生成从 1 到 n 的所有排列。这里，nums 是存储数字的向量，result 是存储所有排列的另一个向量，n 是向量 nums 的大小，start 是递归中的当前索引。
• 最初，从用户那里获取 n 的值作为输入。之后，创建一个向量，其值从 1 到 'n'。接下来，初始化一个空向量并命名为 result。
• 之后，调用 generatePermutations 函数，并以 nums、起始索引和 result 作为参数。当起始索引等于 nums-1 的长度时，此递归函数将终止。循环从 start 迭代到 sum 的长度，并交换 'i' 和 start 的索引。然后再次递归调用该函数。通过这种方式，我们可以在 result 数组中拥有所有排列。