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

Давайте дослідимо веселий, протиінтуїтивний світ комбінаторики.

Поєднання значень для формування наборів різних комбінацій може бути складною справою. Навіть якщо ви ігноруєте порядок, кількість можливих наборів тривожно зростає.

Для масиву з двох значень [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. Практичне знання Лодаша (або Підкреслення) є корисним. Код використовує карту / зменшити базу даних для зберігання.

Першим кроком буде створення бази даних усіх комбінацій морозива, доліва та сиропу. Вхідні дані будуть такими:

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 викликає вищезазначене попередження.

Нам потрібна швидка відповідь на запит, тому рейтинги смаку будуть кешовані в базі даних. З огляду на характер експоненціального збільшення, це може перерости в проблему великих даних, якщо в майбутньому до меню буде додано більше варіантів вибору.

Скажімо, вирішено зберігати комбінації та оцінки вибору в базі даних NoSQL. За допомогою PouchDB кожен вибір та значення смаку зберігаються як документи JSON. Вторинний індекс (інакше дивитися ) з кожним вибором в якості ключа дозволить швидко знайти рейтинг смакової привабливості. Замість надсилання даних у масив allChoices, як показано вище у buildChoices.js, я можу надсилати документи JSON до бази даних для зберігання.

Наївно продовжуючи, я можу зробити кілька змін у Step1.js, щоб перейти на Step2.js: перш за все, мені потрібно встановити PouchDB через npm, а потім вимагати цього. Потім я створюю базу даних NoSQL, яка називається вибір .

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

Тепер кожен вибір розміщується в базі даних про вибір:

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

Це працює! Типу. Як можна зробити висновок за параметром зворотного виклику до db.post , ця операція є асинхронною. Що ми бачимо в журналі:

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

Отже, код говорить, що це зроблено ще до того, як навіть запис 1 був збережений. Це буде проблемою, якщо мені доведеться провести подальшу обробку щодо бази даних, і всі записи ще не там.

Крок 3: Фіксація та доробка

Є також більш тонка проблема: потенційне вичерпання ресурсів. Якщо база даних обмежує кількість одночасних з'єднань, велика кількість одночасних запитів на публікацію може призвести до таймаутів з'єднання.

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