gpt4 book ai didi

java - 如何仅生成整数列表的 3 个分区

转载 作者:太空宇宙 更新时间:2023-11-04 09:22:44 24 4
gpt4 key购买 nike

我正在寻求帮助来调整 Java 代码,该代码从一组整数生成所有分区。我希望修改代码(我在 Stackoverflow 上找到)以仅生成 3 个子集的分区。

示例:

我的列表包含 1, 2, 3, 4, 5, 6

我想要获得 3 个分区,即我想要将列表分为 3 个子集。

输出应如下所示:

[1, 2, 3], [4], [5, 6]

[1, 2], [3, 5], [4, 6]

等等...

我试图修改这段代码,但没有成功。如果我生成所有分区,则仅考虑划分为 3 个子列表的分区。这需要时间。所以我希望避免生成不必要的分区。

代码链接:

Get all possible partitions of a set

package PartitionSetCreator;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class PartitionSetCreator<T> {

private Set<Set<Set<T>>> parts;//the partitions that are created
private Set<Set<T>> pow;//the power set of the input set
private Set<T> base;//the base set

/**
* The main method is just for testing and can be deleted.
*/
public static void main(String[] args) {
//test using an empty set = []
Set<Integer> baseSet = new HashSet<Integer>();

for (int i = 1; i < 10; i++) {
baseSet.add(i);
}
System.out.println("BaseSet: " + baseSet);
PartitionSetCreator<Integer> partSetCreator5 = new PartitionSetCreator<Integer>(baseSet);
Set<Set<Set<Integer>>> partitionSets5 = partSetCreator5.findAllPartitions();
System.out.println("Result: " + partitionSets5);

Iterator<Set<Set<Integer>>> iter = partitionSets5.iterator();
Set<Set<Set<Integer>>> partitionSetsof3 = new HashSet<Set<Set<Integer>>>();

//Print the output
for (Set<Set<Integer>> stock : partitionSets5) {
//Extract when the size is equal to 3
if (stock.size() == 3) {
partitionSetsof3.add(stock);
System.out.println(stock);
}
}
System.out.println(partitionSetsof3);

System.out.println("Base-Size: " + baseSet.size() + " Result-Size: " + partitionSets5.size());

}

public PartitionSetCreator(Set<T> base) {
this.base = base;
this.pow = powerSet(base);
if (pow.size() > 1) {
//remove the empty set if it's not the only entry in the power set
pow.remove(new HashSet<T>());
}
this.parts = new HashSet<Set<Set<T>>>();
}

/**
* Calculation is in this method.
*/
public Set<Set<Set<T>>> findAllPartitions() {
//find part sets for every entry in the power set
for (Set<T> set : pow) {
Set<Set<T>> current = new HashSet<Set<T>>();
current.add(set);
findPartSets(current);
}

//return all partitions that were found
return parts;
}

/**
* Finds all partition sets for the given input and adds them to parts (global variable).
*/
private void findPartSets(Set<Set<T>> current) {
int maxLen = base.size() - deepSize(current);
if (maxLen == 0) {
//the current partition is full -> add it to parts
parts.add(current);
//no more can be added to current -> stop the recursion
return;
} else {
//for all possible lengths
for (int i = 1; i <= maxLen; i++) {
//for every entry in the power set
for (Set<T> set : pow) {
if (set.size() == i) {
//the set from the power set has the searched length
if (!anyInDeepSet(set, current)) {
//none of set is in current
Set<Set<T>> next = new HashSet<Set<T>>();
next.addAll(current);
next.add(set);
//next = current + set
findPartSets(next);
}
}
}
}
}
}

/**
* Creates a power set from the base set.
*/
private Set<Set<T>> powerSet(Set<T> base) {
Set<Set<T>> pset = new HashSet<Set<T>>();
if (base.isEmpty()) {
pset.add(new HashSet<T>());
return pset;
}
List<T> list = new ArrayList<T>(base);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
newSet.add(head);
newSet.addAll(set);
pset.add(newSet);
pset.add(set);
}

return pset;
}

/**
* The summed up size of all sub-sets
*/
private int deepSize(Set<Set<T>> set) {
int deepSize = 0;
for (Set<T> s : set) {
deepSize += s.size();
}
return deepSize;
}

/**
* Checks whether any of set is in any of the sub-sets of current
*/
private boolean anyInDeepSet(Set<T> set, Set<Set<T>> current) {
boolean containing = false;

for (Set<T> s : current) {
for (T item : set) {
containing |= s.contains(item);
}
}

return containing;
}
}

期望避免生成不必要的分区以加速运行。

最佳答案

使用Arrays.copyOfRange

static void splitArray(int[] arr) {
int i, j, k;
int n = arr.length;
for (i = 1; i < n; i++) {
for (j = 1; j < n; j++) {
for (k = 1; k < n; k++) {
if (i + j + k == n) {
System.out.println( //
Arrays.toString(Arrays.copyOfRange(arr, 0, i)) + ", " + //
Arrays.toString(Arrays.copyOfRange(arr, i, i + j)) + ", " + //
Arrays.toString(Arrays.copyOfRange(arr, i + j, n)) //
);
}
}
}
}
}

public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6 };
splitArray(arr);
}

输出

[1], [2], [3, 4, 5, 6]
[1], [2, 3], [4, 5, 6]
[1], [2, 3, 4], [5, 6]
[1], [2, 3, 4, 5], [6]
[1, 2], [3], [4, 5, 6]
[1, 2], [3, 4], [5, 6]
[1, 2], [3, 4, 5], [6]
[1, 2, 3], [4], [5, 6]
[1, 2, 3], [4, 5], [6]
[1, 2, 3, 4], [5], [6]

一般情况下,使用CollectionUtils.permutations查找 arr 的所有排列并为每个排列调用 splitArray()

关于java - 如何仅生成整数列表的 3 个分区,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58126202/

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