javascript递归骰子组合并将结果存储在矩阵中 [英] javascript recursive dice combination and store the result in a matrix
问题描述
我想要实现的是N-dices发布组合的经典结果之一,但是将结果保存在具有MN字段的矩阵中(其中N是骰子的数量,M是总数)可能组合的数量 - 通过6 ^ N获得。到目前为止,我已经编写了以下代码:
what I'm trying to achieve is one of the classical results of the combination of the launch of N-dices,but saving the results in a matrix with M-N fields (where N is the number of dices and M is the total number of possible combinations - obtained by 6^N). So far I've written the following code:
function Dice (commonFace, singleFace){
this.diceFaces = ["critical", commonFace, commonFace, singleFace, "support1", "support2"]
this.numCases = function(){
return Math.pow(this.diceFaces.length, numberDices)
}
}
//create the attack dice
var attackDice = new Dice("smash", "fury");
//create the defence dice
var defenceDice = new Dice("block", "dodge");
//create a function that rolls the dice results and returns the number of results results
function rollDiceResults(diceTypeRolled, numberDicesRolled) {
//total possible results of the rolls of that number of dices
var totalPossibilites = diceTypeRolled.numCases(numberDicesRolled);
//store the dice results
var diceResults = new Array;
function rollDice(diceType, iteration, array) {
if (iteration == 1) {
//return the base case
for (i = 0; i < diceType.diceFaces.length; i++) {
array[i] = (diceType.diceFaces[i]);
}
} else {
//continue
for (i = 0; i < diceType.diceFaces.length; i++) {
array[i] = diceType.diceFaces[i];
rollDice(diceType, iteration - 1, tempResult);
}
}
}
for (i = 0; i < numberDicesRolled; i++) {
rollDice(diceTypeRolled, numberDicesRolled, diceResults);
}
}
我得到的是
- 函数声明中的错误
- 我错过了如何调用数组在函数内部,同时保持mn结构
感谢您的帮助
推荐答案
固定长度组合
递归是一种功能性遗产,因此使用功能样式将产生最佳效果。递归就是将一个大问题分解为较小的子问题,直到达到基本情况。
Recursion is a functional heritage and so using it with functional style will yield the best results. Recursion is all about breaking a large problem down into smaller sub problems until a base case is reached.
下面,我们使用建议的 Array.prototype.flatMap
但是对于尚不支持它的环境包含polyfill。当 n = 0
我们的基本情况已经达到并且我们返回空结果。归纳案例是 n> 0
其中选项
将被添加到较小问题组合的结果中(选项,n - 1)
–我们说这个问题较小,因为 n - 1
更接近基本情况 n = 0
Below, we use the proposed Array.prototype.flatMap
but include a polyfill for environments that don't support it yet. When n = 0
our base case has been reached and we return the empty result. The inductive case is n > 0
where choices
will be added to the result of the smaller problem combination (choices, n - 1)
– We say this problem is smaller here because n - 1
is closer to the base case of n = 0
Array.prototype.flatMap = function (f)
{
return this.reduce ((acc, x) => acc.concat (f (x)), [])
}
const combinations = (choices, n = 1) =>
n === 0
? [[]]
: combinations (choices, n - 1) .flatMap (comb =>
choices .map (c => [ c, ...comb ]))
const faces =
[ 1, 2, 3 ]
// roll 2 dice
console.log (combinations (faces, 2))
// [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 1, 2 ], ..., [ 2, 3 ], [ 3, 3 ] ]
// roll 3 dice
console.log (combinations (faces, 3))
// [ [ 1, 1, 1 ], [ 2, 1, 1 ], [ 3, 1, 1 ], [ 1, 2, 1 ], ..., [ 2, 3, 3 ], [ 3, 3, 3 ] ]
在您的计划中使用组合
Using combinations
with your program
写 rollDice
看起来像这样
const rollDice = (dice, numberOfDice) =>
combinations (dice.diceFaces, numberOfDice)
console.log (rollDice (attackDice, 2))
// [ [ 'critical', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'fury', 'critical' ]
// , [ 'support1', 'critical' ]
// , [ 'support2', 'critical' ]
// , [ 'critical', 'smash' ]
// , [ 'smash', 'smash' ]
// , ...
// , [ 'critical', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'fury', 'support2' ]
// , [ 'support1', 'support2' ]
// , [ 'support2', 'support2' ]
// ]
没有依赖
如果你很好奇 flatMap
和 map
正在运行,我们可以自己实现它们。纯粹的递归,贯穿始终。
If you're curious how flatMap
and map
are working, we can implement them on our own. Pure recursion, through and through.
const None =
Symbol ()
const map = (f, [ x = None, ...xs ]) =>
x === None
? []
: [ f (x), ...map (f, xs) ]
const flatMap = (f, [ x = None, ...xs ]) =>
x === None
? []
: [ ...f (x), ...flatMap (f, xs) ]
const combinations = (choices = [], n = 1) =>
n === 0
? [[]]
: flatMap ( comb => map (c => [ c, ...comb ], choices)
, combinations (choices, n - 1)
)
const faces =
[ 1, 2, 3 ]
// roll 2 dice
console.log (combinations (faces, 2))
// [ [ 1, 1 ], [ 2, 1 ], [ 3, 1 ], [ 1, 2 ], ..., [ 2, 3 ], [ 3, 3 ] ]
// roll 3 dice
console.log (combinations (faces, 3))
// [ [ 1, 1, 1 ], [ 2, 1, 1 ], [ 3, 1, 1 ], [ 1, 2, 1 ], ..., [ 2, 3, 3 ], [ 3, 3, 3 ] ]
Nerfed
好的,所以组合
允许我们确定重复的固定选项的可能组合。如果我们有2个唯一的骰子并希望获得所有可能的掷骰怎么办?
Ok, so combinations
allows us to determine the possible combinations of a repeated, fixed set of choices. What if we had 2 unique dice and wanted to get the all the possible rolls?
const results =
rollDice (attackDice, defenceDice) ???
我们可以调用 rollDice(attackDice,1)
然后 rollDice(defenceDice,1)
然后以某种方式组合答案。但是有更好的方法;一种允许任意数量的独特骰子的方式,即使每个骰子上有不同数量的边。下面,我向您展示两个版本的组合
我们写了一些必要的更改来访问未开发的潜力
We could call rollDice (attackDice, 1)
and then rollDice (defenceDice, 1)
and then somehow combine the answers. But there's a better way; a way that allows for any number of unique dice, even with a varying number of sides on each die. Below, I show you the two versions of combinations
we wrote alongside the necessary changes to access untapped potential
// version 1: using JS natives
const combinations = (choices, n = 1) =>
const combinations = (choices = None, ...rest) =>
n === 0
choices === None
? [[]]
: combinations (choices, n - 1) .flatMap (comb =>
: combinations (...rest) .flatMap (comb =>
choices .map (c => [ c, ...comb ]))
// version 2: without dependencies
const combinations = (choices = [], n = 1) =>
const combinations = (choices = None, ...rest) =>
n === 0
choices === None
? [[]]
: flatMap ( comb => map (c => [ c, ...comb ], choices)
, combinations (choices, n - 1)
, combinations (...rest)
)
这个新版本的组合
,我们可以滚动任意数量的任意大小的骰子 - 即使是在这个程序中物理上不可能的3面骰子也可以^ _ ^
With this new version of combinations
, we can roll any number of dice of any size – even the physically impossible 3-sided die is possible in this program ^_^
// version 3: variadic dice
const combinations = (choices = None, ...rest) =>
choices === None
? [[]]
: flatMap ( comb => map (c => [ c, ...comb ], choices)
, combinations (...rest)
)
const d1 =
[ 'J', 'Q', 'K' ]
const d2 =
[ '♤', '♡', '♧', '♢' ]
console.log (combinations (d1, d2))
// [ [ 'J', '♤' ], [ 'Q', '♤' ], [ 'K', '♤' ]
// , [ 'J', '♡' ], [ 'Q', '♡' ], [ 'K', '♡' ]
// , [ 'J', '♧' ], [ 'Q', '♧' ], [ 'K', '♧' ]
// , [ 'J', '♢' ], [ 'Q', '♢' ], [ 'K', '♢' ]
// ]
当然你可以滚动一个同一个骰子的集合
And of course you can roll a collection of the same dice
console.log (combinations (d1, d1, d1))
// [ [ 'J', 'J', 'J' ]
// , [ 'Q', 'J', 'J' ]
// , [ 'K', 'J', 'J' ]
// , [ 'J', 'Q', 'J' ]
// , [ 'Q', 'Q', 'J' ]
// , [ 'K', 'Q', 'J' ]
// , [ 'J', 'K', 'J' ]
// , ...
// , [ 'K', 'Q', 'K' ]
// , [ 'J', 'K', 'K' ]
// , [ 'Q', 'K', 'K' ]
// , [ 'K', 'K', 'K' ]
// ]
利用您的程序挖掘这种潜力,您可以写 rollDice
作为
Tapping into this potential with your program, you can write rollDice
as
const rollDice = (...dice) =>
combinations (...dice.map (d => d.diceFaces))
console.log (rollDice (attackDice, defenceDice))
// [ [ 'critical', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'smash', 'critical' ]
// , [ 'fury', 'critical' ]
// , [ 'support1', 'critical' ]
// , [ 'support2', 'critical' ]
// , [ 'critical', 'block' ]
// , [ 'smash', 'block' ]
// , ...
// , [ 'support2', 'support1' ]
// , [ 'critical', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'smash', 'support2' ]
// , [ 'fury', 'support2' ]
// , [ 'support1', 'support2' ]
// , [ 'support2', 'support2' ]
// ]
或者各种骰子
const rollDice = (...dice) =>
combinations (...dice.map (d => d.diceFaces))
console.log (rollDice (defenceDice, attackDice, attackDice, attackDice))
// [ [ 'critical', 'critical', 'critical', 'critical' ]
// , [ 'block', 'critical', 'critical', 'critical' ]
// , [ 'block', 'critical', 'critical', 'critical' ]
// , [ 'dodge', 'critical', 'critical', 'critical' ]
// , [ 'support1', 'critical', 'critical', 'critical' ]
// , [ 'support2', 'critical', 'critical', 'critical' ]
// , [ 'critical', 'smash', 'critical', 'critical' ]
// , [ 'block', 'smash', 'critical', 'critical' ]
// , [ 'block', 'smash', 'critical', 'critical' ]
// , [ 'dodge', 'smash', 'critical', 'critical' ]
// , [ 'support1', 'smash', 'critical', 'critical' ]
// , ...
// ]
走高端
很高兴看到我们如何通过一些纯粹的成就来实现这一目标JavaScript中的函数。然而,上述实施是缓慢的,并且在它可以产生多少组合方面受到严重限制。
It's cool to see how we can accomplish so much with just a few pure functions in JavaScript. However, the above implementation is slow af and severely limited in terms of how many combinations it could produce.
下面,我们尝试确定七个六面骰子的组合。我们预计6 ^ 7会导致279936种组合
Below, we try to determine the combinations for seven 6-sided dice. We expect 6^7 to result in 279936 combinations
const dice =
[ attackDice, attackDice, attackDice, attackDice, attackDice, attackDice, attackDice ]
rollDice (...dice)
// => ...
取决于组合的实施
你选择上面,如果它不会导致你的环境无限期挂起,它将导致堆栈溢出错误
Depending on the implementation of combinations
you picked above, if it doesn't cause your environment to hang indefinitely, it will result in a stack overflow error
为了提高性能,我们达到了很高的水平Javascript提供的级别功能: generator 一>。下面,我们重写组合
,但这次使用了与生成器交互所需的一些命令式样式。
To increase performance here, we reach for a high-level feature provided by Javascript: generators. Below, we rewrite combinations
but this time using some imperative style required to interact with generators.
const None =
Symbol ()
const combinations = function* (...all)
{
const loop = function* (comb, [ choices = None, ...rest ])
{
if (choices === None)
return
else if (rest.length === 0)
for (const c of choices)
yield [ ...comb, c ]
else
for (const c of choices)
yield* loop ([ ...comb, c], rest)
}
yield* loop ([], all)
}
const d1 =
[ 'J', 'Q', 'K', 'A' ]
const d2 =
[ '♤', '♡', '♧', '♢' ]
const result =
Array.from (combinations (d1, d2))
console.log (result)
// [ [ 'J', '♤' ], [ 'J', '♡' ], [ 'J', '♧' ], [ 'J', '♢' ]
// , [ 'Q', '♤' ], [ 'Q', '♡' ], [ 'Q', '♧' ], [ 'Q', '♢' ]
// , [ 'K', '♤' ], [ 'K', '♡' ], [ 'K', '♧' ], [ 'K', '♢' ]
// , [ 'A', '♤' ], [ 'A', '♡' ], [ 'A', '♧' ], [ 'A', '♢' ]
// ]
以上,我们使用 Array.from
急切地将所有组合收集到一个结果
中。使用发电机时通常不需要这样做。相反,我们可以使用值作为生成它们
Above, we use Array.from
to eagerly collect all the combinations into a single result
. This is often not necessary when working with generators. Instead, we can use the values as they're being generated
下面,我们使用 for ... of
在发生器出来时直接与每个组合进行交互。在此示例中,我们显示任何包含 J
或♡
const d1 =
[ 'J', 'Q', 'K', 'A' ]
const d2 =
[ '♤', '♡', '♧', '♢' ]
for (const [ rank, suit ] of combinations (d1, d2))
{
if (rank === 'J' || suit === '♡' )
console.log (rank, suit)
}
// J ♤ <-- all Jacks
// J ♡
// J ♧
// J ♢
// Q ♡ <-- or non-Jacks with Hearts
// K ♡
// A ♡
但当然这里有更多的潜力。我们可以在中为
块写出我们想要的任何内容。下面,我们使用继续> c $ c>
But of course there's more potential here. We can write whatever we want in the for
block. Below, we add an additional condition to skip Queens Q
using continue
const d1 =
[ 'J', 'Q', 'K', 'A' ]
const d2 =
[ '♤', '♡', '♧', '♢' ]
for (const [ rank, suit ] of combinations (d1, d2))
{
if (rank === 'Q')
continue
if (rank === 'J' || suit === '♡' )
console.log (rank, suit)
}
// J ♤
// J ♡
// J ♧
// J ♢
// K ♡ <--- Queens dropped from the output
// A ♡
也许这里最强大的是我们可以停止与 break
生成组合。下面,如果遇到King K
,我们会立即停止发电机
And perhaps the most powerful thing here is we can stop generating combinations with break
. Below, if a King K
is encountered, we halt the generator immediately
const d1 =
[ 'J', 'Q', 'K', 'A' ]
const d2 =
[ '♤', '♡', '♧', '♢' ]
for (const [ rank, suit ] of combinations (d1, d2))
{
if (rank === 'K')
break
if (rank === 'J' || suit === '♡' )
console.log (rank, suit)
}
// J ♤
// J ♡
// J ♧
// J ♢
// Q ♡ <-- no Kings or Aces; generator stopped at K
你可以根据条件变得非常有创意。对于(const [a,b,c,d,e],在心中开始或结束的所有组合怎么样?
You can get pretty creative with the conditions. How about all the combinations that begin or end in a Heart
for (const [ a, b, c, d, e ] of combinations (d2, d2, d2, d2, d2))
{
if (a === '♡' && e === '♡')
console.log (a, b, c, d, e)
}
// ♡ ♤ ♤ ♤ ♡
// ♡ ♤ ♤ ♡ ♡
// ♡ ♤ ♤ ♧ ♡
// ...
// ♡ ♢ ♢ ♡ ♡
// ♡ ♢ ♢ ♧ ♡
// ♡ ♢ ♢ ♢ ♡
并显示生成器适用于大型数据集
And to show you generators work for large data sets
const d1 =
[ 1, 2, 3, 4, 5, 6 ]
Array.from (combinations (d1, d1, d1, d1, d1, d1, d1)) .length
// 6^7 = 279936
Array.from (combinations (d1, d1, d1, d1, d1, d1, d1, d1)) .length
// 6^8 = 1679616
我们甚至可以写得更高 - order函数用于生成器,例如我们自己的过滤器
函数。下面,我们找到三个20面骰子的所有组合,形成一个 Pythagorean triple - 3个整体构成有效直角三角形边长的数字
We can even write higher-order functions to work with generators such as our own filter
function. Below, we find all combinations of three 20-sided dice that form a Pythagorean triple - 3 whole numbers that make up the side lengths of a valid right triangle
const filter = function* (f, iterable)
{
for (const x of iterable)
if (f (x))
yield x
}
const d20 =
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]
const combs =
combinations (d20, d20, d20)
const pythagoreanTriple = ([ a, b, c ]) =>
(a * a) + (b * b) === (c * c)
for (const c of filter (pythagoreanTriple, combs))
console.log (c)
// [ 3, 4, 5 ]
// [ 4, 3, 5 ]
// [ 5, 12, 13 ]
// [ 6, 8, 10 ]
// [ 8, 6, 10 ]
// [ 8, 15, 17 ]
// [ 9, 12, 15 ]
// [ 12, 5, 13 ]
// [ 12, 9, 15 ]
// [ 12, 16, 20 ]
// [ 15, 8, 17 ]
// [ 16, 12, 20 ]
或使用 Array.from
,带有映射函数,可以将每个组合同时转换为新结果并收集数组中的所有结果
Or use Array.from
with a mapping function to simultaneously transform each combination into a new result and collect all results in an array
const allResults =
Array.from ( filter (pythagoreanTriple, combs)
, ([ a, b, c ], index) => ({ result: index + 1, solution: `${a}² + ${b}² = ${c}²`})
)
console.log (allResults)
// [ { result: 1, solution: '3² + 4² = 5²' }
// , { result: 2, solution: '4² + 3² = 5²' }
// , { result: 3, solution: '5² + 12² = 13²' }
// , ...
// , { result: 10, solution: '12² + 16² = 20²' }
// , { result: 11, solution: '15² + 8² = 17²' }
// , { result: 12, solution: '16² + 12² = 20²' }
// ]
功能是什么?
功能编程很深。潜入!
const None =
Symbol ()
// Array Applicative
Array.prototype.ap = function (args)
{
const loop = (acc, [ x = None, ...xs ]) =>
x === None
? this.map (f => f (acc))
: x.chain (a => loop ([ ...acc, a ], xs))
return loop ([], args)
}
// Array Monad (this is the same as flatMap above)
Array.prototype.chain = function chain (f)
{
return this.reduce ((acc, x) => [ ...acc, ...f (x) ], [])
}
// Identity function
const identity = x =>
x
// math is programming is math is ...
const combinations = (...arrs) =>
[ identity ] .ap (arrs)
console.log (combinations ([ 0, 1 ], [ 'A', 'B' ], [ '♡', '♢' ]))
// [ [ 0, 'A', '♡' ]
// , [ 0, 'A', '♢' ]
// , [ 0, 'B', '♡' ]
// , [ 0, 'B', '♢' ]
// , [ 1, 'A', '♡' ]
// , [ 1, 'A', '♢' ]
// , [ 1, 'B', '♡' ]
// , [ 1, 'B', '♢' ]
// ]
这篇关于javascript递归骰子组合并将结果存储在矩阵中的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!