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

Question

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

例：

我 我的清单包含1, 2, 3, 4, 5, 6

我想获得 3 的分区，即我想将我的列表划分为 3 个子集。

输出应如下所示：

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

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

等。。。

我试图修改这段代码是徒劳的。如果我生成所有分区，则仅考虑在 3 个子列表中分区的分区。这需要时间。因此，我希望避免生成不必要的分区。

代码链接：

获取集合的所有可能分区

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;
}
}

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

Answer 1

use 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()