7

我敢肯定这很简单，但我很难做到这一点。本质上，如果我有一个包含 P 列和 V^P 行的数组，我该如何填写所有组合，也就是说，基本上，所有可能的数字都在 P 位的基数 V 中。例如，对于 P=3 和 V=2：

000
001
010
011
100
101
110
111

请记住，这是一个二维数组，而不是整数数组。

对于 P = 4 和 V = 3。

0000
0001
0002
0010
0011
0012
....

生成这个数组后，我试图开发的其余工作就变得微不足道了。因此，非常感谢您提供一些有关如何执行此操作的代码/提示。谢谢。

4

4 回答 4

1

以 P=3 和 V=2 为例，在第一列中，您需要以下数字序列：

0, 0, 0, 0, 1, 1, 1, 1

所以你基本上想要四个 0，然后是四个 1。

在第二列中，您需要：

0, 0, 1, 1, 0, 0, 1, 1

因此，您需要两个 0，然后是两个 1，然后再是相同的。

一般来说，在第n列中，每个数字都需要V^(Pn)，重复V^(n-1)次。

P=3 和 V=2 时的示例：

第 1 列：我们需要每个数字的 V^(Pn) = 2^(3-1) = 4，重复 V^(n-1) = 2^0 = 1 次：

[0, 0, 0, 0, 1, 1, 1, 1]

第 2 列：我们需要每个数字的 V^(Pn) = 2^(3-2) = 2，重复 V^(n-1) = 2^1 = 2 次：

[0, 0, 1, 1], [0, 0, 1, 1]

第 3 列：我们需要每个数字的 V^(Pn) = 2^(3-3) = 1，重复 V^(n-1) = 2^2 = 4 次：

[0, 1], [0, 1], [0, 1], [0, 1]

生成此序列的一些 Python 代码：

def sequence(v, p, column):
    subsequence = []
    for i in range(v):
        subsequence += [i] * v**(p - column)
    return subsequence * v**(column - 1)
于 2012-06-03T13:38:40.173 回答
1

基本上，这是从 0 到base中最大数字宽度的 v p数字列表。可用于在 Python 中执行此操作：pvnumpy.base_repr

from numpy import base_repr

def base_of_size(base, size):
    for i in range(base ** size):
        yield base_repr(i, base).rjust(size, "0")

此外，itertools.product(range(v), repeat=p)是另一个可以完成这项工作的 Python 内置函数（结果证明效率最高——参见下面的基准测试）。

这是从numpy.base_repr翻译到 C# 的算法（Convert.ToString()对基础非常有选择性）：

using System;
using System.Collections.Generic;

class Converter
{
    public static IEnumerable<string> BaseOfSize(int baseN, int size) 
    {
        for (int i = 0; i < Math.Pow(baseN, size); i++) 
        {
              yield return BaseRepr(i, baseN).PadLeft(size, '0');
        }
    }

    public static string BaseRepr(int n, int baseN)
    {
        string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        var res = new List<char>();

        for (int num = Math.Abs(n); num > 0; num /= baseN) 
        {
            res.Add(digits[num%baseN]);  
        }

        if (n < 0) res.Add('-');

        res.Reverse();
        return string.Join("", res);
    }

    public static void Main(string[] args) 
    {
        foreach (var n in BaseOfSize(2, 3)) 
        {
            Console.WriteLine(n);
        }

        Console.WriteLine();

        foreach (var n in BaseOfSize(3, 4)) 
        {
            Console.WriteLine(n);
        }
    }
}

输出：

000
001
010
011
100
101
110
111

0000
0001
0002
0010
0011
0012
0020
 ...
2220
2221
2222

虽然 numpy 版本使用简单且可迭代，但速度也很慢。使用递归 DFS 方法意味着我们不必从头开始计算每个数字，而是可以简单地增加前一个数字，直到我们到达新的叶子。这些版本不使用生成器，但很容易调整：

Python：

def base_of_size(base, size):
    def recurse(res, row, i=0):
        if i >= size:
            res.append(row[:])
        else:
            for j in range(base):
                row[i] = j
                recurse(res, row, i + 1)

        return res

    return recurse([], [None] * size)

C＃：

using System;
using System.Collections.Generic;

class Converter
{
    public static List<List<int>> BaseOfSize(int v, int p) 
    {
        var res = new List<List<int>>();
        BaseOfSize(v, p, 0, new List<int>(new int[p]), res);
        return res;
    }

    private static void BaseOfSize(int v, int p, int i, List<int> row, List<List<int>> res)
    {
        if (i >= p) 
        {
            res.Add(new List<int>(row));
        }
        else 
        {
            for (int j = 0; j < v; j++) 
            { 
                row[i] = j;
                BaseOfSize(v, p, i + 1, row, res);
            }
        }
    }
}

快速基准测试（使用生成器）：

from itertools import product
from time import time
from numpy import base_repr

def base_of_size(base, size):
    def recurse(res, row, i=0):
        if i >= size:
            yield row[:]
        else:
            for j in range(base):
                row[i] = j
                yield from recurse(res, row, i + 1)

        return res

    yield from recurse([], [None] * size)

def base_of_size2(base, size):
    for i in range(base ** size):
        yield base_repr(i, base).rjust(size, "0")

if __name__ == "__main__":
    start = time()
    list(base_of_size(10, 6))
    end = time()
    print("dfs:", end - start)
    start = time()
    list(base_of_size2(10, 6))
    end = time()
    print("base_repr:", end - start)
    start = time()
    list(product(range(10), repeat=6))
    end = time()
    print("product:", end - start)

输出：

dfs: 4.616123676300049
base_repr: 9.795292377471924
product: 0.5925478935241699

itertools.product以远射获胜。

于 2019-08-09T16:18:39.847 回答
0

如果每个“数字”中有不同数量的选项，则可以使用此代码。

也许在某些优化工具中存在执行此操作的算法，因为它可能对蛮力方法有用。下面的代码添加了一个显示“最大数字的值”的列，可以忽略它：

import numpy as np
val=np.arange(15)
options=[2,2,3]
print(val)
print(options)
opt = options + [1] # Assumes options to be a list
opt_cp = np.flip(np.cumprod(np.flip(np.array(opt))))
ret = np.floor_divide(val[:,np.newaxis], opt_cp[np.newaxis,:])
ret[:,1:] = np.remainder(ret[:,1:], np.array(opt[:-1])[np.newaxis,:])
inds = ret[:,1:]
print(inds)
于 2019-08-12T06:37:04.110 回答
0

您还可以使用 numpy 的 N 维网格网格函数。

例如

np.mgrid[0:2,0:2,0:2].reshape((3, 8)).T

array([[0, 0, 0],
       [0, 0, 1],
       [0, 1, 0],
       [0, 1, 1],
       [1, 0, 0],
       [1, 0, 1],
       [1, 1, 0],
       [1, 1, 1]])

或者

np.stack(np.meshgrid(range(2), range(2), range(2), indexing='ij')).reshape(3, -1).T

或者一般来说任何P, V:

np.mgrid[[slice(0, V)]*P].reshape((P, -1)).T

或者

np.stack(np.meshgrid(*[range(V)]*P, indexing='ij')).reshape((P, -1)).T

必须有一个更明显的方法，但我想不出什么。

于 2021-06-08T20:37:46.233 回答