8

はっきりさせてください:

2 つの数字の間にすべての一意の数字があるすべての数字を取得する最速の方法は何でしょうか。たとえば、10,000 と 100,000 です。

明らかなものは、12,345 または 23,456 です。それらをすべて集める方法を見つけようとしています。

for i in xrange(LOW, HIGH):
  str_i = str(i)
  ...?
4

5 に答える 5

15

使用itertools.permutations:

from itertools import permutations

result = [
    a * 10000 + b * 1000 + c * 100 + d * 10 + e
    for a, b, c, d, e in permutations(range(10), 5)
    if a != 0
]

私は事実を使用しました：

  • 10000との間の数字は1000005 桁または 6 桁ですが、ここの 6 桁の数字だけは固有の数字を持ちません。
  • itertools.permutations指定された長さで、すべての組み合わせをすべての順序で作成します (結果には12345と54321の両方が表示されます)。
  • 整数のシーケンスに対して直接順列を実行できます (したがって、型を変換するためのオーバーヘッドはありません)。

編集：

私の回答を受け入れていただきありがとうございますが、言及された結果を比較した他のデータは次のとおりです。

>>> from timeit import timeit
>>> stmt1 = '''
a = []
for i in xrange(10000, 100000):
    s = str(i)
    if len(set(s)) == len(s):
        a.append(s)
'''
>>> stmt2 = '''
result = [
    int(''.join(digits))
    for digits in permutations('0123456789', 5)
    if digits[0] != '0'
]
'''
>>> setup2 = 'from itertools import permutations'
>>> stmt3 = '''
result = [
    x for x in xrange(10000, 100000)
    if len(set(str(x))) == len(str(x))
]
'''
>>> stmt4 = '''
result = [
    a * 10000 + b * 1000 + c * 100 + d * 10 + e
    for a, b, c, d, e in permutations(range(10), 5)
    if a != 0
]
'''
>>> setup4 = setup2
>>> timeit(stmt1, number=100)
7.955858945846558
>>> timeit(stmt2, setup2, number=100)
1.879319190979004
>>> timeit(stmt3, number=100)
8.599710941314697
>>> timeit(stmt4, setup4, number=100)
0.7493319511413574

要約すると、次のようになります。

最後のソリューションは、他の人が提案したソリューションよりも約 10 倍高速に見えます。

注: 私のソリューションには、測定していないインポートがいくつかあります。インポートが 1 回行われ、コードが複数回実行されると想定しました。そうでない場合は、必要に応じてテストを調整してください。

編集＃2：文字列を操作する必要さえないため、別のソリューションを追加しました-実際の整数の順列を使用することで実現できます。これでさらに高速化できると思います。

于 2013-09-11T03:53:33.730 に答える
7

これを行う安価な方法：

for i in xrange(LOW, HIGH):
    s = str(i)
    if len(set(s)) == len(s):
        # number has unique digits

これは、 aを使用しsetて一意の数字を収集し、一意の数字が合計数字と同じ数あるかどうかを確認します。

于 2013-09-11T03:44:48.337 に答える
2

ここにゼロからの答えがあります：

def permute(L, max_len):
    allowed = L[:]
    results, seq = [], range(max_len)
    def helper(d):
        if d==0:
            results.append(''.join(seq))
        else:
            for i in xrange(len(L)):
                if allowed[i]:
                    allowed[i]=False
                    seq[d-1]=L[i]
                    helper(d-1)
                    allowed[i]=True
    helper(max_len)
    return results

A = permute(list("1234567890"), 5)
print A
print len(A)
print all(map(lambda a: len(set(a))==len(a), A))

n = 10の場合、違いが生じるかどうかはわかりませんが、許可された要素の間隔表現を使用してさらに最適化できる可能性があります。再帰をループに変換することもできますが、この形式の方がよりエレガントで明確です。

編集：さまざまなソリューションのタイミングは次のとおりです

  • 2.75808000565 (私の解決策)
  • 8.22729802132 (ソル 1)
  • 1.97218298912 (ソル 2)
  • 9.659760952 (ソル 3)
  • 0.841020822525 (ソル 4)
于 2013-09-11T15:29:13.387 に答える