Shulou(Shulou.com)05/31 Report--

How to use the GE language to generate an arrangement, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Arithmetic

At present, there are several algorithms commonly used to generate the arrangement of a sequence:

Violence method (Brute Force) insertion method (Insert) dictionary method (Lexicographic) SJT algorithm (Steinhaus-Johnson-Trotter) heap algorithm (Heap)

The following describes the content, implementation, advantages and disadvantages of the algorithm in turn.

Before we introduce these algorithms, let's do some examples and code conventions:

My code implementation uses the Go language and only implements all the permutations of int slices, and it is not difficult for other types to extend themselves. Unless otherwise stated, I assume that there are no repeating elements in the input int, there are repeating elements that can be removed by themselves, and there are individual algorithms that can deal with the problem of repeating elements.

The complete code is placed on Github.

Description by violence method

Violence method is a very direct divide-and-conquer method: Mr. into the arrangement of 1 element, plus the nth element can get the arrangement of n elements. The steps of the algorithm are as follows:

Swap the nth element to the last position in turn to recursively generate the arrangement of the first nmur1 element plus the last element is the arrangement of n elements.

Realize

The algorithm is also very simple to implement. Here we introduce two helper functions, copy and reverse slices, which will be used in the later code:

Func copySlice (nums [] int) [] int {

N: = make ([] int, len (nums), len (nums))

Copy (n, nums)

Return n

}

/ / reverse the [I, j] range of slice nums

Func reverseSlice (nums [] int, I, j int) {

For i

< j { nums[i], nums[j] = nums[j], nums[i] i++ j-- } } 算法代码如下： func BruteForce(nums []int, n int, ans *[][]int) { if n == 1 { *ans = append(*ans, copySlice(nums)) return } n := len(nums) for i := 0; i < n; i++ { nums[i], nums[n-1] = nums[n-1], nums[i] BruteForce(nums, n-1, ans) nums[i], nums[n-1] = nums[n-1], nums[i] } } 作为一个接口，需要做到尽可能简洁，第二个参数初始值就是前一个参数切片的长度。优化接口： func bruteForceHelper(nums []int, n int, ans *[][]int) { // 生成排列逻辑 ... } func BruteForce(nums []int) [][]int{ ans := make([][]int, 0, len(nums)) bruteForceHelper(nums, len(nums), &ans) return ans } 优缺点 优点：逻辑简单直接，易于理解。 缺点：返回的排列数肯定是n!，性能的关键在于系数的大小。由于暴力法的每次循环都需要交换两个位置上的元素，递归结束后又需要再交换回来，在n较大的情况下，性能较差。 插入法描述 插入法顾名思义就是将元素插入到一个序列中所有可能的位置生成新的序列。从 1 个元素开始。例如要生成{1,2,3}的排列： 先从序列 1 开始，插入元素 2，有两个位置可以插入，生成两个序列 12 和 21将 3 插入这两个序列的所有可能位置，生成最终的 6 个序列 1 12 21 123 132 312 213 231 321 实现 实现如下： func insertHelper(nums []int, n int) [][]int { if n == 1 { return [][]int{[]int{nums[0]}} } var ans [][]int for _, subPermutation := range insertHelper(nums, n-1) { // 依次在位置0-n上插入 for i := 0; i nums[i] { i-- } // 全都逆序了，达到最大值 if i == 0 { reverse(nums, 0, len(nums)-1) return false } // 找到比索引i处元素大的元素 j := len(nums) - 1 for nums[j] 132(交换13) ->

312 (Exchange 12)->

321 (Exchange 32)->

231 (Exchange 31)->

two hundred and thirteen

A simple solution is to generate the arrangement of n elements through the arrangement of 1 elements. For example, we now use the arrangement of two elements to generate the arrangement of three elements.

The arrangement of the two elements is only 2: 1 2 and 2 1.

By inserting 3 in all different positions in the arrangement of two elements, we can get the arrangement of three elements.

Insert 3 in different positions of 1 / 2 to get 1 23132 and 31 / 2. Insert 3 in different positions of 2 1 to get 2 13231 and 32 1.

The above is the logic of the insertion method, but the performance of the insertion method is poor due to a large amount of data movement. The SJT algorithm does not require all the permutations of 1 elements to be generated. It records the direction of each element in the arrangement. The steps of the algorithm are as follows:

Find the largest movable element in the sequence. The movability of an element means that its value is greater than the adjacent element it points to. Swap the element with the adjacent elements it points to. Modify the orientation of all elements whose value is greater than that element. Repeat the above steps until there are no movable elements.

Suppose we need to generate all the permutations of sequence 1 2 3 4. First initialize the orientation of all elements from right to left. The first arrangement is the initial sequence:

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.