Комбинаторни експлозии, обяснени със сладолед: как да добавите малко и да получите много

Нека изследваме забавния, контраинтуитивен свят на комбинаториката.

Комбинирането на стойности за формиране на набори от различни комбинации може да бъде сложно нещо. Дори ако пренебрегнете реда, броят на възможните набори нараства тревожно.

За масив от две стойности [1, 2] можете да генерирате:

  • [] (празен набор)
  • [1]
  • [2]
  • [1,2] (или [2,1])

Ако са позволени повторения ([2, 2] например), увеличението е още по-голямо. С увеличаване на броя на входните стойности, броят на съответните изходни комплекти изстрелва през покрива!

Нека наречем входните стойности на елементите и всяка комбинация от тези стойности на избор . Освен това, нека позволим множество елементи, всеки с различен избор. Добър работещ пример би било меню. Ще симулираме менюто на Ye Olde Ice Cream Shoppe , което предлага на своите клиенти комбинации от сладолед, топинги и аромати на сироп.

Ароматите на сладоледа са: ШОКОЛАД, ЯГОДА, ВАНИЛА

Топинги: ананас, ягода, кокосови люспи, пекани

Сиропи: шоколад, блат, масленица, клен

Има някои ограничения при избора: клиентите могат да изберат всеки два сладоледа, два топинга и един сироп. Изборът на сладолед и топинг е изключителен, което означава, че не мога да избера ананас + ананас, например. Клиентът може да избере да няма добавки и сироп, но трябва да избере поне един сладолед. При тези ограничения скоростта на нарастване е експоненциална, от порядъка 2 до n-та степен, което е значително по-малко, отколкото ако редът е значителен и се допускат дубликати.

Вкус

Ye Olde Ice Cream Shoppe всъщност е доста модерен в своя подход към бизнеса и разработва експертна система за изкуствен интелект, за да прецени кои комбинации от сладолед, топинг и сироп са вкусни. Сървърите ще получат предупреждение в своите регистри, когато клиентът избере неприятен избор. След това сървърите се инструктират да проверят два пъти с клиента дали поръчката им е правилна.

Стъпка 1: Изграждане на данните

Код за тази статия можете да намерите тук. Предполагам, че сте запознати с JavaScript и Node.js. Работното познаване на Lodash (или Underscore) е полезно. Кодът използва карта / намаляване на база данни за съхранение.

Първата стъпка ще бъде създаването на база данни за всички комбинации от сладолед, топинг и сироп. Входовете ще бъдат както следва:

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

С тези данни мога да напиша функция Combinator, която взема всеки елемент от менюто и генерира всички възможни разрешени комбинации. Всяка комбинация се съхранява като масив. Например, комбинациите от сладолед биха изглеждали така:

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

След като се определят комбинациите от сладолед, топинги и сиропи, остава само да се повтори всяка комбинация от артикули с останалите:

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

Това дава комбинация от сладолед (и), топинг (и) и сироп, като:

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

Показаният избор се превежда като:

  • Ванилов сладолед с кокосови люспи и пекани, без сироп
  • Ванилов сладолед с кокосови люспи и шоколадов сироп
  • Ванилов сладолед с кокосови люспи и блатен сироп

Дори само с няколко ограничени елемента от менюто, броят на разрешените възможности за избор е 330!

Стъпка 2: Съхраняване на данните

С всяка комбинация от поръчани елементи, определени сега, може да се извърши допълнителна работа. Системата AI за определяне на вкусни комбинации за избор се оказва сложна и няма да бъде вградена в операционната система на регистрите. Вместо това ще бъде направена AJAX заявка към сървър, в който се намира програмата AI. Входовете ще бъдат избора на менюто на клиента, а изходът ще оцени вкуса на тези избори като един от: [ъф, ме, вкусно, възвишено]. Класификацията на вкус от ugh задейства гореспоменатото предупреждение.

Нуждаем се от бърз отговор на заявката, така че оценките за вкус ще бъдат кеширани в база данни. Като се има предвид естеството на експоненциалното увеличение, това може да се превърне в проблем с големи данни, ако в бъдеще в менюто се добавят повече възможности за избор.

Let’s say it is decided to store choice combinations and ratings in a NoSQL database. Using PouchDB, each choice and palatability value are stored as JSON documents. A secondary index (a.k.a. view) with each choice as a key will allow us to quickly look up the palatability rating. Instead of pushing the data into an allChoices array as shown above in buildChoices.js, I can push JSON documents to the database for storage.

Proceeding naively, I can make a couple of changes in Step1.js to arrive at Step2.js: first of all, I need to install PouchDB via npm, then require it. Then, I create a NoSQL database called choices.

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

Now, each choice is posted to the choices database:

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

This works! Sort of. As can be inferred by the callback parameter to db.post, that operation is asynchronous. What we see in the log is:

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

So the code says it’s done before even record 1 has been stored. This will be a problem if I have further processing to do against the database and all the records aren’t there yet.

Step 3: Fixing and Refining

There’s also a more subtle problem: potential resource exhaustion. If the database limits the number of concurrent connections, a large number of simultaneous post requests may result in connection timeouts.

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