How java traverses all combinations of m to n
This article will explain in detail how java traverses all the combinations of m to n. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.
Example:
* find all the combinations of m and n. * the number of m is 0pm, 1pm, 2m, respectively. * algorithm description: * two combinations are regarded as the same combination if only the order of the elements is different. * the left position is low and the right position is high. * take the first combination according to the natural method (the digits are: 0Power1, respectively), and all the subsequent combinations are changed from the previous combination: * from right to left, find the bit with incremental space and add it by 1, so that all bits higher than that bit are larger than their left neighbor by 1, thus forming a new combination. * if all bits have no incremental space, all combinations have been traversed. * the number of combinations generated by this method: for any combination of int [] c, the number with small subscript must be less than the number with large subscript. *
, /
Public class Combination {
Int n, m
Int [] pre;//previous combination.
Public Combination (int n, int m) {
This.n = n
This.m = m
}
/ * *
* take the next combination. It can avoid returning all combinations at once (huge quantity, waste of resources).
* if return null, all combinations have been taken out.
, /
Public int [] next () {
If (pre = = null) {/ / take the first combination, and all subsequent combinations are changed from the previous combination.
Pre = new int [n]
For (int I = 0; I
< pre.length; i++) { pre = i; } int[] ret = new int[n]; System.arraycopy(pre, 0, ret, 0, n); return ret; } int ni = n - 1, maxNi = m - 1; while (pre[ni] + 1 >MaxNi) {/ / from right to left, find the bit with incremental space.
Ni--
MaxNi--
If (ni < 0)
If return null;// is not found, it means that all the combinations have been taken.
}
Preni + +
While (+ + ni < n) {
Pre [ni] = pre [ni-1] + 1
}
Int [] ret = new int [n]
System.arraycopy (pre, 0, ret, 0, n)
Return ret
}
}
This is the end of this article on "how java traverses all the combinations of m and n". I hope the above content can be helpful to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.
