javascript - 同时可能的唯一元素组合的输出数组

问题描述

我的应用程序引用了一个充当目录的数据库对象。如果用户拥有必要的组件，它是可以制作的物品目录。这是目录的一个小样本：

const itemCatalog = {
    "bramble_vest" : {
        "components" : [ "Chain Vest", "Chain Vest" ],
        "name" : "Bramble Vest"
    },
    "guardian_angel" : {
        "components" : [ "B.F. Sword", "Chain Vest" ],
        "name" : "Guardian Angel"
    },
    "hextech_gunblade" : {
        "components" : [ "B.F. Sword", "Needlessly Large Rod" ],
        "name" : "Hextech Gunblade"
    },
    "locket_of_the_iron_solari" : {
        "components" : [ "Chain Vest", "Needlessly Large Rod" ],
        "name" : "Locket of the Iron Solari"
    },
    "morellonomicon" : {
        "components" : [ "Giant's Belt", "Needlessly Large Rod" ],
        "name" : "Morellonomicon"
    },
    "sunfire_cape" : {
        "components" : [ "Chain Vest", "Giant's Belt" ],
        "name" : "Sunfire Cape"
    },
    "zekes_herald" : {
        "components" : [ "B.F. Sword", "Giant's Belt" ],
        "name" : "Zeke's Herald"
    }
}

当用户拥有任何给定项目的必要组件时，用户可以组装该项目。用户被任意随机授予组件，但用户如何接收组件与我的问题无关。只需将用户的组件放入客户端上的数组中，然后用于确定用户可以组装哪些项目即可：

let myComponents = [
    "B.F. Sword",
    "Chain Vest",
    "Giant's Belt",
    "Chain Vest",
    "Needlessly Large Rod"
]

我编写了一段代码，用于确定哪些项目可以使用myComponents. 这相当简单，即使它不是特别简洁或时尚。

myComponents使用此示例中的所有项目中列出的组件itemCatalog都是可能的。然而，它们不可能同时发生。这样做的原因当然是所有项目都没有足够的组件。

考虑到引用时的组件，我需要能够确定哪些项目同时可能的逻辑。输出应该是一个数组数组。每个内部数组将是同时可能的目录项的列表。在这种情况下，当前包含的组件如下所示：myComponentsitemCatalogmyComponents

[ 
    ["Bramble Vest", "Hextech Gunblade"], 
    ["Bramble Vest", "Morellonomicon"], 
    ["Bramble Vest", "Zeke's Herald"], 
    ["Guardian Angel", "Locket of the Iron Solari"], 
    ["Guardian Angel", "Morellonomicon"], 
    ["Guardian Angel", "Sunfire Cape"], 
    ["Hextech Gunblade", "Sunfire Cape"], 
    ["Locket of the Iron Solari", "Sunfire Cape"], 
    ["Locket of the Iron Solari","Zeke's Herald"]
]

以下是我目前的逻辑。那里有很多日志可以帮助筛选，但该功能的主要问题buildSimultaneousItems()是，一旦在迭代期间检查了一个项目与另一个项目，这两个项目就不会再次检查。我不想过多地涉及它，因为我不想用信息过载吓跑人们。这一切都非常简单，尽管它很丑陋。主要是预期的输出在上面。请随时提出问题。

// A catalog of items that can be assembled using components.
// The app uses this as a reference. This catalog is larger in the app, with many more items.
const itemCatalog = {
  "bramble_vest" : {
    "components" : [ "Chain Vest", "Chain Vest" ],
    "name" : "Bramble Vest"
  },
  "guardian_angel" : {
    "components" : [ "B.F. Sword", "Chain Vest" ],
    "name" : "Guardian Angel"
  },
  "hextech_gunblade" : {
    "components" : [ "B.F. Sword", "Needlessly Large Rod" ],
    "name" : "Hextech Gunblade"
  },
  "locket_of_the_iron_solari" : {
    "components" : [ "Chain Vest", "Needlessly Large Rod" ],
    "name" : "Locket of the Iron Solari"
  },
  "morellonomicon" : {
    "components" : [ "Giant's Belt", "Needlessly Large Rod" ],
    "name" : "Morellonomicon"
  },
  "sunfire_cape" : {
    "components" : [ "Chain Vest", "Giant's Belt" ],
    "name" : "Sunfire Cape"
  },
  "zekes_herald" : {
    "components" : [ "B.F. Sword", "Giant's Belt" ],
    "name" : "Zeke's Herald"
  }
}

// Components the user currently has
let myComponents = [
  "B.F. Sword",
  "Chain Vest",
  "Giant's Belt",
  "Chain Vest",
  "Needlessly Large Rod"
]

// Returns array of possible items with provided component combinations (myComponents)
getPossibleItems = (arr) => {
  let possibleItems = [];
  for (const possItem in arr) {
    if (doArraysMatch(arr[possItem].components, myComponents) ==  true) {
      possibleItems.push(arr[possItem].name);
    }
  }
  return possibleItems;
}

// Returns array of components at corresponding indices that correspond to the array returned in the above function
getPossItemsComponents = (arrA, arrB) => {
  let possItemsComponents = []
  for (const item in arrA) {
    for (const combItem in arrB) {
      console.log(arrB[combItem].name, ": ",arrB[combItem].components);
      if (arrA[item] == arrB[combItem].name) {
        possItemsComponents.push(arrB[combItem].components);
      }
    }
  }
  return possItemsComponents;
}

// Attempts to return an array of arrays. Each inner array is a list of items that can be
// assembled SIMULTANEOUSLY with the provided components (myComponents)
buildSimultaneousItems = () => {
  let terms = [];   
  possibleItems = getPossibleItems(itemCatalog);
  possibleItemsComponents = getPossItemsComponents(possibleItems, itemCatalog);
  for (let i = 0; i < possibleItems.length; i++) {
    let simultaneousItems = [];
    let simultaneousItemsComponents = [];
    simultaneousItems.push(possibleItems[i]);
    console.log(JSON.stringify(possibleItems[i]), ": ", JSON.stringify(possibleItemsComponents[i]), "-----------------------")
    simultaneousItemsComponents.push(possibleItemsComponents[i]);
    //console.log(possibleItemsComponents[i][0])
    for (let j = 0; j < possibleItems.length; j++) {
      console.log("Does myItems", JSON.stringify(myComponents), " contain ",JSON.stringify(simultaneousItemsComponents[0].concat(possibleItemsComponents[j])), " for ", JSON.stringify(possibleItems[j]),this.containsAllItems(myComponents, simultaneousItemsComponents[0].concat(possibleItemsComponents[j])))
      while (containsAllItems(myComponents, simultaneousItemsComponents[0].concat(possibleItemsComponents[j]))) {
        simultaneousItems.push(possibleItems[j]);
        console.log("Add ", JSON.stringify(possibleItemsComponents[j]), " to ", JSON.stringify(simultaneousItemsComponents[0]))
        simultaneousItemsComponents[0].push(possibleItemsComponents[j][0]);
        simultaneousItemsComponents[0].push(possibleItemsComponents[j][1]);
      }
    }
    terms.push(simultaneousItems);
  }
  console.log(terms)
}

// Utility functions for comparing arrays -------------------------- //

doArraysMatch = (subset, superset) => {
  const subsetCount = _.countBy(subset);
  const supersetCount = _.countBy(superset);
  return _.every(subsetCount, (count, value) => supersetCount[value] >= count);
}

containsAllItems = (arrA, arrB) => {
  arrA.forEach(elA => {
    if (arrB.includes(elA)) {
      arrB.splice(arrB.indexOf(elA), 1);
    }
  })
  if (arrB.length == 0) {
    return true;
  } else {
    return false;
  }
}

buildSimultaneousItems()

<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.10/lodash.min.js"></script>

标签： javascriptarraysrecursionset

解决方案

（注意：下面有一个更新版本来处理附加要求。）

这是另一种基于简单递归算法的方法：我们查看列表中的第一项，如果可以，我们将其与通过调用函数形成的每个结果与其余目标和列表组件减去制作此项目所需的组件。如果我们不能制作第一个项目，我们只需使用剩余的项目和完整的组件列表重复。当项目列表为空时，递归触底。要使用它，我们首先将您的目录转换为带有的数组Object.values，因为我们根本不需要您的对象键。

一旦我们找到了我们的集合，我们就会删除那些是另一个严格子集的集合。这是因为除了您想要的完整值之外，该collect函数还收集仍然可以包含其他值的集合。例如，使用您的上述数据，它收集[["Bramble Vest", "Hextech Gunblade"], ["Bramble Vest", "Morellonomicon"], ["Bramble Vest", "Zeke's Herald"], ["Bramble Vest"], ...]（还有十几个项目，其中许多包含单个组件。）请注意，第四个项目["Bramble Vest"]是前三个项目中每一个的严格子集。使用maximize，我们从结果中删除这些子集。

这种分解很有用，因为collect它自己表达了一个有用的算法。（实现仍然与您的结构相关，使用每个项目的components和name属性，但不难变得更通用。）该算法采用items，组件集合的集合，和components，组件的集合，并返回items可以使用该固定组件列表制作所有可能集合的列表。在此之上分层maximize为我们提供了您的目标和这个更通用的算法。据我所知，这也是一个更简单的算法。也许有人可以向我展示一个将这两个步骤合二为一的简化。

这是一个实现：

// utility functions
const dropFirst = (x, xs, i = xs .indexOf (x)) =>
  i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]

const dropEach = ([x, ...xs], ys) => 
  x == undefined ? ys : dropEach (xs, dropFirst (x, ys))

const canMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : false

const isSubset = (xs, ys) =>
  xs .every (x => ys .includes (x))

const maximize = (xs) => 
  xs .filter (x => ! (xs .some (y => x !== y && isSubset (x, y))))


// main function
const collect = ([x, ...xs], ys) => 
  x == undefined
    ? [[]]
  : canMake (x.components, ys)
    ? [
        ... collect (xs, dropEach (x .components, ys)) .map (coll => [x .name, ... coll]), 
        ... collect (xs, ys)
      ]
    : collect (xs, ys)


// public function
const simultaneousItems = (catalog, components) => 
  maximize (collect (Object.values(catalog), components))


// sample data
const itemCatalog = { bramble_vest: {components : [ "Chain Vest", "Chain Vest" ], name : "Bramble Vest"}, guardian_angel: {components : [ "B.F. Sword", "Chain Vest" ], name : "Guardian Angel"}, hextech_gunblade: {components : [ "B.F. Sword", "Needlessly Large Rod" ], name : "Hextech Gunblade"}, locket_of_the_iron_solari: {components : [ "Chain Vest", "Needlessly Large Rod" ], name : "Locket of the Iron Solari"}, morellonomicon: {components : [ "Giant's Belt", "Needlessly Large Rod" ], name : "Morellonomicon"}, sunfire_cape: {components : [ "Chain Vest", "Giant's Belt" ], name : "Sunfire Cape"}, zekes_herald: {components : [ "B.F. Sword", "Giant's Belt" ], name : "Zeke's Herald"}}

const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Needlessly Large Rod"]


// demo
console .log (
  simultaneousItems(itemCatalog, myComponents)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

我们从一组效用函数开始：

dropFirst删除值数组中第一次出现的值。例如，

//                          v------------ First 'bar'
dropFirst ('bar', ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) 
//=> ["foo", "baz", "qux", "bar", "bar", "corge"]
//          ^---------------------------- now missing

dropEvery扩展它以从主列表中删除每个值列表，使用dropFirst. 例如

//   will all be removed -----------v------v--------------------v              
dropEach (['bar', 'foo', 'bar'], ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) 
//=> ["baz", "qux", "bar", "corge"]

canMake报告我们是否可以根据手头的组件列出组件列表。例如，使用您的组件示例列表，
```
canMake (['B.F. Sword', 'Chain Vest']) (myComponents) //=> true
canMake (['B.F. Sword', 'Chain Vest', 'B.F. Sword']) (myComponents) //=> false
```
第一个有效，因为我们的组件中既有剑也有背心。第二个失败是因为我们只有一把剑。

我们可以使用许多其他技术来编写此函数。递归版本适合这些函数的其余部分，但我们也可以比较项目组件和可用组件之间相关字符串的计数。

（注意：如果我们为项目的组件和我们的整个组件列表都实现了 MultiSet/Bag 类型，那么前三个函数可能会容易得多。我不会在这里尝试，但它可能值得研究。）

isSubset简单地报告一个字符串数组是否是另一个字符串的子集。在这里，我们不关心多重性，因为我们的输出不包括我们任何一个项目的许多副本。
maximize上面讨论过。它从集合列表中删除列表中另一个集合的子集。

然后我们有我们的中心功能，

collect，它决定了我们的项目列表的哪些子集可以用我们的组件制作。该算法如上所述。

还有我们的公共包装函数，

simultaneousItems，它会调用Object.values您的输入以将其转换为有用的格式collect，然后将其和组件列表传递给collect，然后调用maximize结果。这个函数产生我认为你想要的输入。

这是提供的数据的输出：

[
  ["Bramble Vest", "Hextech Gunblade"],
  ["Bramble Vest", "Morellonomicon"],
  ["Bramble Vest", "Zeke's Herald"],
  ["Guardian Angel", "Locket of the Iron Solari"],
  ["Guardian Angel", "Morellonomicon"],
  ["Guardian Angel", "Sunfire Cape"],
  ["Hextech Gunblade", "Sunfire Cape"],
  ["Locket of the Iron Solari", "Sunfire Cape"], 
  ["Locket of the Iron Solari", "Zeke's Herald"]
]

如果我们在我们的组件列表中添加第二个“BF Sword”，我们会得到这个列表：

[
  ["Bramble Vest", "Hextech Gunblade", "Zeke's Herald"],
  ["Bramble Vest", "Morellonomicon"],
  ["Guardian Angel", "Hextech Gunblade", "Sunfire Cape"],
  ["Guardian Angel", "Locket of the Iron Solari", "Zeke's Herald"],
  ["Guardian Angel", "Morellonomicon"],
  ["Locket of the Iron Solari", "Sunfire Cape"]
]

这将是一个有趣的练习，collect变成一个更通用的函数，并且仍然易于使用来定义makeSimultaneous。如果这个通用问题是一个众所周知的问题，并且针对它进行了一些优化，我也不会感到惊讶。我也会对算法性能感到好奇。但那是另一天的事了。

还有一个合理的论点可以将您的输出转换为 Set of Sets 而不是数组数组。数组的顺序无关紧要，在任何这种情况下，Set 都是一种更合乎逻辑的数据结构。我可能不会这样做，因为它是合乎逻辑的，因为我仍然发现数组更容易使用。但值得考虑。

更新

OP 的评论描述了上述未满足的附加要求：我们收集的项目可能会多次出现。这对于了解相关底层游戏的人来说可能很清楚，但上面的代码并没有处理它。

此外，这不是一个简单的修复。上面的设计collect是选择是否收集提供的第一个项目（如果可能），然后在剩余的项目和用完该项目所需的组件后剩余的组件上重复。我没有看到简单的方法来改变它以允许多个副本。

所以这里是collect用现有的辅助函数和新的来支持它的混合重写：

// utility functions
const dropFirst = (x, xs, i = xs .indexOf (x)) =>
  i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]

const dropEach = ([x, ...xs], ys) => 
  x == undefined ? ys : dropEach (xs, dropFirst (x, ys))

const dropEachRepeatedly = (n, xs, ys) =>
  n == 0 ? ys : dropEach(xs, dropEachRepeatedly(n - 1, xs, ys))

const canMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : false

const howMany = (xs, ys) => 
  canMake (xs, ys)
    ? 1 + howMany (xs, dropEach(xs, ys))
    : 0

const range = (lo, hi) => Array .from ({length: hi - lo + 1}, (_, i) => i + lo)

const count = (xs) => 
  xs .reduce ((a, x) => ((a[x] = (a[x] || 0) + 1), a), {})

const isMultiSubset = (xs, ys, cx = count (xs), cy = count (ys)) =>
  Object .keys (cx) .every (x => cx [x] <= (cy [x] || 0))

const maximize = (xs) => 
  xs .filter (x => ! (xs .some (y => x !== y && isMultiSubset (x, y))))


// main function
const collect = ([x, ...xs], ys) => 
  x == undefined
    ? [[]]
    : range (0, howMany (x.components, ys)) .reverse() .flatMap(
        (n) => collect(xs, dropEachRepeatedly(n, x.components, ys)) .map (
          coll =>  [...Array(n).fill(x.name), ...coll]
        )
      )


// public function
const simultaneousItems = (catalog, components) => 
  maximize (collect (Object .values (catalog), components))


// sample data
const itemCatalog = { bramble_vest: {components : [ "Chain Vest", "Chain Vest" ], name : "Bramble Vest"}, guardian_angel: {components : [ "B.F. Sword", "Chain Vest" ], name : "Guardian Angel"}, hextech_gunblade: {components : [ "B.F. Sword", "Needlessly Large Rod" ], name : "Hextech Gunblade"}, locket_of_the_iron_solari: {components : [ "Chain Vest", "Needlessly Large Rod" ], name : "Locket of the Iron Solari"}, morellonomicon: {components : [ "Giant's Belt", "Needlessly Large Rod" ], name : "Morellonomicon"}, sunfire_cape: {components : [ "Chain Vest", "Giant's Belt" ], name : "Sunfire Cape"}, zekes_herald: {components : [ "B.F. Sword", "Giant's Belt" ], name : "Zeke's Herald"}}

// const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Needlessly Large Rod"]
const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Chain Vest", "Needlessly Large Rod", "Chain Vest"]


// demo
console .log (
  simultaneousItems (itemCatalog, myComponents)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

在我们的组件中再添加两个“Chain Vest”，我们现在得到这个结果：

[
    ["Bramble Vest", "Bramble Vest", "Hextech Gunblade"],
    ["Bramble Vest", "Bramble Vest", "Morellonomicon"],
    ["Bramble Vest", "Bramble Vest", "Zeke's Herald"],
    ["Bramble Vest", "Guardian Angel", "Locket of the Iron Solari"],
    ["Bramble Vest", "Guardian Angel", "Morellonomicon"],
    ["Bramble Vest", "Guardian Angel", "Sunfire Cape"],
    ["Bramble Vest", "Hextech Gunblade", "Sunfire Cape"],
    ["Bramble Vest", "Locket of the Iron Solari", "Sunfire Cape"],
    ["Bramble Vest", "Locket of the Iron Solari", "Zeke's Herald"],
    ["Guardian Angel", "Locket of the Iron Solari", "Sunfire Cape"]
]

和以前一样，collect是我们的主要功能，它simultaneousItems是一个简单的包装器，它在调用之前对输入进行按摩collect，然后maximize在结果上运行。

许多辅助函数是相同的。只是maximize变了。它现在依赖于isMultiSubset而不是isSubset（我们不再需要它。）但是我们还有一些额外的助手：

dropEachRepeatedly从另一个列表（我们的可用组件）中删除一个列表（这里是项目的组件）的多个副本
howMany报告可以从另一个列表的成员中复制多少个列表

range简单地生成一个整数范围。例如

range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

count计算列表中每个值的出现次数。例如

count (['a', 'b', 'a', 'c', 'b', 'd', 'b'])
//=> {a: 2, b: 3, c: 1, d: 1}

isMultiSubset报告一个多重集（这里表示为一个数组，但顺序无关紧要）是否是另一个多重集的子集。例如，['a' , 'b' , 'a']不是一个多子集，['a', 'b', 'c', 'd']因为第一个中有两个'a's，而第二个中只有一个。但它是一个多子集，['a', 'b', 'c', 'a']因为有足够多'a'的 s 和'b'可以绕过。因为我们现在允许在每个输出配置中使用多个组件副本，所以我们在进行最大化时需要使用它。

我们的 main 函数collect现在是这样工作的：如果我们的输入中没有项目，我们返回一个仅包含空数组的数组。如果我们这样做，我们关注第一个组件，计算它在我们的组件列表中出现的次数，然后对于从该数字到零的每个值，我们选择包含该项目的那么多副本，并在剩余的部分重复项目和组件减少了项目的组件列表的许多副本。我们只返回这个结果的扁平化版本。

这段代码很可能可以简化。我从我们已经拥有的东西开始，并从那里改变。通常这不会像我们从一开始就计划好的那样产生结果。但很多时候我们没有那种奢侈。

javascript - 同时可能的唯一元素组合的输出数组

问题描述

解决方案

更新

推荐阅读