现在,我正在尝试编写一个函数,该函数接受一个数组和一个整数n,并给出每个大小为n的组合的列表(因此为一个int数组的列表)。我可以使用n个嵌套循环来编写它,但这仅适用于特定大小的子集。我不知道如何将其推广到任何规模的组合。我想我需要使用递归吗?
这是3个元素的所有组合的html" target="_blank">代码,我需要一个任意数量的元素的算法。
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");
}
}
}
这是生成所有k子集或k组合的经过充分研究的问题,无需递归即可轻松完成。
这个想法是要使大小数组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个元素的所有组合的代码,我需要一个适用于任意数量元素的算法。
问题内容: 我想编写一个函数,该函数以字母数组作为参数,并选择多个字母。 假设您提供8个字母的数组,并希望从中选择3个字母。然后您将获得: 返回由3个字母组成的数组(或单词)。 问题答案: 格雷码您会遇到的一个问题当然是记忆力,而且很快,您的集合中会有20个元素出现问题-20 C 3 =1140。而且,如果要遍历集合,最好使用修改后的灰色代码算法,因此您不必将所有代码都保存在内存中。这些将根据之前
代码: 为什么第二个打印5而不是20?
问题内容: 我有一个字符数组c [] [],每个索引都有不同的映射。例如: 我需要以字符串形式返回此数组的所有可能字符组合。也就是说,对于上述字符数组,我应该返回:“ ag”,“ ah”,“ ai”,“ bg”,“ bh”,“ bi”,“ cg”,“ ch”,“ ci”等对于上面只有两件事的字符数组,这样做很容易,但是如果有更多的数组,那么我不知道该怎么办…这就是我要大家提供的帮助!:) 问题答案
问题内容: 我试图推导一种算法,该算法生成特定大小的所有可能组合,例如一个函数,该函数接受一个chars和size数组作为其参数,并返回一个组合数组。 示例:假设我们有一组字符:Set A = {A,B,C} a)大小2的所有可能组合:(3 ^ 2 = 9) b)大小3的所有可能组合:(3 ^ 3 = 27) 请注意,线对的大小可以大于对等的总大小。例如 如果set包含3个字符,则我们还可以创建大
给定一个具有n个键的数组或对象,我需要找到长度的所有组合 给定的是可变的。 目前我正在使用这个: 输出为: 因此,如果我想从< code>n=4中得到二项式系数< code>x=3,我选择所有长度等于3的字符串。{abc,abd,acd,bcd}。 所以我分两步做。 有没有一种复杂度更小、效率更高的算法? 链接: 解决方案性能 (JSPerf)