java通过排除元素将一个列表拆分为多个列表

Question

有一个列表，其中的元素根据特定条件相互排斥

1. 现在我需要根据这个互斥条件拆分成多个列表

2. 对进行分区后，互斥元素不能出现在子列表中

3. 分段后的子列表数量应最小化

---------------例如------------------

1. 原始列表[A，B，C]

2. A和C互斥，A和B不互斥，B和C不互斥

3. 可分为[A]、[B、C]或[C]、[A、B]

4. 不要拆分为[A]、[B]、[C]，因为拆分后的子列表总数不是最小

谁能帮我？

Answer 1

据我所知，您希望根据集合中任意两个元素之间的任意比较来划分集合元素。我不认为java提供了开箱即用的功能。你可以这样做的一种方法是：

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

你可以这样测试你的场景：

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