gpt4 book ai didi

java - 从数组(Java)中获取所有大小 n 组合的算法?

转载 作者:IT老高 更新时间:2023-10-28 21:11:40 26 4
gpt4 key购买 nike

现在我正在尝试编写一个函数,它接受一个数组和一个整数 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");
}
}
}

最佳答案

这是一个经过充分研究的生成所有 k 子集的问题,或 k-combinations ,无需递归即可轻松完成。

这个想法是让大小为 k 的数组保持输入数组中元素的 indices 序列(它们是从 0n - 1) 以升序排列。 (子集然后可以通过这些索引从初始数组中获取项目来创建。)所以我们需要生成所有这样的索引序列。

第一个索引序列将是 [0, 1, 2, ... , k - 1],在第二步它切换到 [0, 1, 2,.. ., k],然后到 [0, 1, 2, ... k + 1] 等等。最后一个可能的序列将是 [n - k, n - k + 1, ..., n - 1].

在每一步中,算法都会查找最接近可以递增的最终项目,将其递增并填充到该项目的右侧。

为了说明,考虑 n = 7k = 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;
}

关于java - 从数组(Java)中获取所有大小 n 组合的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29910312/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com