英文:
java Split one list into multiple lists by exclusion of elements
问题
有一个列表,其中的元素根据某些条件是相互排斥的。
-
现在我需要根据这种相互排斥条件将其拆分为多个列表。
-
在分割后,相互排斥的元素不能出现在同一个子列表中。
-
分割后子列表的数量应尽量少。
-------------例如----------------------
-
原始列表 [A, B, C]
-
A 和 C 是相互排斥的,A 和 B 不是相互排斥的,B 和 C 也不是相互排斥的。
-
可以分成 [A], [B, C] 或者 [C], [A, B]。
-
不要分成 [A], [B], [C],因为分割后的子列表总数不是最少的。
谁能帮帮我?
英文:
There is a List in which the elements are mutually exclusive according to certain conditions
-
Now I need to split into multiple Lists according to this mutual exclusion condition
-
Mutually exclusive elements cannot appear in a child List after partitioning
-
The number of child Lists after segmentation should be minimized
-------------For example----------------------
-
Original list [A, B, C]
-
A and C are mutually exclusive, A and B are not mutually exclusive, and B and C are not mutually exclusive
-
It can be divided into [A], [B, C] or [C], [A, B]
-
Do not split into [A], [B], [C], because the total number of sub lists after splitting is not the minimum
Who can help me?
答案1
得分: 0
根据我理解,您想要基于集合中任意两个元素之间的任意比较来对集合元素进行分区。我认为 Java 并没有内置这种功能。您可以使用以下方法来实现:
public class Partition<T> {
public List<Set<T>> partition(List<T> list, BiPredicate<T, T> partitionCondition) {
List<Set<T>> partition = new ArrayList<>();
while (!list.isEmpty()) {
// 从原始列表中获取剩余元素的第一个元素
T firstElement = list.remove(0);
// 将第一个元素添加到子集中
// 此子集中的所有元素都不得与 firstElement 互斥
Set<T> subset = new HashSet<>();
subset.add(firstElement);
// 获取所有其余元素,它们可以存在于与 firstElement 相同的子集中
List<T> notMutuallyExclusive = list.stream().filter(e -> !partitionCondition.test(firstElement, e))
.collect(Collectors.toList());
// 将它们添加到 firstElement 的子集中
subset.addAll(notMutuallyExclusive);
// 将子集添加到分区(子集列表)中
partition.add(subset);
// 从原始列表中删除已添加的元素
list.removeAll(notMutuallyExclusive);
}
return partition;
}
}
您可以像这样测试您的场景:
public class PartitionSmallTest {
private BiPredicate<String, String> areMutuallyExclusive() {
return (left, right) -> ("A".equals(left) && "C".equals(right)) || ("C".equals(left) && "A".equals(right));
}
@Test
public void test() {
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
List<Set<String>> expected = new ArrayList<>();
expected.add(Set.of("A", "B"));
expected.add(Set.of("C"));
List<Set<String>> actual = new Partition<String>().partition(list, areMutuallyExclusive());
Assert.assertEquals(expected, actual);
}
}
英文:
From what I understand, you want to partition a set elements based on an arbitrary comparison between any two elements in the set. I don't think java comes with that functionality out of the box. One way you can do that is the following:
public class Partition<T> {
public List<Set<T>> partition(List<T> list, BiPredicate<T, T> partitionCondtion) {
List<Set<T>> partition = new ArrayList<>();
while (!list.isEmpty()) {
// get first element from the remaining elements on the original list
T firstElement = list.remove(0);
// add first element into a subset
// all elements on this subset must not be mutually exclusive with firstElement
Set<T> subset = new HashSet<>();
subset.add(firstElement);
// get all remaining elements which can reside in the same subset of
// firstElement
List<T> notMutuallyExclusive = list.stream().filter(e -> !partitionCondtion.test(firstElement, e))
.collect(Collectors.toList());
// add them to the subset of firstElement
subset.addAll(notMutuallyExclusive);
// add subset to partition (list of subsets)
partition.add(subset);
// remove elements added from original list
list.removeAll(notMutuallyExclusive);
}
return partition;
}
}
You can test your scenario like this:
public class PartitionSmallTest {
private BiPredicate<String, String> areMutuallyExclusive() {
return (left, right) -> ("A".equals(left) && "C".equals(right)) || ("C".equals(left) && "A".equals(right));
}
@Test
public void test() {
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
List<Set<String>> expected = new ArrayList<>();
expected.add(Set.of("A", "B"));
expected.add(Set.of("C"));
List<Set<String>> actual = new Partition<String>().partition(list, areMutuallyExclusive());
Assert.assertEquals(expected, actual);
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论