Вычисление всех подмножеств набора чисел
Типичный код для итерации по карте:
Map<String,Thing> map = ...;
for (Map.Entry<String,Thing> entry : map.entrySet()) {
String key = entry.getKey();
Thing thing = entry.getValue();
...
}
HashMap каноническая реализация Map и не делает гарантии (или хотя она не должна заявка на изменение, если никакая операция видоизменения не выполняется на ней). SortedMap возвратит записи на основе естественного упорядочивания ключей, или Comparator, если обеспечено. LinkedHashMap или возвратит записи в порядке вставки или порядке доступа в зависимости от того, как это было создано. EnumMap записи возвратов в естественном порядке ключей.
(Обновление: Я думаю, что это больше не верно. ) Примечание, IdentityHashMap entrySet итератор в настоящее время имеет специфическую реализацию, которая возвращает тот же Map.Entry экземпляр для каждого объекта в entrySet! Однако каждый раз новое итератор совершенствуется эти Map.Entry, обновляется.
1 ответ
Простой Java рекурсивное решение -
private static List<List<Integer>> allsubSet(List<Integer> integers, int start, int end) {
//Base case if there is only one element so there would be two subset
// empty list and that element
if(start == end) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> emptyList = new ArrayList<>();
result.add(emptyList);
List<Integer> element = new ArrayList<>();
element.add(integers.get(start));
result.add(element );
return result;
}
//I know if by recursion we can expect that we'll get the n-1 correct result
List<List<Integer>> lists = allsubSet(integers, start, end-1);
//here i copy all the n-1 results and just added the nth element in expected results
List<List<Integer>> copyList = new ArrayList<>(lists);
for (List<Integer> list : lists) {
List<Integer> copy= new ArrayList<>(list);
copy.add(integers.get(end));
copyList.add(copy);
}
return copyList;
}
Для предотвращения дублирования мы можем просто использовать Набор вместо Списка