正在寻找一个更简单的解决方案

Question

问题：根据给定的bucket及其项的映射，我需要确定是否至少有三个bucket具有唯一项。

注：

1. 一个bucket可以有多个项目
2. 存储桶的总数可以是0-100之间的任何值
3. 唯一项目将仅在项目1、项目2和项目3之间

样本数据：

Map<String, List<String>> buckets = new HashMap<>();
// sample data 1 - expected output -> true
buckets.put("b1", Arrays.asList("item1", "item2", "item3"));
buckets.put("b2", Arrays.asList("item1", "item2", "item3"));
buckets.put("b3", Arrays.asList("item1"));

System.out.println("sample 1: "+ isUniqueBucketsAndItemFound(buckets));

Map<String, List<String>> bucket2 = new HashMap<>();

// sample data 2 - expected output -> false because there are no unique buckets for 2,3
bucket2.put("b1", Arrays.asList("item1", "item2", "item3"));
bucket2.put("b2", Arrays.asList("item1"));
bucket2.put("b3", Arrays.asList("item1"));

System.out.println("sample 2: "+ isUniqueBucketsAndItemFound(bucket2));

我在下面尝试的解决方案实际上有效。然而，如果可能的话，寻找更简单的解决方案来避免迭代，

private static boolean isUniqueBucketsAndItemFound(Map<String, List<String>> buckets) {

//handle basic negative cases null/empty/ size<3 etc

List<List<String>> perumatations = new ArrayList<>();
perumatations.add(Arrays.asList("item1", "item2", "item3"));
perumatations.add(Arrays.asList("item1", "item3", "item2"));
perumatations.add(Arrays.asList("item2", "item1", "item3"));
perumatations.add(Arrays.asList("item2", "item3", "item1"));
perumatations.add(Arrays.asList("item3", "item1", "item2"));
perumatations.add(Arrays.asList("item3", "item2", "item1"));

for(List<String> items : perumatations) {
System.out.println("iteration: "+ items);
boolean isItem1Found = false;
boolean isItem2Found = false;
boolean isItem3Found = false;

for(Map.Entry<String, List<String>> bucket : buckets.entrySet()) {
List<String> currentItems = bucket.getValue();

if(!isItem1Found && currentItems.contains(items.get(0))) {
isItem1Found = true;
} else if(!isItem2Found && currentItems.contains(items.get(1))) {
isItem2Found = true;
} else if(!isItem3Found && currentItems.contains(items.get(2))) {
isItem3Found = true;
}

if(isItem1Found && isItem2Found && isItem3Found) {
return true;
}
}
}

return false;
}

Answer 1

这里有一种递归方法，它尝试每个bucket最多分配一个项目，如果无法将剩余项目分配给剩余bucket，则会回溯：

private static boolean isUniqueBucketsAndItemFound(Map<String, List<String>> buckets) {
Set<String> items = new HashSet<>(Arrays.asList("item1", "item2", "item3"));
return search(items, new ArrayList<>(buckets.values()), 0);
}
private static boolean search(Set<String> items, List<List<String>> buckets, int offset) {
// allocated all unique items?
if (items.isEmpty()) {
return true;
}

for (int i = offset; i < buckets.size(); i++) {
for (String item : buckets.get(i)) {
// found unique item?
if (items.remove(item)) {
// search remaining items in remaining buckets
if (search(items, buckets, i + 1)) {
return true;
}
// restore popped item
items.add(item);
}
}
}

// out of buckets
return false;
}

Ideone演示

在第一种方法中，可以通过对bucket进行排序并删除重复项来优化搜索，但我将把这作为一个练习留给读者。