Sure, here is the translation: 将一个列表按元素排除分割为多个列表

huangapple go评论69阅读模式
英文:

java Split one list into multiple lists by exclusion of elements

问题

有一个列表,其中的元素根据某些条件是相互排斥的。

  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],因为分割后的子列表总数不是最少的。

谁能帮帮我?

英文:

There is a List in which the elements are mutually exclusive according to certain conditions

  1. Now I need to split into multiple Lists according to this mutual exclusion condition

  2. Mutually exclusive elements cannot appear in a child List after partitioning

  3. The number of child Lists after segmentation should be minimized

-------------For example----------------------

  1. Original list [A, B, C]

  2. A and C are mutually exclusive, A and B are not mutually exclusive, and B and C are not mutually exclusive

  3. It can be divided into [A], [B, C] or [C], [A, B]

  4. 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&lt;T&gt; {

	public List&lt;Set&lt;T&gt;&gt; partition(List&lt;T&gt; list, BiPredicate&lt;T, T&gt; partitionCondtion) {
		List&lt;Set&lt;T&gt;&gt; partition = new ArrayList&lt;&gt;();

		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&lt;T&gt; subset = new HashSet&lt;&gt;();
			subset.add(firstElement);

			// get all remaining elements which can reside in the same subset of
			// firstElement
			List&lt;T&gt; notMutuallyExclusive = list.stream().filter(e -&gt; !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&lt;String, String&gt; areMutuallyExclusive() {
		return (left, right) -&gt; (&quot;A&quot;.equals(left) &amp;&amp; &quot;C&quot;.equals(right)) || (&quot;C&quot;.equals(left) &amp;&amp; &quot;A&quot;.equals(right));
	}

	@Test
	public void test() {
		List&lt;String&gt; list = new ArrayList&lt;&gt;(Arrays.asList(&quot;A&quot;, &quot;B&quot;, &quot;C&quot;));

		List&lt;Set&lt;String&gt;&gt; expected = new ArrayList&lt;&gt;();
		expected.add(Set.of(&quot;A&quot;, &quot;B&quot;));
		expected.add(Set.of(&quot;C&quot;));

		List&lt;Set&lt;String&gt;&gt; actual = new Partition&lt;String&gt;().partition(list, areMutuallyExclusive());

		Assert.assertEquals(expected, actual);
	}

}

huangapple
  • 本文由 发表于 2020年9月23日 10:16:52
  • 转载请务必保留本文链接:https://go.coder-hub.com/64020084.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定