生成给定基数和位数的所有可能排列 [英] Generating all possible permutations for a given base and number of digits
问题描述
我敢肯定这很简单，但是我为实现这一目标而烦恼.本质上，如果我有一个包含P个列和V ^ P行的数组，那么我该如何填充所有组合，也就是说，本质上是P位以V为底的所有可能数字.例如，对于P = 3和V = 2:
I'm sure this is pretty simple, but I'm stumped for a way to do this. Essentially if I have an array with P collumns and V^P rows, how can I fill in all the combinations, that is, essentially, all possible numbers in base V of P digits. For example, for P=3 and V=2:
000
001
010
011
100
101
110
111
请记住，这是一个二维数组，而不是整数数组.
Keep in mind that this is an 2 dimensional array, not an array of ints.
对于P = 4和V = 3.
For P=4 and V=3.
0000
0001
0002
0010
0011
0012
....
生成此数组后，我要开发的其余工作微不足道.因此，对如何执行此操作有一些代码/提示将不胜感激.谢谢.
Having this array generated, the rest of work for what I'm trying to devolop is trivial. So having some code/tips on how to do this would be greatly appreciated. Thanks.
推荐答案
基本上，这是列出v p 数字的列表，这些数字从0到基数numpy.base_repr 可以用于在Python中执行此操作:
Basically this is making a list of vp numbers from 0 to the largest number of digit width p in base v. numpy.base_repr can be used to do this in Python:
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可以完成工作(结果效率最高-请参见下面的基准).
Additionally, itertools.product(range(v), repeat=p) is another Python builtin that does the job (it turns out most efficiently--see benchmark below).
这是从numpy.base_repr转换为C#的算法(Convert.ToString()对于基数非常有选择性):
Here's the algorithm from numpy.base_repr translated to C# (Convert.ToString() is very selective about bases):
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方法意味着我们不必从头开始计算每个数字，而可以简单地递增之前的数字，直到到达新的叶子为止.这些版本不使用生成器，但这是一个简单的调整:
Although the numpy version is simple to use and iterative, it's also slow. Using a recursive DFS approach means we don't have to compute each number from scratch, but can simply increment the previous number until we reach a new leaf. These versions don't use generators, but it's an easy adjustment:
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);
}
}
}
}
快速基准测试(带有生成器):
Quick benchmark (with generators):
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远距离获胜.
这篇关于生成给定基数和位数的所有可能排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
