Kombinationseksplosioner forklaret med is: hvordan man tilføjer lidt og får meget

Lad os udforske den sjove, kontraintuitive verden af ​​kombinatorik.

At kombinere værdier til at danne sæt af forskellige kombinationer kan være en vanskelig ting. Selvom du ignorerer rækkefølge, vokser antallet af mulige sæt alarmerende.

For en matrix med to værdier [1, 2] kan du generere:

  • [] (tomt sæt)
  • [1]
  • [2]
  • [1,2] (eller [2,1])

Hvis gentagelser er tilladt (f.eks. [2, 2]), er stigningen endnu større. Når antallet af inputværdier stiger, skyder antallet af tilsvarende output-sæt gennem taget!

Lad os kalde inputværdierne poster og hver kombination af disse værdier et valg . Lad os desuden tillade flere emner, hver med forskellige valg. Et godt fungerende eksempel ville være en menu. Vi simulerer menuen fra Ye Olde Ice Cream Shoppe , der tilbyder sine kunder kombinationer af is, påfyldninger og sirupsmag.

Isens smagsvarianter er: CHOCOLATE, STRAWBERRY, VANILLA

Toppings: ananas, jordbær, kokosflager, pekannødder

Sirupper: chokolade, marshmallow, butterscotch, ahorn

Der er nogle begrænsninger for valgene: kunder kan vælge to is, to påfyldninger og en sirup. Valg af is og topping er eksklusive, hvilket betyder at jeg for eksempel ikke kan vælge ananas + ananas. Kunden kan vælge ikke at have nogen påfyldninger og ingen sirup, men skal vælge mindst en is. Med disse begrænsninger er stigningshastigheden eksponentiel, af rækkefølgen 2 til den niende magt, hvilket er betydeligt mindre end hvis ordren var signifikant og duplikater tilladt.

Velsmag

Ye Olde Ice Cream Shoppe er faktisk ret moderne i sin tilgang til forretning og udvikler et ekspertsystem for kunstig intelligens til at bedømme hvilke kombinationer af is, topping og sirup, der er velsmagende. Servere får vist en advarsel i deres registre, når en kunde vælger et ubehageligt valg. Serverne instrueres derefter i at dobbelttjekke med kunden, om deres ordre er korrekte.

Trin 1: Opbygning af data

Kode til denne artikel kan findes her. Jeg antager, at du er fortrolig med JavaScript og Node.js. En praktisk viden om Lodash (eller understregning) er nyttig. Koden bruger et kort / reducer database til lagring.

Det første trin vil være at oprette en database med alle kombinationer af is, topping og sirup. Indgangene vil være som følger:

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

Med disse data kan jeg skrive en Combinator-funktion, der tager hvert menupunkt og genererer alle mulige tilladte kombinationer. Hver kombination er gemt som en matrix. For eksempel ser iskombinationer ud:

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

Når kombinationerne af is, påfyldninger og sirupper er bestemt, er alt tilbage at gentage hver varekombination med de andre:

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

Dette giver en kombination af is (er), topping (er) og sirup, som:

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

De viste valg oversættes som:

  • Vanilleis med kokosflager og pekannødder, ingen sirup
  • Vanilleis med kokosflager og chokoladesirup
  • Vanilleis med kokosflager og marshmallowsirup

Selv med nogle få begrænsede menupunkter er antallet af tilladte valg 330!

Trin 2: Lagring af data

Med hver kombination af bestilte varer, der nu er bestemt, kan yderligere arbejde udføres. AI-systemet til bestemmelse af velsmagende valgkombinationer viser sig at være komplekst og vil ikke blive indlejret i registerets operativsystem. I stedet for sendes en AJAX-anmodning til en server, der huser AI-programmet. Indgangene vil være kundens menuvalg, og output vil bedømme, at disse valg er velsmagende : [uh, meh, velsmagende, sublim]. En velsmagervurdering på ugh udløser ovennævnte advarsel.

Vi har brug for et hurtigt svar på anmodningen, så klassificeringerne af velsmagelse caches i en database. I betragtning af arten af ​​eksponentiel stigning kan dette udvikle sig til at blive et Big Data-problem, hvis flere elementvalg tilføjes til menuen i fremtiden.

Lad os sige, at det er besluttet at gemme valgkombinationer og ratings i en NoSQL-database. Ved hjælp af PouchDB lagres hvert valg og spisestedsværdi som JSON-dokumenter. Et sekundært indeks (aka view ) med hvert valg som en nøgle giver os mulighed for hurtigt at slå op på velsmagens vurdering. I stedet for at skubbe dataene ind i et allChoices- array som vist ovenfor i buildChoices.js, kan jeg skubbe JSON-dokumenter til databasen til lagring.

Fortsat naivt kan jeg foretage et par ændringer i Step1.js for at nå frem til Step2.js: Først og fremmest skal jeg installere PouchDB via npm og derefter kræve det. Derefter opretter jeg en NoSQL-database kaldet valg .

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

Nu sendes hvert valg til valgdatabasen:

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

Dette fungerer! På en måde. Som det kan udledes af tilbagekaldsparameteren til db.post , er denne operation asynkron. Hvad vi ser i loggen er:

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

Så koden siger, at det er gjort, før selv post 1 er blevet gemt. Dette vil være et problem, hvis jeg har yderligere behandling at gøre mod databasen, og alle optegnelserne ikke er der endnu.

Trin 3: Fastsættelse og raffinering

Der er også et mere subtilt problem: potentiel ressourceudmattelse. Hvis databasen begrænser antallet af samtidige forbindelser, kan et stort antal samtidige postanmodninger resultere i timeouts for forbindelsen.

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

Det er det! Alt der er tilbage er at skrive klientsoftware, der indsender valg via AJAX og får en smagsværdi (velsmag) tilbage. Hvis det er uh , så kommer en advarsel op på registret.

I et efterfølgende indlæg forfinerer jeg algoritmen, der er brugt ovenfor. Tjek det ud!

Referencer

Eksponentiel vækst er ikke sej. Kombinatorisk eksplosion er.

Så meget af den tekniske industri er besat af eksponentiel vækst. Alt lineært er ved at dø eller har været død i årevis ...

www.torbair.com

Kombinationer og permutationsberegner

Find ud af, hvor mange forskellige måder du kan vælge emner på. For en grundig forklaring af formlerne besøg ...

www.mathsisfun.com