This is the 113th original article without water. If you want to get more original articles, please search the public account to follow us. This article was first published in the blog: E-commerce minimum inventory – SKU and algorithm implementation

preface

At present, as long as there are commodities in the business of e-commerce platform, it is inevitable to encounter SKU functions. From theory to practice, from product creation to product purchase, this article will walk you through the implementation of SKU related “core algorithms”.

Let’s look at the actual scenario:

With the above specification selected pretreatment, it can help users intuitively understand whether goods can be purchased when buying goods.

In our actual development process, the product creation page will first carry out specification assembly, and the product purchase page will deal with the specification selection. Specification assembly can be combined into SKU set through specification. Specification selection can obtain inventory data amount according to specification content and calculate whether SKU can be selected. Both functions are indispensable in e-commerce process.

Assemble SKU practices

Property description

SKU as explained by Baidu Baike

  • A Stock Keeping Unit is sometimes referred to as a SKU in retail chains, defined as the smallest available Unit for Keeping inventory control, such as a SKU in textiles, usually indicating specification, color, style.

The business scenario

  • As long as the e-commerce related products, such as shopping APP, shopping website, etc., will encounter such a scene, each product corresponds to multiple specifications, users can choose the product they want according to different specifications combination. We use this feature a lot in our own lives.

With the above description, let’s relate the concept to the actual data. Let’s take 🌰 as an example:

Existing specifications

const type = ["Men's trousers"."Panty"]
const color = ["Black"."White"]
const size = ["S"."L"]
Copy the code

Then according to the existing specifications, all SKUs can be obtained as follows:

[["Men's trousers"."Black"."S"],
  ["Men's trousers"."Black"."L"],
  ["Men's trousers"."White"."S"],
  ["Men's trousers"."White"."L"],
  ["Panty"."Black"."S"],
  ["Panty"."Black"."L"],
  ["Panty"."White"."S"],
  ["Panty"."White"."L"]]Copy the code

Let’s take a look at the implementation ideas and calculate them through 🌰 above.

SKU combination implementation idea

The cartesian product

Let’s first look at the description of the Cartesian product

  • Cartesian product means in mathematics, two [sets]X å’Œ YOf Cartesian product, also known as [direct product], expressed asX × YThe first object isXAnd the second object isYA member of all possible ordered pairs of
  • Assuming that set A = {A, b}, set b = {0, 1, 2}, the two sets of cartesian product for {(A, 0), (A, 1), (A, 2), (b, 0), (b, 1), (b, 2)}

It seems that cartesian products satisfy the conditions of combinatorial computation, so let’s do a little bit of thinking collision, let’s do a little bit of mapping, how do we do that

From the mind map above, you can see that this combination of specifications is a classic permutation to combine each specification into a final SKU.

So let’s do the code and see how the code implements the Cartesian product.

The implementation code

 /** * Cartesian product assembly *@param {Array} list
 * @returns [] * /
function descartes(list) {
  // parent upper index; Count pointer count
  let point = {}; // Ready to move pointer
  let result = []; // Prepare to return data
  let pIndex = null; // Prepare the parent pointer
  let tempCount = 0; // Each layer pointer coordinates
  let temp = []; // Assemble as an SKU result

  // generate a pointer object based on the parameter column
  for (let index in list) {
    if (typeof list[index] === 'object') {
      point[index] = { parent: pIndex, count: 0}; pIndex = index; }}// Single-dimensional data structures are returned directly
  if (pIndex === null) {
    return list;
  }

  // Dynamically generate cartesian product
  while (true) {
    // Two: generate a result
    let index;
    for (index in list) {
      tempCount = point[index].count;
      temp.push(list[index][tempCount]);
    }
    // Press into the result array
    result.push(temp);
    temp = [];

    // check the maximum value of pointer and move pointer
    while (true) {
      if (point[index].count + 1 >= list[index].length) {
        point[index].count = 0;
        pIndex = point[index].parent;
        if (pIndex === null) {
          return result;
        }
        // Assign parent to check again
        index = pIndex;
      } else {
        point[index].count++;
        break; }}}}Copy the code

Let’s look at the actual input, output and call results.

So that solves the classic permutation and combination problem. Next, let’s take a look at how to deal with multiple specifications in the purchase of goods.

Product specifications to choose

Review the usage scenarios before you begin

This picture clearly shows the business requirements. Combined with the above GIF, it can be seen that after the user selects a certain specification each time, other specifications need to be processed through the calculation of the program, so as to provide the user with other specifications available for selection under the current situation.

So let’s take a look at the implementation approach, first in the initialization, provide alternative SKU, go out from the optional SKU does not contain the specifications of the content, after excluding, offer to the next step selection of specifications, the subsequent in every time a user clicks cases, treatment may be selected SKU, finally after completion of the full specifications to choose, Gets the selected SKU.

Commodity multi – specification choice realization idea

Adjacency matrix

First of all, what is an adjacency matrix

  • Data about the relationships between vertices (edges or arcs) is stored in a two-dimensional array called an adjacency matrix.
  • The logical structure is divided into two parts: the set V and E, where V is the vertex and E is the edge. Therefore, a one-dimensional array is used to store all the vertex data in the graph.

If two vertices are connected to each other, the value of their corresponding subscript is 1; otherwise, it is 0.

Let’s continue with the previous 🌰 data

specifications

const type = ["Men's trousers"."Panty"]
const color = ["Black"."White"]
const size = ["S"."L"]
Copy the code

Assume that the total SKU inventory value is the following example, which can be selected as inventory, but cannot be selected as no inventory for a specification

[["Men's trousers"."Black"."S"]./ / S no. No
  ["Men's trousers"."Black"."L"],
  ["Men's trousers"."White"."S"]./ / S no. No
  ["Men's trousers"."White"."L"],
  ["Panty"."Black"."S"]./ / S no. No
  ["Panty"."Black"."L"],
  ["Panty"."White"."S"]./ / S no. No
  ["Panty"."White"."L"]]Copy the code

Then, according to the idea of adjacency matrix, the resulting graph can be obtained:

As shown in the figure, if two SKU specifications can be selected, the corresponding flag value is 1; otherwise, the flag value is 0. When all SKU specifications are selected, the entire SKU link is available.

The idea is to have, but how to achieve it through the code, presumably we also have a variety of ways to achieve, so I will introduce their own way of implementation: collection.

method

A collection of

High school for many years past, it is hard to forget, here through the set illustration diagram review the definition of the set

The image above is from Baidu Photo

Think of set, then we have the calculation idea, here we need to use the set equal situation, to deal with the CALCULATION of SKU and specification value.

Implement mind mapping

  • Suppose A set A{A, b, c} and another set b {A, e}, how to quickly determine whether B is A subset of A. The easy way to do this is to compare all elements in B with elements in A, and for each element in the set, the value of each element is unique. So with this property, we can convert all letters to A prime number, so the set A can be represented as the product of the set elements **, B and again, ** is B A subset of A, so we just divide B by A to see if it’s divisible, and if it is, then B is A subset of A.
  • So according to the adjacency matrix idea, the entire SKU will have oneThe set values, set values corresponding to all involved specificationsThe product ofThe result is that in the process of selecting specifications, the set value is reversed and divisible by the corresponding specification value to determine whether it is a subset and whether it is 1.
  • Now according to the multiplication algorithm, with the above analysis, we can sort out the algorithm process:
    • Data preprocessing, all the specification content to be processed one by one corresponds to a non-repeating prime number, and the ITEM combination is converted into the product of each prime number
    • Scans all items based on the items that the user has selected, exits if the ITEM is already selected, and multiplies all selected items if not (because two items of the same category cannot appear in one combination). Therefore, the selected ITEM needs to be removed from the ITEM in the same category as the currently matched ITEM), which is the set B above
    • Divide and compare the product of the combination of set B and SKU (equivalent to set A above). If it is divided exactly, it exits. The currently matched SKU can be selected; if it is not matched until the end, the currently matched SKU cannot be selected.

Let’s look at the core code through the idea of collections.

The core code

Methods for calculating prime numbers:

/** * prepare prime *@param {Int} Num Range of prime numbers *@returns* /
getPrime: function (num) {
  // Start with the first prime number 2
  let i = 2;
  const arr = [];
  /** * check if it is prime *@param {Int} number
   * @returns* /
  const isPrime = (number) = > {
    for (let ii = 2; ii < number / 2; ++ii) {
      if (number % ii === 0) {
        return false; }}return true;
  };
  // The number of primes is sufficient to complete the return
  for (i; arr.length < total; ++i) {
    if(isPrime(i)) { arr.push(i); }}// Return the required prime number
  return arr;
}
// Display the input parameter and return result of the above GIF:
// getPrime(500) return==> 
// 0: (8) [2, 3, 5, 7, 11, 13, 17, 19]
// 1: (8) [23, 29, 31, 37, 41, 43, 47, 53]
// 2: (8) [59, 61, 67, 71, 73, 79, 83, 89]
// 3: (8) [97, 101, 103, 107, 109, 113, 127, 131]
// 4: (8) [137, 139, 149, 151, 157, 163, 167, 173]
// 5: (8) [179, 181, 191, 193, 197, 199, 211, 223]
// 6: (8) [227, 229, 233, 239, 241, 251, 257, 263]
Copy the code

After initialization, the first batch of adjacency matrix results are obtained:

/** * initialization, the format needs to compare data, and initialization is optional calculation */
init: function () {
  this.light = util.cloneTwo(this.maps, true);
  var light = this.light;

  // By default, each rule can be selected, that is, assigned to 1
  for (var i = 0; i < light.length; i++) {
    var l = light[i];
    for (var j = 0; j < l.length; j++) {
      this._way[l[j]] = [i, j];
      l[j] = 1; }}// Corresponding to the result value, here the data processing method corresponds to the mind map of the adjacency matrix
  // 0: (8) [1, 1, 1, 1, 1, 1, 1]
  // 1: (8) [1, 1, 1, 1, 1, 1, 1]
  // 2: (8) [1, 1, 1, 1, 1, 1, 1]
  // 3: (8) [1, 1, 1, 1, 1, 1, 1]
  // 4: (8) [1, 1, 1, 1, 1, 1, 1]
  // 5: (8) [1, 1, 1, 1, 1, 1, 1]
  // 6: (8) [1, 1, 1, 1, 1, 1, 1]

  // Get the set of every operable SKU prime
  for (i = 0; i < this.openway.length; i++) {
    // A single line of results:
    // this.openway[i].join('*') ==> eval(2*3*5*7*11*13*17*19)
    this.openway[i] = eval(this.openway[i].join(The '*'));
  }
  // return initializes to get the specification position. The specification is optional by default, and the set of primes corresponding to the specification of the SKU can be selected
  this._check();
}
Copy the code

Calculation optional method:

/** * Updates the adjacency matrix corresponding to the result value *@param {Boolean} IsAdd Whether to add status *@returns* /
_check: function (isAdd) {
  var light = this.light;
  var maps = this.maps;
  
  for (var i = 0; i < light.length; i++) {
    var li = light[i];
    var selected = this._getSelected(i);
    for (var j = 0; j < li.length; j++) {
      if(li[j] ! = =2) {
      // If you add a condition, select only the point where light is 1
        if (isAdd) {
          if (li[j]) {
            light[i][j] = this._checkItem(maps[i][j], selected); }}else {
          light[i][j] = this._checkItem(maps[i][j], selected); }}}}return this.light; },/** * Updates the adjacency matrix result value * to check for optional content@param {Int} Item Current specification prime *@param {Array} selected
 * @returns* /
_checkItem: function (item, selected) {
  // Get a selection of SKU contents
  var openway = this.openway;
  var val;
  // Get the set of selected specifications * the set of specifications value
  val = item * selected;
  // The SKU set can be reversed
  for (var i = 0; i < openway.length; i++) {
    this.count++;
    if (openway[i] % val === 0) {
      return 1; }}return 0;
}

Copy the code

Method for adding specifications:

/** Select optional specifications for post-processing *@param {array} point [x, y]
 */
add: function (point) {
  point = point instanceof Array ? point : this._way[point];
  // Get the prime content of the selected specification
  var val = this.maps[point[0]][point[1]].// Check whether it can be selected
  if (!this.light[point[0]][point[1]]) {
    throw new Error(
      'this point [' + point + '] is no availabe, place choose an other'
    );
  }
  // Check whether the selected content already exists in the selected content
  if (val in this.selected) return;
  
  var isAdd = this._dealChange(point, val);
  this.selected.push(val);
  // Change the corresponding data of the adjacency matrix to 2 to make it optional
  this.light[point[0]][point[1]] = 2;
  this._check(! isAdd); }Copy the code

Method for removing selected specifications:

/** * Removes the selected specifications *@param {Array} point 
 */
remove: function (point) {
  point = point instanceof Array ? point : this._way[point];
  // error tolerance
  try {
    var val = this.maps[point[0]][point[1]];
  } catch (e) {}

  if (val) {
    // In the selected content, locate to remove the specification prime
    for (var i = 0; i < this.selected.length; i++) {
      if (this.selected[i] == val) {
        var line = this._way[this.selected[i]];
        // The corresponding adjacency matrix content is updated to optional
        this.light[line[0]][line[1]] = 1;
        // Remove from selected content
        this.selected.splice(i, 1); }}// Recalculate
  this._check(); }}Copy the code

The overall code

The open source code will be available in mid-September. If necessary, please follow the wechat official number: Zhengcai Cloud Front End Team. Reply to SKU to obtain the open source address.

conclusion

It seems that the teacher did not deceive us, in the study of classical permutation and combination, adjacency matrix, set is still very useful. The classical permutation combination cartesian product idea does not need to memorize, through understanding can complete a large number of recursive tree. According to the adjacency matrix, the complexity of space can be simplified.

After reading this article, you will have a general understanding of the two algorithms for e-commerce specification processing.

reference

1. The above set calculation ideas refer to the literature, see the link for details.

2. Another way to realize regular matching is referred to in the literature, see the link for details.

3. Adjacency matrix ideas refer to the literature, see the link for details.

Recommended reading

What you need to know about project management

The most familiar stranger rC-form

How to build a build deployment platform suitable for your team

Let’s talk about Deno

Open source works

  • Political cloud front-end tabloid

Open source address www.zoo.team/openweekly/ (wechat communication group on the official website of tabloid)

, recruiting

ZooTeam, a young passionate and creative front-end team, belongs to the PRODUCT R&D department of ZooTeam, based in picturesque Hangzhou. The team now has more than 50 front-end partners, with an average age of 27, and nearly 30% of them are full-stack engineers, no problem in the youth storm group. The members consist of “old” soldiers from Alibaba and netease, as well as fresh graduates from Zhejiang University, University of Science and Technology of China, Hangzhou Electric And other universities. In addition to daily business docking, the team also carried out technical exploration and practice in material system, engineering platform, building platform, performance experience, cloud application, data analysis and visualization, promoted and implemented a series of internal technical products, and continued to explore the new boundary of front-end technology system.

If you want to change what’s been bothering you, you want to start bothering you. If you want to change, you’ve been told you need more ideas, but you don’t have a solution. If you want change, you have the power to make it happen, but you don’t need it. If you want to change what you want to accomplish, you need a team to support you, but you don’t have the position to lead people. If you want to change the pace, it will be “5 years and 3 years of experience”; If you want to change the original savvy is good, but there is always a layer of fuzzy window… If you believe in the power of believing, believing that ordinary people can achieve extraordinary things, believing that you can meet a better version of yourself. If you want to be a part of the process of growing a front end team with deep business understanding, sound technology systems, technology value creation, and impact spillover as your business takes off, I think we should talk. Any time, waiting for you to write something and send it to [email protected]