A kombinatorikus robbanások jégkrémmel magyarázhatók: hogyan lehet egy keveset adni és sokat kapni?

Fedezzük fel a kombinatorika szórakoztató, intuitív világát.

Az értékek egyesítése különálló kombinációk halmazaként trükkös dolog lehet. Még akkor is, ha figyelmen kívül hagyja a rendet, a lehetséges készletek száma riasztóan növekszik.

Két értékű tömb [1, 2] esetén létrehozhat:

  • [] (üres készlet)
  • [1]
  • [2]
  • [1,2] (vagy [2,1])

Ha az ismétlések megengedettek (például [2, 2]), a növekedés még nagyobb. A bemeneti értékek számának növekedésével a megfelelő kimeneti készletek száma a tetőn hajt át!

Nevezzük a bemeneti értékek terméket és minden egyes kombinációja ezeket az értékeket a választás . Engedjünk meg több elemet is, mindegyiknek külön választási lehetősége van. Jó működő példa lenne a menü. Szimuláljuk a Ye Olde Ice Cream Shoppe étlapját , amely fagylalt, öntetek és szirup ízesítéseket kínál vásárlóinak.

A fagylalt ízei: CSOKOLÁD, Eper, VANILLA

Öntetek: ananász, eper, kókuszreszelék, pekándió

Szörpök: csokoládé, fehérmályva, vaj, juhar

Van néhány korlát a választás szempontjából: az ügyfelek tetszőleges két fagylaltot, két öntetet és egy szirupot választhatnak . A fagylalt és az öntet választása kizárólagos, vagyis például nem választhatok ananászt + ananászt. Az ügyfél dönthet úgy, hogy nincs öntete és nincs szirupja, de legalább egy fagylaltot kell választania. Ezekkel a megszorításokkal a növekedés mértéke exponenciális, a 2. nagyságrendtől az n-edik hatványig, ami lényegesen kisebb, mint ha a sorrend szignifikáns lenne, és megengednék az ismétléseket.

Ízlés

A Ye Olde Ice Cream Shoppe valójában meglehetősen modern az üzleti megközelítésben, és egy mesterséges intelligencia szakértői rendszert fejleszt ki annak megítélésére, hogy a fagylalt, az öntet és a szirup melyik kombinációja ízletes. A kiszolgálók figyelmeztetést kapnak a nyilvántartásukból, ha az ügyfél ízléstelen választást választ. A szervereket ezután arra utasítják, hogy még egyszer ellenőrizzék az ügyféllel, hogy megrendelésük helyes-e.

1. lépés: Az adatok felépítése

A cikk kódja itt található. Feltételezem, hogy ismeri a JavaScriptet és a Node.js. Hasznos a Lodash (vagy az Aláhúzás) ismerete. A kód egy térkép / kicsinyítés adatbázist használ tárolásra.

Az első lépés az összes fagylalt, öntet és szirup kombináció adatbázisának létrehozása lesz. A bemenetek a következők lesznek:

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"]} }

Ezekkel az adatokkal írhatok egy Combinator függvényt, amely felveszi az egyes menüpontokat, és minden lehetséges kombinációt generál. Minden kombinációt tömbként tárolunk. A fagylaltkombinációk például a következőképpen néznének ki:

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

Miután meghatároztuk a fagylalt, az öntetek és a szirupok kombinációit, már csak az összes tételkombinációt kell megismételni a többivel:

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

Így jégkrém (ek), feltét (ek) és szirup kombinációját kapjuk, például:

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

A bemutatott választások a következők:

  • Vanília fagylalt kókuszreszelékkel és pekándióval, szirup nélkül
  • Vanília fagylalt kókuszreszelékkel és csokoládé sziruppal
  • Vanília fagylalt kókuszreszelékkel és fehérmályva sziruppal

Csak néhány korlátozott menüpont mellett a megengedett választások száma 330!

2. lépés: Az adatok tárolása

A megrendelhető cikkek minden kombinációjának meghatározásával további munkát lehet elvégezni. Az ízletes választási kombinációk meghatározására szolgáló AI rendszer bonyolultnak bizonyul, és nem kerül beágyazásra a regiszterek operációs rendszerébe. Ehelyett egy AJAX kérést fognak küldeni az AI programot tartalmazó kiszolgálónak. A bemenetek az ügyfél menüpontjai lesznek, a kimenet pedig az alábbiak egyikének minősíti a választás ízét: [ugh, meh, finom, fenséges]. Az ugh ízletes besorolása kiváltja a fent említett figyelmeztetést.

Gyors válaszra van szükségünk a megkeresésre, ezért az ízesítési minősítéseket egy adatbázis tárolja. Az exponenciális növekedés jellegét figyelembe véve ez Big Data problémává válhat, ha a jövőben több elemválasztás kerül a menübe.

Tegyük fel, hogy úgy döntöttek, hogy a választási kombinációkat és értékeléseket egy NoSQL adatbázisban tárolják. A PouchDB használatával az egyes választási lehetőségek és ízletes értékek JSON-dokumentumokként kerülnek tárolásra. A másodlagos index (más néven nézet ) minden egyes választáshoz kulcsként lehetővé teszi számunkra, hogy gyorsan megkereshessük az ízletes minősítést. Ahelyett, hogy az adatokat egy allChoices tömbbe tolnám, amint az a buildChoices.js-ben fent látható, a JSON-dokumentumokat az adatbázisba tudom tárolni.

Naivan haladva néhány változtatást tudok végrehajtani a Step1.js-ben, hogy megérkezhessek a Step2.js-re: először is telepítenem kell a PouchDB-t az npm-en keresztül, majd megkövetelem. Ezután létrehozok egy NoSQL adatbázist, amelyet választásoknak hívnak .

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

Most minden választás felkerül a választási adatbázisba:

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??');

Ez működik! Fajta. Amint arra a db.post visszahívási paramétere következtethet , ez a művelet aszinkron. Amit a naplóban látunk:

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

Tehát a kód szerint az még az 1. rekord tárolása előtt megtörtént. Ez akkor jelent problémát, ha további feldolgozásra van szükségem az adatbázis ellen, és az összes rekord még nincs ott.

3. lépés: Javítás és finomítás

Van egy finomabb probléma is: az erőforrások potenciális kimerülése. Ha az adatbázis korlátozza az egyidejű kapcsolatok számát, akkor az egyidejű feladási kérelmek nagy száma csatlakozási időkorlátot eredményezhet.

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