Найдите отличные квалифицированные комбинации A & B, с множеством исключений A: B - PullRequest
Новая
       4

Найдите отличные квалифицированные комбинации A & B, с множеством исключений A: B

5 голосов
/ 31 августа 2011

С учетом всех вопросов о "отличной комбинации" и "декартовом произведении", связанных с SO, я уверен, что для этого вопроса есть название и каноническое решение, но я не собираюсь его поднимать.

Обновление ... Вот потенциально лучший пример: Предположим, в клубе регулярно проводятся лотереи. Многие вещи разыгрываются за событие, и участники покупают билеты за каждую вещь. В лотерейный вечер менеджер лотереи распечатывает пачки карточек с именами, партии A, B, C и так далее. Когда разыгрывается каждый предмет, он бросает одну из этих предварительно собранных партий в бункер, смешивает ее и рисует имя. После раздачи приза имя возвращается в партию, которую он использует повторно, если какой-либо другой предмет имеет ту же партию участников. Вопрос: существует ли алгоритм без сохранения состояния, который может собирать партии карточек с именами, печатая минимальное общее количество карточек? [Если нет, то пример HashSet <> Криса Шейна - наиболее эффективная альтернатива с отслеживанием состояния, которую я знаю.]

Оригинальный вопрос и примеры: Рассмотрим следующие списки людей, бутербродов и аллергий (хранятся реляционно; эти структуры данных предназначены только для того, чтобы публикация была короткой, и не являются неотъемлемой частью вопроса или решения) : 

var people = { "Pete", "Barb", "Debbie", "Frank", "Ralph", "Sally" };
var sandwiches = { "Peanut Butter", "Egg Salad", "Tuna Salad", "Oven Roasted Chicken", "Gluten-free Twigs" };
var allergies = {
    { "Pete", null }, 
    { "Barb", { "Peanut Butter" } }, 
    { "Debbie", { "Peanut Butter", "Egg Salad", "Tuna Salad" } }, 
    { "Frank", { "Egg Salad", "Tuna Salad" } }, 
    { "Ralph", { "Oven Roasted Chicken" } },
    { "Sally", { "Egg Salad", "Tuna Salad" } } };

Чтобы найти людей, которые могут съесть тот или иной бутерброд, я, конечно, могу достаточно легко перебрать бутерброды (внешние) и людей (внутренние) и проверить на аллергию.

Однако я хочу предварительно рассчитать и опубликовать наименьший список неаллергических людей наборов , которые будут охватывать все бутерброды (люди, очевидно, будут принадлежать более чем к одному набору), не более чем один набор людей для любого сэндвича, и максимальное повторное использование, например, набор [Пит, Барб, Дебби, Фрэнк, Салли] будет охватывать как безглютеновые веточки, так и жареную курицу в духовке.

Например, скажем, есть список бутербродов, которые нужно разыграть. Повар делает один, а затем должен выяснить, кто участвует в розыгрыше (все, кто не аллергик). Я хочу получить наименее повторяющуюся пачку карточек с именами в резиновой полоске, пачку A, B, C и так далее, чтобы можно было иметь список сэндвичей, каждый из которых указывает, какую пачку карточек с именами бросить в шляпу для этого бутерброда , Представьте себе, что бумага с именной карточкой стоит действительно дорого. (Очевидно, я изменил проблемный домен для примера.)

Я делаю это сейчас, используя эквивалент хеш-таблицы наборов людей, а затем вставляю указатели на эти наборы в словарь, снабженный сэндвичем. Он работает просто отлично, но чувствует себя не элегантно.

Спасибо всем, кто может назвать эту проблему и указать мне на более симпатичный (или более учебный) подход.

Обновление : я достигаю желаемого конечного результата, используя эквивалент MySQL GROUP_CONCAT. Это не идеально, но я добавляю это, потому что это проясняет желаемый конечный результат. В псевдокоде: 

// SandwichPeople = the sandwich list with a concatenated list of 
// people who can eat it:
SELECT Sandwich.SandwichName, GROUP_CONCAT(Person.FullName SEPARATOR ', ') as MemberNames
FROM Sandwich JOIN Person on [...not allergic...]

// SandwichRoster = distinct People from SandwichPeople with auto id
INSERT IGNORE INTO SandwichRoster (MemberNames) 
 SELECT DISTINCT MemberNames from SandwichPeople

// Match sandwiches with rosters:
SELECT SandwichPeople.SandwichName, SandwichRoster.ID
FROM SandwichPeople 
JOIN SandwichRoster on SandwichPeople.MemberNames = SandwichRoster.MemberNames

1 Ответ

1 голос
/ 31 августа 2011

Создать словарь строковых ключей и HashSet<string> значений. Выполните итерацию по словарю человека-> аллергии один раз, и для каждой аллергии получите или создайте запись в словаре для этой аллергии: 

// A dictionary containing the set of people who are allergic to any given thing
var allergyLookup = new Dictionary<String, HashSet<String>>();
allergies.ForEach(kvp => {
    var allergicSet = allergyLookup.ContainsKey(kvp.Value) ? allergyLookup[kvp.Value] : allergyLookup[kvp.Value] = new HashSet<String>();
    allergicSet.Add(kvp.Key);
}

Тогда, когда вам нужно найти людей, страдающих аллергией на набор ингредиентов, вы можете использовать функцию ExceptWith на основе быстрого набора: 

var ingredients = { "Tuna", "Peanut Butter" };
var peopleWhoCanEatThis = new HashSet<String>(allPeople);
ingredients.ToList().ForEach(i => peopleWhoCanEatThis.ExceptWith(allergyLookup[i]));

Функция ExceptWith () в HashSet намного быстрее, чем универсальная, потому что она основана на множествах и может выполнять поиск в фиксированное время, а не в линейный.

РЕДАКТИРОВАТЬ: ошибочно использовал функцию «кроме» - вычитание быстрого набора ExceptWith: http://msdn.microsoft.com/en-us/library/bb299875.aspx

...