首页 » 技术分享 » deque冰淇淋_用冰淇淋解释组合爆炸：如何添加一点并获得很多

deque冰淇淋_用冰淇淋解释组合爆炸：如何添加一点并获得很多

　
评论关闭　758次浏览

deque冰淇淋

Let’s explore the fun, counter-intuitive world of combinatorics.

让我们探索组合学的有趣，违反直觉的世界。

Combining values to form sets of distinct combinations can be a tricky thing. Even if you ignore order, the number of possible sets grows alarmingly.

将值组合以形成不同组合的集合可能是一件棘手的事情。 即使您忽略顺序，可能的集合数量也会惊人地增加。

For an array of two values [1, 2], you can generate:

对于两个值[1、2]的数组，可以生成：

  • [] (empty set)

    [](空集)

  • [1]

    [1]

  • [2]

    [2]

  • [1,2] (or [2,1])

    [1,2](或[2,1])

If repeats are allowed ([2, 2] for example), the increase is even greater. As the number of input values increase, the number of corresponding output sets shoots through the roof!

如果允许重复(例如[2，2])，则增加幅度更大。 作为输入值的数量的增加，相应的输出组的数量通过屋顶枝条 ！

Let’s call the input values items and each combination of those values a choice. Furthermore, let’s allow for multiple items, each with distinct choices. A good working example would be a menu. We’ll simulate the menu of Ye Olde Ice Cream Shoppe, which offers its customers combinations of ice cream, toppings, and syrup flavors.

让我们将输入值项和这些值的每种组合称为choice 。 此外，让我们允许多个项目，每个项目都有不同的选择。 一个很好的工作示例是菜单。 我们将模拟Ye Olde Ice Cream Shoppe的菜单，该菜单向客户提供冰淇淋，浇头和糖浆口味的组合。

The ice cream flavors are: CHOCOLATE, STRAWBERRY, VANILLA

冰淇淋的口味有： 巧克力，草莓，香草

Toppings: pineapple, strawberry, coconut flakes, pecans

配料： 菠萝，草莓，椰子片，山核桃

Syrups: chocolate, marshmallow, butterscotch, maple

糖浆： 巧克力，棉花糖，奶油糖，枫糖

There are some constraints on the choices: customers can choose any two ice creams, two toppings, and one syrup. Ice cream and topping choices are exclusive, meaning that I can’t choose pineapple + pineapple, for instance. The customer may choose to have no toppings and no syrup, but must choose at least one ice cream. With these constraints, the rate of increase is exponential, of the order 2 to the nth power, which is considerably less than if order was significant and duplicates allowed.

选择上有一些限制：客户可以选择两种冰淇淋， 两种浇头和一种糖浆。 冰淇淋和浇头的选择是唯一的，例如，我不能选择菠萝+菠萝。 顾客可以选择没有馅料和糖浆，但是必须选择至少一种冰淇淋。 在这些约束下，增加的速率是指数级的，从2到n次方，这大大小于阶次为有效且允许重复的情况。

适口性 (Palatability)

Ye Olde Ice Cream Shoppe is actually quite modern in its approach to business, and is developing an artificial intelligence expert system to judge which combinations of ice cream, topping, and syrup are palatable. Servers will be shown a warning on their registers when a customer chooses an unpalatable selection. The servers are then instructed to double check with the customer that their order is correct.

Ye Olde冰淇淋专卖店的业务方式实际上很现代，并且正在开发一种人工智能专家系统，以判断哪种冰淇淋，馅料和糖浆组合是可口的。 当客户选择不受欢迎的选择时，服务器将在其寄存器上显示警告。 然后指示服务器与客户再次确认其订单正确。

步骤1：建立资料 (Step 1: Building the Data)

Code for this article can be found here. I will assume you’re familiar with JavaScript and Node.js. A working knowledge of Lodash (or Underscore) is helpful. The code uses a map/reduce database for storage.

可以在此处找到本文的代码。 我假设您熟悉JavaScript和Node.js。 对Lodash(或Underscore)有一定的了解。 该代码使用map / reduce数据库进行存储。

The first step will be to create a database of all ice cream, topping, and syrup combinations. The inputs will be as follows:

第一步将是创建一个包含所有冰淇淋，馅料和糖浆组合的数据库。 输入将如下所示：

With this data, I can write a Combinator function that takes each menu item and generates all possible permitted combinations. Each combination is stored as an array. For example, ice cream combinations would look like:

利用这些数据，我可以编写一个Combinator函数，该函数接受每个菜单项并生成所有可能的允许组合。 每个组合都存储为数组。 例如，冰淇淋组合看起来像： 

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

Once the combinations of ice cream, toppings, and syrups are determined, all that’s left is to iterate each item combination with the others:

一旦确定了冰淇淋，浇头和糖浆的组合，剩下的就是将每个组合与其他组合进行迭代：

This yields a combination of ice cream(s), topping(s), and syrup, like:

这将产生冰淇淋，浇头和糖浆的组合，例如： 

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

The choices shown translate as:

显示的选择翻译为：

  • Vanilla ice cream with coconut flakes and pecans, no syrup

    香草冰淇淋配椰子片和山核桃，无糖浆

  • Vanilla ice cream with coconut flakes and chocolate syrup

    香草冰淇淋配椰子片和巧克力糖浆

  • Vanilla ice cream with coconut flakes and marshmallow syrup

    香草冰淇淋配椰子片和棉花糖糖浆

Even with just a few restricted menu items, the number of permitted choices is 330!

即使只有几个受限制的菜单项，允许的选择数量也只有330个！

步骤2：储存资料 (Step 2: Storing the Data)

With every combination of orderable items now determined, further work can be done. The AI system for determining palatable choice combinations is turning out to be complex and won’t be embedded in the registers’ operating system. Instead, an AJAX request will be made to a server housing the AI program. The inputs will be the customer’s menu choices, and the output will rate the palatability of those choices as one of: [ugh, meh, tasty, sublime]. A palatability rating of ugh triggers the aforesaid warning.

现在确定了可订购物品的每种组合，便可以做进一步的工作。 用于确定可口选择组合的AI系统变得很复杂，并且不会嵌入寄存器的操作系统中。 相反，将向包含AI程序的服务器发出AJAX请求。 输入将是客户的菜单选项，输出将这些选项的可口性评定为以下各项之一： [ugh，meh，美味，崇高]。 适口性为ug会触发上述警告。

We need a fast response to the request, so the palatability ratings will be cached in a database. Given the nature of exponential increase, this could evolve to become a Big Data problem if more item choices are added to the menu in the future.

我们需要对请求的快速响应，因此可口性等级将被缓存在数据库中。 考虑到指数增长的性质，如果将来在菜单中添加更多的项目选择，则可能演变成大数据问题。

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.

假设决定将选择组合和等级存储在NoSQL数据库中。 使用PouchDB，每个选项和可口性值都存储为JSON文档。 以每个选择为键的二级索引 (又称view )将使我们能够快速查找适口性等级。 可以像上面在buildChoices.js中所示将数据推送到allChoices数组中一样 ，我可以将JSON文档推送到数据库中进行存储。

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.

幼稚地进行操作，我可以在Step1.js中进行一些更改，以达到Step2.js：首先，我需要通过npm安装PouchDB，然后再要求它。 然后，我创建一个名为choices的NoSQL数据库。 

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

Now, each choice is posted to the choices database:

现在，每个选择都将发布到选择数据库：

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:

这可行！ 有点。 可以通过db.post的callback参数推断出，该操作是异步的。 我们在日志中看到的是： 

>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.

因此，代码表示在存储记录1之前就已经完成。 如果我要对数据库做进一步的处理，而所有记录还没有，那将是一个问题。

步骤3：修正和完善 (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:

对于Step3.js ，我对Step2.js中编写的内容进行了一些错误修复，重新格式化和重构。 一个错误是每次运行都会向数据库中添加越来越多的记录，从而重复了以前的记录。 解决方案是销毁现有数据库，重新创建它，然后运行主程序： 

// 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):

下一步是添加存储的文档的运行计数，并在处理中发布请求，以便程序：1)知道何时存储了最后一个文档； 2)一次只能进行五个发布。 run()方法现在看起来像这样(有一些遗漏)：

The main changes to note are that:

需要注意的主要更改是：

  1. A postCount tracks how many posts are outstanding

    postCount跟踪有多少未完成的帖子

  2. An interval timer checks the postCount and will post and exit when post slots are available

    间隔计时器检查postCount ，并在有可用的发布槽时发布和退出

  3. a done() handler is called when all choices are stored

    存储所有选择时，将调用done()处理函数

步骤4：添加适口性 (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.

有了所有可能的菜单选项，我们现在可以让AI确定每个菜单的适口性。 目前，AI只是一个模拟，它为PouchDB中的每个文档记录分配随机值。 这些值将通过使用品味评分更新每个文档而存储在数据库中。

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'
*/

步骤5：查找可食性 (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:

我可以使用r.doc.choice作为键，但是数组具有顺序，并且如果稍后重新排列了步骤1中定义的菜单项，则顺序可能会更改。 键只是选择选择的标识符，不具有其自身的语义。 应该起作用的是：

  • flatten each r.doc.choice array,

    展平每个r.doc.choice数组，

  • 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:

但是，如果将来添加更多选择，则密钥长度可能超出数据库允许的限制。 代替使用所构造的密钥，可以将密钥散列用作真实密钥。 十六进制的SHA256哈希长度为64个字符，即使是四方选择，哈希冲突的可能性也基本上为零。 使用Node.js 加密模块和Lodash链，可以很容易地为选择编写哈希函数：

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:

将哈希添加到我们现有的文档中很简单，只需遍历每个数据库文档，计算其哈希并使用键值更新文档即可：

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

接下来，使用文档关键字字段作为索引来构建数据库视图； 我称它为选择 。

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:

对于任何文档键(选择数组的哈希)，我都可以通过视图选择找到它的味道。 现在一切就绪，可以确定客户的选择是ugh，meh，美味还是崇高 。 为了测试这一点，我们做出一些随机选择，看看是否可以找到口味：

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.

而已！ 剩下的就是编写客户端软件，该软件通过AJAX提交选择并获得回味(适口性)值。 如果是ugh ，则会在寄存器上显示警告。

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

指数增长并不酷。 组合爆炸是。 因此，许多技术行业都沉迷于指数增长。 线性的一切即将消亡，或者已经死亡多年…… www.torbair.com

Combinations and Permutations CalculatorFind out how many different ways you can choose items. For an in-depth explanation of the formulas please visit…www.mathsisfun.com

组合和排列计算器 查找选择项目的方式有几种。 有关公式的详细说明，请访问…… www.mathsisfun.com

翻译自: https://www.freecodecamp.org/news/combinatorics-handle-with-care-ed808b48e5dd/

deque冰淇淋

转载自原文链接, 如需删除请联系管理员。

原文链接：deque冰淇淋_用冰淇淋解释组合爆炸：如何添加一点并获得很多，转载请注明来源！

赞 0