Explosiones combinatorias explicadas con helado: cómo agregar un poco y obtener mucho

Exploremos el mundo divertido y contrario a la intuición de la combinatoria.

Combinar valores para formar conjuntos de combinaciones distintas puede ser complicado. Incluso si ignora el orden, el número de conjuntos posibles crece de forma alarmante.

Para una matriz de dos valores [1, 2], puede generar:

  • [] (conjunto vacio)
  • [1]
  • [2]
  • [1,2] (o [2,1])

Si se permiten repeticiones ([2, 2] por ejemplo), el aumento es aún mayor. A medida que aumenta el número de valores de entrada, ¡el número de conjuntos de salida correspondientes se dispara por las nubes!

Llamemos a los valores de entrada elementos y cada combinación de esos valores una elección . Además, permitamos varios elementos, cada uno con distintas opciones. Un buen ejemplo práctico sería un menú. Simularemos el menú de Ye Olde Ice Cream Shoppe , que ofrece a sus clientes combinaciones de helados, coberturas y sabores de almíbar.

Los sabores del helado son: CHOCOLATE, FRESA, VAINILLA

Ingredientes: piña, fresa, copos de coco, nueces

Siropes: chocolate, malvavisco, caramelo, arce

Existen algunas limitaciones en las opciones: los clientes pueden elegir dos helados, dos ingredientes y un jarabe. Las opciones de helado y cobertura son exclusivas, lo que significa que no puedo elegir piña + piña, por ejemplo. El cliente puede optar por no tener coberturas ni almíbar, pero debe elegir al menos un helado. Con estas restricciones, la tasa de aumento es exponencial, del orden 2 elevado a la n-ésima potencia, que es considerablemente menor que si el orden fuera significativo y se permitieran duplicados.

Sabor agradable

Ye Olde Ice Cream Shoppe es en realidad bastante moderno en su enfoque comercial y está desarrollando un sistema experto en inteligencia artificial para juzgar qué combinaciones de helado, aderezo y almíbar son apetecibles. A los servidores se les mostrará una advertencia en sus registros cuando un cliente elija una selección desagradable. A continuación, se indica a los servidores que verifiquen con el cliente que su pedido es correcto.

Paso 1: construir los datos

El código de este artículo se puede encontrar aquí. Asumiré que está familiarizado con JavaScript y Node.js. Un conocimiento práctico de Lodash (o subrayado) es útil. El código usa una base de datos de mapa / reducción para almacenamiento.

El primer paso será crear una base de datos de todas las combinaciones de helado, aderezo y jarabe. Las entradas serán las siguientes:

var menu = { iceCream: {min: 1, max: 2, values: ["CHOCOLATE", "STRAWBERRY", "VANILLA"]}, topping: {min: 0, max: 2, values: ["pineapple", "strawberry", "coconut flakes", "pecans"]}, syrup: {min:0, max: 1, values: ["chocolate", "marshmallow", "butterscotch", "maple"]} }

Con estos datos, puedo escribir una función Combinadora que tome cada elemento del menú y genere todas las combinaciones permitidas posibles. Cada combinación se almacena como una matriz. Por ejemplo, las combinaciones de helados se verían así:

[ [ ‘CHOCOLATE’, ‘STRAWBERRY’ ], [ ‘CHOCOLATE’, ‘VANILLA’ ], [ ‘CHOCOLATE’ ], [ ‘STRAWBERRY’, ‘VANILLA’ ], [ ‘STRAWBERRY’ ], [ ‘VANILLA’ ] ]

Una vez que se determinan las combinaciones de helado, aderezos y jarabes, todo lo que queda es iterar cada combinación de elementos con los demás:

var allChoices = []; _.each(iceCreamChoices, function(ic) { _.each(toppingChoices, function(tp) { _.each(syrupChoices, function(sy) { allChoices.push([ic,tp,sy]); }) }) })

Esto produce una combinación de helado (s), cobertura (s) y almíbar, como:

[ [ 'VANILLA' ], [ 'coconut flakes', 'pecans' ], [] ], [ [ 'VANILLA' ], [ 'coconut flakes' ], [ 'chocolate' ] ], [ [ 'VANILLA' ], [ 'coconut flakes' ], [ 'marshmallow' ] ],...

Las opciones que se muestran se traducen como:

  • Helado de vainilla con copos de coco y nueces pecanas, sin almíbar
  • Helado de vainilla con copos de coco y sirope de chocolate
  • Helado de vainilla con copos de coco y sirope de malvavisco

Incluso con unos pocos elementos de menú restringidos, ¡el número de opciones permitidas es 330!

Paso 2: almacenar los datos

Con cada combinación de artículos que se pueden pedir ahora determinada, se puede seguir trabajando. El sistema de inteligencia artificial para determinar combinaciones de opciones apetitosas está resultando ser complejo y no estará integrado en el sistema operativo de los registros. En su lugar, se realizará una solicitud AJAX a un servidor que aloja el programa AI. Las entradas serán las opciones del menú del cliente, y la salida calificará la palatabilidad de esas opciones como una de las siguientes: [ugh, meh, sabroso, sublime]. Una calificación de palatabilidad de ugh desencadena la advertencia anterior.

Necesitamos una respuesta rápida a la solicitud, por lo que las calificaciones de palatabilidad se almacenarán en caché en una base de datos. Dada la naturaleza del aumento exponencial, esto podría evolucionar hasta convertirse en un problema de Big Data si se agregan más opciones de elementos al menú en el futuro.

Digamos que se decide almacenar combinaciones de opciones y calificaciones en una base de datos NoSQL. Con PouchDB, cada elección y valor de palatabilidad se almacenan como documentos JSON. Un índice secundario (también conocido como vista ) con cada elección como clave nos permitirá buscar rápidamente la calificación de palatabilidad. En lugar de enviar los datos a una matriz allChoices como se muestra arriba en buildChoices.js, puedo enviar documentos JSON a la base de datos para su almacenamiento.

Procediendo ingenuamente, puedo hacer un par de cambios en Step1.js para llegar a Step2.js: en primer lugar, necesito instalar PouchDB a través de npm, luego lo necesito. Luego, creo una base de datos NoSQL llamada opciones .

var PouchDB = require('pouchdb'); var db = new PouchDB('choices');

Ahora, cada opción se publica en la base de datos de opciones:

var count = 0; _.each(iceCreamChoices, function(ic) { _.each(toppingChoices, function(tp) { _.each(syrupChoices, function(sy) { //allChoices.push([ic,tp,sy]); db.post({choice: [ic,tp,sy]}, function(err, doc){ if (err) console.error(err); else console.log(`stored ${++count}`); }); }) }) }); console.log('done??');

¡Esto funciona! Algo así como. Como puede inferirse del parámetro de devolución de llamada a db.post , esa operación es asincrónica. Lo que vemos en el registro es:

>node Step2.js done?? stored 1 stored 2 stored 3 ...

Entonces, el código dice que está hecho incluso antes de que se haya almacenado el registro 1. Esto será un problema si tengo que procesar más en la base de datos y todos los registros aún no están allí.

Paso 3: reparación y refinamiento

También hay un problema más sutil: el posible agotamiento de los recursos. Si la base de datos limita el número de conexiones simultáneas, una gran cantidad de solicitudes de publicación simultáneas puede resultar en tiempos de espera de conexión.

For Step3.js, I did a bit of bug fixing, reformatting and refactoring of what was written in Step2.js. One bug was that each run added more and more records to the database, duplicating what was there before. The solution was to destroy the existing database, re-create it, and then run the main program:

// remove old db.destroy(null, function () { db = new PouchDB('choices'); run(); });

Next was to add a running count of documents stored and post requests in process so that the program: 1) knows when the last document is stored; 2) allows only five posts to proceed at any one time. The run() method looks like this now (with some omissions):

function run() { var menu = { //... } var iceCreamChoices = new Combinator({ //... }); var toppingChoices = new Combinator({ //... }); var syrupChoices = new Combinator({ //... }); var count = 0; var total = iceCreamChoices.length * toppingChoices.length * syrupChoices.length; var postCount = 0; var postCountMax = 5; _.each(iceCreamChoices, function (ic) { _.each(toppingChoices, function (tp) { _.each(syrupChoices, function (sy) { var si = setInterval(() => { if (postCount < postCountMax) { clearInterval(si); postChoice(ic, tp, sy); } }, 10); }) }) }); function postChoice(ic, tp, sy) { ++postCount; db.post({ choice: [ic, tp, sy] }, function (err, doc) { --postCount; done(err); }); } function done(err) { if (err) { console.error(err); process.exit(1); } console.log(`stored ${++count}`); if (count === total) { console.log('done'); } } }

The main changes to note are that:

  1. A postCount tracks how many posts are outstanding
  2. An interval timer checks the postCount and will post and exit when post slots are available
  3. a done() handler is called when all choices are stored

Step 4: Adding Palatability

With all possible menu choices in place, we can now have the AI determine the palatability of each. The AI is just a mock at the moment, which assigns random values to each document record in PouchDB. Those values will be stored in the database by updating each document with a taste rating.

var _ = require('lodash'); var PouchDB = require('pouchdb'); var db = new PouchDB('choices'); db.allDocs({ include_docs: true }) .then(docs => { _.each(docs.rows, r => { r.doc.taste = palatability(); db.put(r.doc); }); }); function palatability() { var scale = Math.round(Math.random() * 10); var taste; switch (true) { // this switch is a horrible hack; don't ever do this ;-P case (scale < 2): taste = "ugh"; break; case (scale < 5): taste = "meh"; break; case (scale < 8): taste = "tasty"; break; default: taste = "sublime"; break; } return taste; }

Just to verify that we stored things correctly, we can dump the docs in the database to the console:

db.allDocs({ include_docs: true }) .then(docs => { _.each(docs.rows, r => { console.log(r.doc.choice, r.doc.taste) }); }); //output looks like: /* [ [ 'STRAWBERRY' ], [ 'coconut flakes' ], [ 'maple' ] ] 'sublime' [ [ 'CHOCOLATE' ], [ 'pecans' ], [ 'chocolate' ] ] 'tasty' [ [ 'CHOCOLATE', 'STRAWBERRY' ], [], [ 'chocolate' ] ] 'sublime' [ [ 'VANILLA' ], [], [ 'marshmallow' ] ] 'meh' [ [ 'CHOCOLATE', 'STRAWBERRY' ], [ 'pineapple' ], [ 'marshmallow' ] ] 'meh' */

Step 5: Looking Up Palatability

The documents are in the database, but now there needs to be a way to determine what the palatability is for a customer’s choices. This is done by defining a view, which is a function that returns a key for each document, along with a value. What should the key be?

I could use r.doc.choice as the key, but arrays have an order and that order might change if the menu items defined in Step 1 were later rearranged. The key is just an identifier of the choice selection and doesn’t carry an semantic meaning of its own. What should work is to:

  • flatten each r.doc.choice array,
  • order the elements alphabetically, then
  • concatenate them together
  • result is a key

If more choices are added in the future, though, the key length might be over the limit allowed by the database. Instead of using the key as constructed, a hash the key could be used as the real key. A SHA256 hash in hex is 64 characters long, and the likelihood of a hash collision, even for a quadrillion choices, is essentially zero. Writing the hash function for choices is easy, using the Node.js crypto module and a Lodash chain:

const crypto = require('crypto'); const _ = require('lodash') function hash(choice) ') .value(); return crypto.createHmac('sha256', 'old ice cream') .update(str) .digest('hex');  module.exports = hash;

Adding the hash to our existing documents is a simple matter of iterating through each database document, computing its hash, and updating the document with a key value:

const _ = require('lodash'); const hash = require('./hash'); const PouchDB = require('pouchdb'); const db = new PouchDB('choices'); db.allDocs({ include_docs: true }) .then(docs => { _.each(docs.rows, r => { r.doc.key = hash(r.doc.choice); db.put(r.doc); }); }) .catch(e => { console.error(e) });

Next, a database view is built using the document key field as an index; I’ll call it choice.

const PouchDB = require('pouchdb'); const db = new PouchDB('choices'); // doc that defines the view var ddoc = { _id: '_design/choice', views: { by_key: { map: function (doc) { emit(doc.key, doc.taste); }.toString() } } }; // remove any existing view, then add new one: db.get(ddoc._id) .then(doc => { return db.remove(doc); }) .then(() => { db.put(ddoc) .catch(function (err) { console.error(err); }); });

For any document key (hash of choice array), I can find its taste via the view choice. Now everything is in place to determine whether a customer’s choice is ugh, meh, tasty, or sublime. To test this, we make some random choices and see if we can find the taste:

 const choices = [ [['VANILLA'], ['coconut flakes', 'pecans'], ['marshmallow']], [['CHOCOLATE'], ['pecans'], ['chocolate']], [['STRAWBERRY', 'VANILLA'], ['pineapple', 'coconut flakes'], ['marshmallow']], [['STRAWBERRY'], ['pecans'], ['maple']], [['VANILLA'], ['coconut flakes', 'pineapple'], ['chocolate']], [['CHOCOLATE, STRAWBERRY'], ['pineapple', 'pecans'], ['butterscotch']], ]; const keys = _.map(choices, c => { return hash(c); }); db.query('choice/by_key', { keys: keys, include_docs: false, }, function (err, result) { if (err) { return console.error(err); } _.each(result.rows, (r, i) => { console.log(`${choices[i]} tastes ${r.value}`); }) });

The results are:

=> node test VANILLA,coconut flakes,pecans,marshmallow tastes ugh CHOCOLATE,pecans,chocolate tastes sublime STRAWBERRY,VANILLA,pineapple,coconut flakes,marshmallow tastes tasty STRAWBERRY,pecans,maple tastes meh VANILLA,coconut flakes,pineapple,chocolate tastes sublime

That’s it! All that’s left is to write client software that submits choices via AJAX and gets a taste (palatability) value back. If it’s ugh, then up comes a warning on the register.

In a subsequent post, I refine the algorithm used above. Check it out!

References

Exponential Growth Isn't Cool. Combinatorial Explosion Is.

So much of the tech industry is obsessed with exponential growth. Anything linear is dying, or has been dead for years…

www.torbair.com

Combinations and Permutations Calculator

Find out how many different ways you can choose items. For an in-depth explanation of the formulas please visit…

www.mathsisfun.com