Algoritmo / estrutura de dados para responder "que receitas posso fazer com este conjunto de ingredientes?"

Formalmente, vamos s ( U , Q ) = { V | V ∈ U e V ⊆ Q } onde U , Q e V representam todos conjuntos, e U , mais especificamente, representa um conjunto de conjuntos. Por uma questão de exemplo, U pode ser um conjunto dos (conjuntos de) ingredientes necessários para várias receitas em um livro de receitas com Q representando o conjunto de ingredientes que tenho V representando uma receita que eu poderia fazer com esses ingredientes. A consulta s ( U , Q) corresponde à pergunta "O que posso fazer com esses ingredientes?"

O que eu estou procurando é uma representação de dados que indexe U de modo a suportar consultas eficientes de s ( U , Q ), em que Q e todos os membros de U geralmente serão pequenos em comparação com a união de todos os membros de U . Além disso, gostaria de poder atualizar U com eficiência (por exemplo, adicionar ou remover uma receita).

Não posso deixar de pensar que esse problema deve ser bem compreendido, mas não consegui encontrar um nome ou referência para ele. Alguém sabe de uma estratégia para resolver isso com eficiência ou de um lugar onde eu possa ler mais sobre isso?

Tanto quanto pensamento sobre uma solução, um pensamento que tive foi para construir uma árvore de decisão para o conjunto U . Em cada nó da árvore, a pergunta "sua lista de ingredientes contém x ?" seria solicitado com x escolhido para maximizar o número de membros de U que são eliminados pela resposta. À medida que U é atualizado, essa árvore de decisão precisa ser reequilibrada para minimizar o número de perguntas necessárias para encontrar o resultado correto. Outro pensamento é representar U com algo como um 'octree' booleano n- dimensional (onde n é o número de ingredientes únicos).

Eu acredito que "Que receitas podem ser feitas com esses ingredientes?" pode ser respondido pegando o produto cartesiano das (conjuntos de ingredientes necessários para) as receitas do livro de receitas com o conjunto de ingredientes que você possui e filtrando os pares ordenados resultantes por pares nos quais os dois elementos são iguais, mas isso não é um solução eficiente, e o que estou perguntando é como otimizar esse tipo de operação; como alguém escreveria isso no SQL para que fosse eficiente e o que o SQL faz para permitir que isso seja eficiente?

Embora eu use a ilustração de um livro de receitas e um conjunto de ingredientes, prevejo que o número de 'receitas' e o número de 'ingredientes' serão muito grandes (até centenas de milhares cada), embora o número de ingredientes em uma dada receita e o número de ingredientes em um determinado conjunto de ingredientes será relativamente pequeno (provavelmente entre 10 e 50 para uma 'receita' típica e cerca de 100 para um 'conjunto de ingredientes' típico). Além disso, a operação mais comum será a consulta s ( U , Q ), portanto, deve ser a ideal. Isso também significa que um algoritmo de força bruta que exige a verificação de todas as receitas ou a operação de cada ingrediente seria indesejável e lento por si só. Com cache inteligente,

Para os números que você deu, apenas força bruta.

Aqui está um programa JavaScript que o força forçado a obter 10 ingredientes no banco de dados, 10 receitas no banco de dados, cada receita precisa de 2 ingredientes e eu tenho 5 ingredientes disponíveis:

var i, j;
var numIngredients = 10;
var numRecipes = 10;
var numIngredientsPerRecipe = 2;
var numIngredientsInQuery = 5;

function containsAll(needles, haystack){ 
  var i, len;
  for(i = 0 , len = needles.length; i < len; i++){
      if(haystack.indexOf(needles[i]) == -1) {
          return false;
      }
  }
  return true;
}

// Set up a fake DB of recipes
var ingredients = [];
for (i = 0; i < numIngredients; i++) {
    ingredients.push(i);
}
console.log('Here are the ingredients:', ingredients);

var recipes = [];
for (i = 0; i < numRecipes; i++) {
    var neededIngredients = [];
    for (j = 0; j < numIngredientsPerRecipe; j++) {
        neededIngredients.push(Math.floor(Math.random() * numRecipes));
    }
    recipes.push({ recipeId: i, needed: neededIngredients});
}
console.log('Here are the recipes:', recipes);

// Set up a fake query
var ingredientsAvailable = [];
for (i = 0; i < numIngredientsInQuery; i++) {
    ingredientsAvailable.push(Math.floor(Math.random() * numRecipes));
}

console.log("Here's a query:", ingredientsAvailable);

//Time how long brute force takes
var start = Date.now();
var result = [];
for (i = 0; i < numRecipes; i++) {
    var candidateRecipe = recipes[i];
    if (containsAll(candidateRecipe.needed, ingredientsAvailable)) {
        result.push(candidateRecipe);
    }
}
var end = Date.now();
console.log('Found ' + result.length + ' recipes in ' + (end - start) + ' milliseconds.');
console.log(result);

É executado em 0 milissegundos. Eu escolhi esses números pequenos para que você possa executá-lo algumas vezes e se convencer de que faz o que deseja e é relativamente livre de bugs.

Agora mude para que tenhamos 1'000'000 ingredientes no DB, 1'000'000 receitas no DB, 50 ingredientes por receita e 100 ingredientes disponíveis para mim. Ou seja, valores todos iguais ou maiores que o maior caso de uso que você forneceu.

Ele é executado em 125 milissegundos sob nodejs, e isso ocorre com a implementação mais burra, sem absolutamente nenhum esforço para otimizar.