从数组 (Java) 中获取大小为 n 的所有组合的算法?
Algorithm to get all the combinations of size n from an array (Java)?
现在我正在尝试编写一个函数,它接受一个数组和一个整数 n,并给出每个大小 n 组合的列表(因此是一个 int 数组列表)。我可以使用 n 个嵌套循环来编写它,但这只适用于特定大小的子集。我无法弄清楚如何将它概括为适用于任何规模的组合。我想我需要使用递归?
这是 3 个元素的所有组合的代码,我需要一个适用于任意数量元素的算法。
import java.util.List;
import java.util.ArrayList;
public class combinatorics{
public static void main(String[] args) {
List<int[]> list = new ArrayList<int[]>();
int[] arr = {1,2,3,4,5};
combinations3(arr,list);
listToString(list);
}
static void combinations3(int[] arr, List<int[]> list){
for(int i = 0; i<arr.length-2; i++)
for(int j = i+1; j<arr.length-1; j++)
for(int k = j+1; k<arr.length; k++)
list.add(new int[]{arr[i],arr[j],arr[k]});
}
private static void listToString(List<int[]> list){
for(int i = 0; i<list.size(); i++){ //iterate through list
for(int j : list.get(i)){ //iterate through array
System.out.printf("%d ",j);
}
System.out.print("\n");
}
}
}
你绝对可以通过迭代来做到这一点。
这是一个解决方案,它计算我们应该创建多少个数组,然后使用数学构建它们以计算源数组中的哪一项应该放在什么地方:
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
int[] current = new int[n];
// Calculate the correct item for each position in the array
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
list.add(current);
}
}
更新:
这是一个优化版本,可以显着减少对 Math.pow
的调用次数
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
list.add(new int[n]);
}
// Fill up the arrays
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
for(int i = 0; i < numArrays; i++) {
int[] current = list.get(i);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
}
}
如果我对你的问题的理解正确,this 文章似乎指出了你正在尝试做的事情。
引用文章:
Method 1 (Fix Elements and Recur)
We create a temporary array ‘data[]’ which stores all outputs one by
one. The idea is to start from first index (index = 0) in data[], one
by one fix elements at this index and recur for remaining indexes. Let
the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index
0 in data[], then recur for remaining indexes, then we fix 2 at index
0 and recur. Finally, we fix 3 and recur for remaining indexes. When
number of elements in data[] becomes equal to r (size of a
combination), we print data[].
Method 2 (Include and Exclude every element)
Like the above method, We create a temporary array data[]. The idea
here is similar to Subset Sum Problem. We one by one consider every
element of input array, and recur for two cases:
- The element is included in current combination (We put the element in data[] and increment next available index in data[])
- The element is excluded in current combination (We do not put the element and do not change index)
When number of elements in data[] become equal to r (size of a
combination), we print it.
这是一个经过充分研究的生成所有 k 子集的问题,或 k-combinations,无需递归即可轻松完成。
这个想法是让大小为 k
的数组保持输入数组中元素的 索引 的序列(它们是从 0
到 n - 1
) 按升序排列。 (子集然后可以通过从初始数组中获取这些索引的项目来创建。)所以我们需要生成所有这样的索引序列。
第一个索引序列将是[0, 1, 2, ... , k - 1]
,在第二步切换到[0, 1, 2,..., k]
,然后是[0, 1, 2, ... k + 1]
等等。最后可能的序列将是 [n - k, n - k + 1, ..., n - 1]
.
在每一步中,算法都会寻找最接近可以递增的最终项目,将其递增并填充该项目的项目。
为了说明,请考虑 n = 7
和 k = 3
。第一个索引序列是 [0, 1, 2]
,然后是 [0, 1, 3]
等等......在某个时候我们有 [0, 5, 6]
:
[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements
next iteration:
[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"
因此,[0, 5, 6]
之后是 [1, 2, 3]
,然后是 [1, 2, 4]
等等
代码:
int[] input = {10, 20, 30, 40, 50}; // input array
int k = 3; // sequence length
List<int[]> subsets = new ArrayList<>();
int[] s = new int[k]; // here we'll keep indices
// pointing to elements in input array
if (k <= input.length) {
// first index sequence: 0, 1, 2, ...
for (int i = 0; (s[i] = i) < k - 1; i++);
subsets.add(getSubset(input, s));
for(;;) {
int i;
// find position of item that can be incremented
for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--);
if (i < 0) {
break;
}
s[i]++; // increment this item
for (++i; i < k; i++) { // fill up remaining items
s[i] = s[i - 1] + 1;
}
subsets.add(getSubset(input, s));
}
}
// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
int[] result = new int[subset.length];
for (int i = 0; i < subset.length; i++)
result[i] = input[subset[i]];
return result;
}
现在我正在尝试编写一个函数,它接受一个数组和一个整数 n,并给出每个大小 n 组合的列表(因此是一个 int 数组列表)。我可以使用 n 个嵌套循环来编写它,但这只适用于特定大小的子集。我无法弄清楚如何将它概括为适用于任何规模的组合。我想我需要使用递归?
这是 3 个元素的所有组合的代码,我需要一个适用于任意数量元素的算法。
import java.util.List;
import java.util.ArrayList;
public class combinatorics{
public static void main(String[] args) {
List<int[]> list = new ArrayList<int[]>();
int[] arr = {1,2,3,4,5};
combinations3(arr,list);
listToString(list);
}
static void combinations3(int[] arr, List<int[]> list){
for(int i = 0; i<arr.length-2; i++)
for(int j = i+1; j<arr.length-1; j++)
for(int k = j+1; k<arr.length; k++)
list.add(new int[]{arr[i],arr[j],arr[k]});
}
private static void listToString(List<int[]> list){
for(int i = 0; i<list.size(); i++){ //iterate through list
for(int j : list.get(i)){ //iterate through array
System.out.printf("%d ",j);
}
System.out.print("\n");
}
}
}
你绝对可以通过迭代来做到这一点。
这是一个解决方案,它计算我们应该创建多少个数组,然后使用数学构建它们以计算源数组中的哪一项应该放在什么地方:
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
int[] current = new int[n];
// Calculate the correct item for each position in the array
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
list.add(current);
}
}
更新:
这是一个优化版本,可以显着减少对 Math.pow
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
list.add(new int[n]);
}
// Fill up the arrays
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
for(int i = 0; i < numArrays; i++) {
int[] current = list.get(i);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
}
}
如果我对你的问题的理解正确,this 文章似乎指出了你正在尝试做的事情。
引用文章:
Method 1 (Fix Elements and Recur)
We create a temporary array ‘data[]’ which stores all outputs one by one. The idea is to start from first index (index = 0) in data[], one by one fix elements at this index and recur for remaining indexes. Let the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index 0 in data[], then recur for remaining indexes, then we fix 2 at index 0 and recur. Finally, we fix 3 and recur for remaining indexes. When number of elements in data[] becomes equal to r (size of a combination), we print data[].
Method 2 (Include and Exclude every element)
Like the above method, We create a temporary array data[]. The idea here is similar to Subset Sum Problem. We one by one consider every element of input array, and recur for two cases:
- The element is included in current combination (We put the element in data[] and increment next available index in data[])
- The element is excluded in current combination (We do not put the element and do not change index)
When number of elements in data[] become equal to r (size of a combination), we print it.
这是一个经过充分研究的生成所有 k 子集的问题,或 k-combinations,无需递归即可轻松完成。
这个想法是让大小为 k
的数组保持输入数组中元素的 索引 的序列(它们是从 0
到 n - 1
) 按升序排列。 (子集然后可以通过从初始数组中获取这些索引的项目来创建。)所以我们需要生成所有这样的索引序列。
第一个索引序列将是[0, 1, 2, ... , k - 1]
,在第二步切换到[0, 1, 2,..., k]
,然后是[0, 1, 2, ... k + 1]
等等。最后可能的序列将是 [n - k, n - k + 1, ..., n - 1]
.
在每一步中,算法都会寻找最接近可以递增的最终项目,将其递增并填充该项目的项目。
为了说明,请考虑 n = 7
和 k = 3
。第一个索引序列是 [0, 1, 2]
,然后是 [0, 1, 3]
等等......在某个时候我们有 [0, 5, 6]
:
[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements
next iteration:
[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"
因此,[0, 5, 6]
之后是 [1, 2, 3]
,然后是 [1, 2, 4]
等等
代码:
int[] input = {10, 20, 30, 40, 50}; // input array
int k = 3; // sequence length
List<int[]> subsets = new ArrayList<>();
int[] s = new int[k]; // here we'll keep indices
// pointing to elements in input array
if (k <= input.length) {
// first index sequence: 0, 1, 2, ...
for (int i = 0; (s[i] = i) < k - 1; i++);
subsets.add(getSubset(input, s));
for(;;) {
int i;
// find position of item that can be incremented
for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--);
if (i < 0) {
break;
}
s[i]++; // increment this item
for (++i; i < k; i++) { // fill up remaining items
s[i] = s[i - 1] + 1;
}
subsets.add(getSubset(input, s));
}
}
// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
int[] result = new int[subset.length];
for (int i = 0; i < subset.length; i++)
result[i] = input[subset[i]];
return result;
}