在 Javascript 中寻找期权排列算法。也许…？

Question

我不知道该怎么称呼这类问题，因此找不到可靠的例子。我正在用 JS 编写，但是伪代码算法是一个很好的解决方案。

说我想要一篮子 3 件商品。篮子里有牙膏、牙刷和小苏打。我有三个可能的供应商可供选择，我可以从不同的供应商处选择每件商品。

我将价格数据存储在二维数组中，如下所示：

productVendors = [
    [3,6,2],
    [9,4,5],
    [1,3,4]
];

其中每一行是不同的供应商，每一列是特定的产品。 col1 = toothpaste、col2 = toothbrush、col3 = baking soda，例如

productVendors[0][0] = 3代表第一个供应商的牙膏价格。

我需要一个算法，returns n 个特定商品的每个可能篮子，来自 n 个供应商。生成的篮子将包含其中每个项目的坐标，而不是价格，如下所示：

           //item1   //item2    //item3
basket1 = [{x:0,y:0}, {x:1,y:1}, {x:2,y:2}];
basket2 = [{x:2,y:0}, {x:0,y:1}, {x:1,y:2}];
…

allBaskets = [basket1, basket2, basket3, etc…];

这个java论坛有一个几乎相同的问题正在解决，但我不明白。

算法： https://www.java-forums.org/advanced-java/81134-optimise-recursive-method-prints-all-possible-rows-2d-array.html#post351752

使用示例： https://www.java-forums.org/advanced-java/81134-optimise-recursive-method-prints-all-possible-rows-2d-array.html#post351876

我想完全理解一个解决方案，而不仅仅是有一些有用的东西。第一次在这里提问，多谢指教

Answer 1

假设有n个供应商和n个商品我认为每件商品应该来自不同的供应商。这可以按如下方式完成：

有一个递归函数 gen(n, arr)，其中 arr 是部分生成的 basket
if arr.length 等于 n - 将 arr 推入篮子列表和来自函数
在函数内部你应该迭代每个项目 id (i) 如果 arr 不包含它 - 去 gen (n, [...arr, {x: arr.length, y: i}])。这将添加一对，代表您从下一个供应商处获得的物品（供应商 ID arr.length）
要检查id是否已经在你可以做如下：arr.filter(item => (item.y == id)).length > 0

Answer 2

您的输出似乎包含具有 3 个可变组件的对象，这些组件可以采用 n 值：

篮子数组中的位置，
x 坐标，
y 坐标

在评论中您解释说您期望 nⁿ 解决方案，因此这意味着 3 个组件之一是重复的。看起来所需结果中的 y 坐标和索引是那些重复项：在您的示例中，它们始终相同。

所有 nⁿ 重复排列

这归结为生成所有可能的大小为 n 的列表，这些列表可以用 n 值制作，允许重复。所有商品都必须在一个购物篮中，并且每个商品只能出现一次，但并非所有供应商都必须由他们代表：购物篮中可能有两个或更多商品来自同一供应商。

您可以为此使用递归算法。在每个递归级别，我们确定一个特定项目的供应商。为它迭代所有可能的供应商。对于其中的每一个，都会进行递归调用以对以下所有项目执行相同的操作，从而生成所有可能性：

    function* permutations(n) {
        // Produce array [0, ..., n-1]
        const arr = [...Array(n).keys()];

        function* generate(n) {
            if (n < 0) {
                yield [...arr]; // a copy of arr
            } else {
                for (let i = 0; i < arr.length; i++) {
                    arr[n] = i;
                    yield* generate(n - 1);
                }
            }
        }

        yield* generate(n - 1);
    }

// Sample call for n=4
for (let arr of permutations(4)) {
    // output permuted arrays as x-y pairs:
    console.log(JSON.stringify(arr.map( (x, y) => ({ x, y }))));
    // For normal permutation view (without y), replace above line with following:
    // console.log(JSON.stringify(arr));
}

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

上述实现使用了一些 ES6 特性，例如扩展语法（获取可迭代对象的数组副本）、解构（用于交换）和生成器。生成器 (function*) returns 一个迭代器，它在产生排列时提供排列。

在这个答案的第一个版本中，我了解到一个购物篮中不能有重复的供应商。这导致了一个纯排列问题：

所有 n! 排列无重复

如果所有供应商都必须出现在每个购物篮中，那么这就变成了一个简单的排列问题。

为了生成排列，有几种有效的算法，例如 Heap's Algorithm:

function* permutations(n) {
    // Produce array [0, ..., n-1]
    const arr = [...Array(n).keys()];
    
    function swap(i, j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }

    function* generate(n) {
        if (n < 2) {
            yield [...arr]; // a copy of arr
        } else {
            for (let i = 0; i < n - 1; i++) {
                yield* generate(n - 1);
                swap(n%2 ? 0 : i, n - 1);
            }
            yield* generate(n - 1);
        }
    }

    yield* generate(n);
}

// Sample call for n=4
for (let arr of permutations(4)) {
    // output permuted arrays as x-y pairs:
    console.log(JSON.stringify(arr.map( (x, y) => ({ x, y }))));
    // For normal permutation view (without y), replace above line with following:
    // console.log(JSON.stringify(arr));
}

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

Heap 的算法很晦涩，但他找到了一种模式，select 一个元素与最后一个元素交换，通过递归产生下一组排列：

使用递归生成前 n-1 个元素的 (n-1)! 排列，将最后一个元素附加到这些 n-1 大小的排列中的每一个。这将生成以最后一个元素结尾的所有 n 大小排列。
如果n是奇数，取第一个元素，否则取i^th元素，并将其与最后一个元素交换。
对范围在0到n-2之间的i重复前两步，并再次执行步骤1。

在第 2 步中，似乎总是来回交换相同的两个值（因为 n 在循环中不会改变），但是请注意第一步改变数组中的顺序，所以是第一个元素的值，不再是（通常）在步骤 1 之后。

事实上，在每次执行步骤1时，最后一个元素都会不同，所以在循环完成后所有的排列都会生成。

当数组中只有一个元素需要考虑时，递归结束。在这种情况下，不需要交换任何内容，并且数组以其当前顺序输出（通过 yield）。

请注意，此算法有几个错误的变体，以及使用基于 1 的索引的变体，因此在比较这些变体时可能会变得非常混乱。

在 Javascript 中寻找期权排列算法。也许…？

Looking for Permutations of Options algorithm in Javascript. Maybe…?

javascript

arrays

permutation

combinatorics

multidimensional-array

所有 nⁿ 重复排列

所有 n! 排列无重复

在 Javascript 中寻找期权排列算法。也许…？

Looking for Permutations of Options algorithm in Javascript. Maybe…?

javascript

arrays

permutation

combinatorics

multidimensional-array

所有 nn 重复排列

所有 n! 排列无重复

所有 nⁿ 重复排列