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")
Additionally, itertools.product(range(v), repeat=p) is another Python builtin that does the job (it turns out most efficiently--see benchmark below).
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);
}
}
}
Output:
000
001
010
011
100
101
110
111
0000
0001
0002
0010
0011
0012
0020
...
2220
2221
2222
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)
Output:
dfs: 4.616123676300049
base_repr: 9.795292377471924
product: 0.5925478935241699
itertools.product wins by a long shot.
