Работа со словарем

@SW Developer · Регистрация: 10.01.2016

Студворк — интернет-сервис помощи студентам

Добрый день!
Предположим, есть словарь {1: [ 'A', 'B', 'C'], 2: ['B', 'D', 'F' ], 3: ['С', 'A', 'D', 'E'], 4: ['А', 'Е', 'В', 'F' ] }.
Как найти минимальное количество ключей, чтобы они охватили полностью диапазон ABCDEF?
Не хочу пока писать свои размышления, чтобы не навязывать то, что не получается у меня.)

@Fudthhh · 09.10.2020, 13:36

SW Developer,

Теория вкратце:
1) Скорее всего лучше хранить наборы данных не в списке, а в множестве.
2.1) А алгоритм перебора.
2.2) Получаем длину множества исходного слова.
2.3) Начинаем перебор словаря.

@SW Developer · 09.10.2020, 13:45 **[ТС]**

Я перевёл словарь в список списков.

@Fudthhh · 09.10.2020, 13:55

SW Developer, Скорее всего, это можно сделать проще.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import combinations
 
my_dictionary = {
    #0: {'A', 'B', 'C', 'D', 'E', 'F'},
    3: {'С', 'A', 'D', 'E'},
    4: {'А', 'Е', 'В', 'F'},
    1: {'A', 'B', 'C'},
    2: {'B', 'D', 'F'}
}
 
 
word = "ABCDEF"
 
results = []
for i in range(len(my_dictionary)):
    for keys in combinations(my_dictionary, i + 1):
        collect = set.union(*map(my_dictionary.get, keys))
        if len(collect) >= len(word) and set(word) <= collect:
            results.append(keys)
print(results)

Добавлено через 1 минуту
Выводит списки ключей, с помощью которых можно собрать слово.

Добавлено через 3 минуты
Можно после нахождения подходящей комбинации, перерывать циклы, т.к. первое найденное по факту будет самым меньшим набором индексов.

@SW Developer · 09.10.2020, 14:12 **[ТС]**

DmFat, спасибо. Буду разбираться.

@eaa · 09.10.2020, 14:17

Сообщение от SW Developer

чтобы они охватили полностью диапазон ABCDEF

это как? поясните если не сложно

@Fudthhh · 09.10.2020, 14:19

SW Developer, Логика такова:

1) Создаем цикл от нуля до размера словаря, переменную назовем "i".
2) Получаем все возможные комбинации размером "i + 1".
3) Цикл по всем возможным комбинациям.
4) Объединяем все множества по полученным ключам и называем "collect".
5) Если длинна множества "collect" больше или равно длинне множества исходного слова и все элементы исходного слова принадлежат множеству "collect", то мы нашли комбинацию.

Добавлено через 1 минуту
eaa, ему нужно чтобы слово было подмножеством набора, которое собирается из ключей.

@eaa · 09.10.2020, 14:24

хотелось бы услышать более точную формулировку и ограничения на входные данные, и примеры входных/выходных данных.

Добавлено через 3 минуты
пересечение ключей должно образовывать множество ABCDEF? Может так?

@SW Developer · 09.10.2020, 14:29 **[ТС]**

eaa, найти минимальное количество пересечений ключей, при которых будет охват ABCDEF.

@eaa · 09.10.2020, 14:36

ну если combination устраивает, то ок.
но что то мне подсказывает что время работы будет большое.

@SW Developer · 09.10.2020, 14:41 **[ТС]**

eaa, есть другие предложения? Хочу разобраться.

@eaa · 09.10.2020, 15:12

Задача о покрытии множества

@SW Developer · 09.10.2020, 15:18 **[ТС]**

eaa, спасибо.

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@SW Developer 97 / 93 / 81 Регистрация: 10.01.2016 Сообщений: 663 Записей в блоге: 13

	Работа со словарем 09.10.2020, 13:30. Показов 1397. Ответов 12 Метки нет (Все метки) Добрый день! Предположим, есть словарь {1: [ 'A', 'B', 'C'], 2: ['B', 'D', 'F' ], 3: ['С', 'A', 'D', 'E'], 4: ['А', 'Е', 'В', 'F' ] }. Как найти минимальное количество ключей, чтобы они охватили полностью диапазон ABCDEF? Не хочу пока писать свои размышления, чтобы не навязывать то, что не получается у меня.) 0

@Fudthhh Модератор 2695 / 1601 / 513 Регистрация: 21.02.2017 Сообщений: 4,210 Записей в блоге: 1
	09.10.2020, 13:36
	SW Developer, Теория вкратце: 1) Скорее всего лучше хранить наборы данных не в списке, а в множестве. 2.1) А алгоритм перебора. 2.2) Получаем длину множества исходного слова. 2.3) Начинаем перебор словаря. 0

@SW Developer 97 / 93 / 81 Регистрация: 10.01.2016 Сообщений: 663 Записей в блоге: 13
	09.10.2020, 13:45 [ТС]
	Я перевёл словарь в список списков. 0

@SW Developer 97 / 93 / 81 Регистрация: 10.01.2016 Сообщений: 663 Записей в блоге: 13
	09.10.2020, 14:12 [ТС]
	DmFat, спасибо. Буду разбираться. 0

@Fudthhh Модератор 2695 / 1601 / 513 Регистрация: 21.02.2017 Сообщений: 4,210 Записей в блоге: 1
	09.10.2020, 14:19
	SW Developer, Логика такова: 1) Создаем цикл от нуля до размера словаря, переменную назовем "i". 2) Получаем все возможные комбинации размером "i + 1". 3) Цикл по всем возможным комбинациям. 4) Объединяем все множества по полученным ключам и называем "collect". 5) Если длинна множества "collect" больше или равно длинне множества исходного слова и все элементы исходного слова принадлежат множеству "collect", то мы нашли комбинацию. Добавлено через 1 минуту eaa, ему нужно чтобы слово было подмножеством набора, которое собирается из ключей. 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.10.2020, 14:24
	хотелось бы услышать более точную формулировку и ограничения на входные данные, и примеры входных/выходных данных. Добавлено через 3 минуты пересечение ключей должно образовывать множество ABCDEF? Может так? 0

@SW Developer 97 / 93 / 81 Регистрация: 10.01.2016 Сообщений: 663 Записей в блоге: 13
	09.10.2020, 14:29 [ТС]
	eaa, найти минимальное количество пересечений ключей, при которых будет охват ABCDEF. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.10.2020, 14:36
	ну если combination устраивает, то ок. но что то мне подсказывает что время работы будет большое. 0

@SW Developer 97 / 93 / 81 Регистрация: 10.01.2016 Сообщений: 663 Записей в блоге: 13
	09.10.2020, 14:41 [ТС]
	eaa, есть другие предложения? Хочу разобраться. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.10.2020, 15:12
	Задача о покрытии множества 1

@SW Developer 97 / 93 / 81 Регистрация: 10.01.2016 Сообщений: 663 Записей в блоге: 13
	09.10.2020, 15:18 [ТС]
	eaa, спасибо. 0

Работа со словарем

Решение