Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to use full permutation, combination, subset". Many people will encounter such a dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Ask for a perfect arrangement?

Full arrangement is all the permutations and combinations of n elements from n elements (all elements).

Looking for a combination?

Combination is all combinations of n elements and m elements (non-permutation).

A subset?

A subset is all subsets of n elements (all possible combinations).

Generally speaking, the numerical number of all permutations is all elements, but the difference is the order of arrangement; the combination is the combination of selecting a fixed number (not looking at the arrangement); the subset is the expansion of the combination, all possible combinations (whether or not the arrangement is considered).

Of course, these three problems are similar but slightly different, and we may come into contact with more full permutations, so you can think of combinatorial and subset problems as an extension of full permutations. And the question may be whether there is a repetition of the characters to be processed. It is also very critical and important to adopt different strategies to remove weight. There may be many methods to solve each problem. The most popular methods in all permutations are neighborhood exchange method and backtracking method, while other combination and subset problems are classical backtracking problems. The most important and basic thing in this article is to master the non-repetitive full arrangement realized by these two methods, and the others are transformed and expanded based on this.

Total permutation problem

Full arrangement, the total number of elements is the largest, the difference is the order of arrangement.

Full permutation of non-repetitive sequences

This question happens to be buckled 46 is the original topic, you can go to a try after learning.

Problem description:

Given a sequence with no repeating numbers, return all possible full permutations.

Example:

Input: [1mage2, 3] output: [1, 2, 2, 3], [1, 2, 1, 3], [2, 3, 1, 1], [3, 1, 1, 2]]

Complete arrangement without repetition by backtracking method

The backtracking algorithm is used to solve the search problem, and full permutation happens to be a search problem, so first review what the backtracking algorithm is:

In fact, the backtracking algorithm is a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the process of search attempt. When it is found that the solution condition is not satisfied, the backtracking algorithm returns and tries another path.

The full permutation can just use the heuristic method to enumerate all the possibilities. A sequence or set of length n. The possibilities of all its permutations and combinations share n! Kind of. The specific exploratory strategies are as follows:

Select the first element from the selected collection (there are n cases) and mark that the element is already in use and can no longer be used.

Recursive to the next layer on the basis of step 1, find an element from the remaining 1 element according to the method of 1, mark it, and continue to recurse downward.

When all elements are tagged, the tagged elements are sequentially collected and stored in the result, and the current layer ends recursively and goes back to the previous layer (while the elements of the current layer tag are cleared). This will be carried out until the end.

If the flow of backtracking from the pseudo-code flow looks something like this:

Recursive function: if all elements of the collection are marked: add temporary storage to the result set otherwise: select one of the unmarked elements in the collection to store in the temporary collection to mark that the element is marked with the next level recursive function (the end of this layer recursion) marks that the element is not used

If the sequence 1 2 3 4 is used to represent a process of such backtracking, this diagram can be used to show:

There are many ideas to use code to achieve, it is necessary to need a List to store temporary results, but for the original collection we also have two processing ideas, the first is to use List to store the collection, remove it and then recursively to the next layer, and then add it to the original location after recursion. Another idea is to use fixed array storage, mark the corresponding position with a boolean array after using the corresponding location, and then restore it after recursion. Because List frequent lookups for insertions and deletions are generally inefficient, we generally use an boolean array to mark whether the location element is used.

The specific implementation code is as follows:

List list;public List permuteUnique (int [] nums) {list=new ArrayList (); / / final result List team=new ArrayList (); / / backtracking process collection element boolean jud [] = new boolean [nums.length]; / / used to mark dfs (jud, nums, team, 0); return list;} private void dfs (boolean [] jud, int [] nums, List team, int index) {int len = nums.length If (index = = len) / / stop {list.add (new ArrayList (team));} elsefor (int I = 0; I

< len; i++) { if (jud[i]) //当前数字被用过 当前即不可用continue;team.add(nums[i]);jud[i]=true;//标记该元素被使用dfs(jud, nums, team, index + 1);jud[i] = false;// 还原team.remove(index);//将结果移除临时集合}} 修改一下输出的结果和上面思维导图也是一致的： 邻里互换法实现无重复全排列 回溯的测试是试探性填充，是对每个位置进行单独考虑赋值。而邻里互换的方法虽然是也是递归实现的，但是他是一种基于交换的策略和思路。而理解起来也是非常简单，邻里互换的思路是从左向右进行考虑。 因为序列是没有重复的，我们开始将数组分成两个部分：暂时确定部分和未确定部分。开始的时候均是未确定部分，我们需要妥善处理的就是未确定部分。在未确定部分的序列中，我们需要让后面未确定的每一位都有机会处在未确定的首位，所以未确定部分的第一个元素就要和每一个依次进行交换(包括自己)，交换完成之后再向下进行递归求解其他的可能性，求解完毕之后要交换回来(还原)再和后面的进行交换。这样当递归进行到最后一层的时候就将数组的值添加到结果集中。如果不理解可以参考下图进行理解：

The implementation code is:

Class Solution {public List permute (int [] nums) {Listlist=new ArrayList (); arrange (nums,0,nums.length-1,list); return list } private void arrange (int [] nums, int start, int end, Listlist) {if (start==end) / / to the last one added to the result {Listlist2=new ArrayList () For (int a:nums) {list2.add (a);} list.add (list2);} for (int itemstartwiti)

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.