7

これは非常に簡単だと思いますが、これを行う方法に困惑しています。基本的に、P列とV ^ P行の配列がある場合、すべての組み合わせ、つまり、基本的に、P桁のベースVのすべての可能な数値を入力するにはどうすればよいですか。たとえば、P=3およびV=2の場合：

000
001
010
011
100
101
110
111

これは2次元配列であり、intの配列ではないことに注意してください。

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

したがって、基本的には 4 つの 0 の後に 4 つの 1 が必要です。

2 番目の列では、次のものが必要です。

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

したがって、2 つの 0 の後に 2 つの 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_reprC# に変換されたアルゴリズムは次のとおりです (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 アプローチを使用すると、各数値をゼロから計算する必要がなくなり、新しいリーフに到達するまで前の数値を単純にインクリメントできます。これらのバージョンはジェネレーターを使用しませんが、簡単に調整できます。

パイソン:

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 に答える