javascript - 将一系列数字的每种可能组合分配给变量

Question

给定一个数字范围(1-25)，如何创建一个循环，以便在每次迭代时获得一组唯一的变量。

举个例子，如果我用 4 个数字来做，我的变量将是: 在循环 1 上:

a = 1，b = 2，c = 3，d = 4，

在循环 2 上:

a = 1、b = 2、c = 4、d = 3

等等

我想做的是迭代每个位置的每个可能的数字(想想数独) 所以在 3x3 网格中:a = 左上角位置，b = 顶部中间位置，等等...

与数独非常相似，我有一个条件(每行 = 65:a + b + c + d + e= 65)

所以我想做的是有一个循环，我可以将所有值分配给变量:

for (something) {
   var topLeft = (determined from loop)
   var nextPosition = etc.

我的解决方案目前是这样的:

var numbers = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25];
var a,b,c,d,e,f,g,h,i,j,k,l,n,o,p,q,r,s,t,u,v,w,x,y;
var vars = [a,b,c,d,e,f,g,h,i,j,k,l,n,o,p,q,r,s,t,u,v,w,x,y];
var counter = 0;
var found = false;
while(found == false) {
for (var asdf = numbers, i = asdf.length; i--; ) {
    var random = asdf.splice(Math.floor(Math.random() * (i + 1)), 1)[0];
    vars[i] = random;
}
if (
    {a+b+c+d+e = 65,
    f+g+h+i+j = 65,
    k+l+1+n+o = 65,
    p+q+r+s+t = 65,
    u+v+w+x+y = 65,
    a+f+k+p+u = 65,
    b+g+l+q+v = 65,
    c+h+1+r+w = 65,
    d+i+n+s+x = 65,
    e+j+o+t+y = 65,
    u+q+1+i+e = 65,
    a+g+1+s+y = 65}
) {
    console.log(a,b,c,d,e,f,g,h,i,j,k,l,n,o,p,q,r,s,t,u,v,w,x,y);
    found = true;
}
counter++;
}

然而，明显的问题是它只是随机选择值。因此，这将花费令人难以置信的时间。我无法弄清楚如何迭代每个可能的组合(没有 25 个 for 循环)，因此我可以检查哪些值将通过条件。

Answer 1

Given a range of numbers (1-25) how can I create a loop so that at each iteration I get a unique set of variables.

听起来您正在谈论 permutations of a set 。您可以找到许多不同的算法来执行此操作。这是 this StackOverflow answer 中的一篇不错的文章:

function getArrayMutations(arr, perms = [], len = arr.length) {
  if (len === 1) perms.push(arr.slice(0))

  for (let i = 0; i < len; i++) {
    getArrayMutations(arr, perms, len - 1)

    len % 2 // parity dependent adjacent elements swap
      ? [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]]
      : [arr[i], arr[len - 1]] = [arr[len - 1], arr[i]]
  }

  return perms
}

getArrayMutations([1, 2, 3])
> [ [ 1, 2, 3 ],
    [ 2, 1, 3 ],
    [ 3, 1, 2 ],
    [ 1, 3, 2 ],
    [ 2, 3, 1 ],
    [ 3, 2, 1 ] ]

不过要小心!排列是阶乘，这意味着它们增长得非常快。

P(n, k) =

这意味着，如果您想要排列 25 个数字，那么您正在寻找 1.551121e+25 可能的组合，这将进入您一生中无法计算的领域。

What I am trying to do is iterate over every possible number for each position (think sudoku) so in a 3x3 grid: a = top left position, b = top middle, etc...

二维数组(实际上只是列表的列表)是存储此类矩阵数据的好方法。改变单个数组的表示形式并不会从根本上改变数学，但它可能更容易思考。我不能 100% 确定您想要 3x3 网格还是 5x5 网格，但我会假设 5x5，因为您的示例中有 25 个数字。您可以像这样轻松地 reshape 它们:

function reshapeArray(array, n=5) {
    let result = []
    let row = 0
    let col = 0
    for (let i = 0; i < array.length; i++) {
        if (col == 0) {
            result[row] = []
        }
        result[row][col] = array[i]
        col++
        if (col == n) {
            col = 0
            row++
        }
    }

    return result
}

reshapeArray([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25])
> [ [  1,  2,  3,  4,  5 ],
    [  6,  7,  8,  9, 10 ],
    [ 11, 12, 13, 14, 15 ],
    [ 16, 17, 18, 19, 20 ],
    [ 21, 22, 23, 24, 25 ] ]

so similar to sudoku I would have a condition (each row = 65: a + b + c + d + e= 65)

现在您已将数据存储在可迭代数组中，您可以非常轻松地检查此约束或任何其他约束。例如:

/**
 * Checks if a matrix (a 2-d array like the output from reshapeArray())
 * meets our criteria.
 */
function checkMatrix(matrix) {
    for (let row = 0; row < matrix.length; row++) {
        let rowSum = 0
        for (let col = 0; col < matrix[row].length; col++) {
            rowSum += matrix[row][col]
        }
        // The row sum does not equal 65, so this isn't the one!
        if (rowSum != 65) {
            return false
        }
    }
    // All the row sums equal 65
    return true
}

如果您想添加额外的规则(例如让列的总和为 65)，只需修改代码来检查即可。您可以通过索引matrix[row][col]来获取矩阵中任意点的值，因此matrix[0][0]是左上角，等等.

However the obvious problem with this is that it's just randomly selecting values. So it will take an incredible amount of time. I can't work out how to iterate over every possible combination (without having 25 for loops) so I can check which values will pass the condition.

是的，会的。数独是 NP-Hard problem 。如果您以前没有见过复杂性类，那么这只是一种非常数学形式化的说法，没有比仅检查每个可能的解决方案更快的聪明解决方案。这个假设的问题并不完全相同，所以它可能是可能的，但它有一种非常 np 的感觉。

目前，您的伪代码解决方案如下所示:

let permutations = getPermutations() // You're going to need to change this part
                                     // because getting all the permutations
                                     // ahead of time will take too long.
                                     // Just picking random numbers each time is
                                     // not actually a terrible idea. Or, look at
                                     // generator functions (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators)
for (let permutation of permutations) {
    let matrix = reshapeArray(permutation)
    if (checkMatrix(matrix)) {
        console.log("Found it")
        console.log(matrix)
        break
    }
}

如果只有一种可能的解决方案符合您的标准，您将永远不会以这种方式找到它。如果解决方案的密度相对较高，您可能会找到一些。如果你真的想解决这个问题，我建议你首先从数学 Angular 来看它——你能证明它是或不是 NP 吗？你能对解的密度做出一些预测吗？