与えられた数よりも少ない数で、数字が繰り返されていない数を見つけるにはどうすればよいでしょうか?
たとえば、100 未満の数は 90 です (11、22、33、44、55、66、77、88、99 は数字が繰り返されるため除外されます)。
同様に、1000 未満の場合は、101、110、122、202 などの数字を除外する必要があります。
6939 次
3 に答える
2
次の 2 つのケースを考えることができます。
- 数値が制限より短い
- 一部の桁で制限と異なる数値
-桁の数のカウントdは9*9*8*... = 9*9!/(9-d)!(最初の桁がゼロでない可能性があります) です。より短いすべての数字dのカウントは、0 桁の数字のカウント + .. - 桁の数字のカウントですd-1。これらの合計は、事前に計算されている場合があります (またはハードコーディングされている場合もあります)。
最初の桁が指定された - 桁のd数字の数は です。階乗も事前計算できます。f(10-f)*...*(10-(d-1)) = (10-f)!/(10-d)!
擬似コード:
To precompute fac:
- fac = int[10];
- fac[0] = 1;
- for i in 1..10:
- fac[i] = fac[i-1] * i;
To precompute count_shorter:
- cs = int[10];
- cs[0] = 0;
- cs[1] = 1; // if zero is allowed
- for i in 1..10:
- cs[i+1] = cs[i] + 9 * fac[9] / fac[10-i]
- count_shorter = cs;
To determine the count of numbers smaller than d:
- sl = strlen(d)
- if sl > 10
- return count_shorter[11]
- else
- sum = 0
account for shorter numbers:
- sum += count_shorter[sl]
account for same-length numbers; len=count of digits shared with the limit:
- sum += 9* fac[9] / fac[10-sl];
- for every len in 1..{sl-1}:
count the unused digits less than d[len]; credits to @MvG for noting:
- first_opts = d[len]-1;
- for every i in 0..{len-1}:
- if d[i] < d[len]
- first_opts -= 1;
- sum += first_opts * fac[9-len] / fac[10-sl]
- return sum
于 2012-11-06T09:10:26.143 に答える
2
ここにそれをより速くする方法があります。最大数の桁数と解 (と呼ぶ数NON)の間には相関関係があることに注意してください。
100 (3 digits) => NON = 10 * 9
1000 (4 digits) => NON = 10 * 9 * 8
10000 (5 digits) => NON = 10 * 9 * 8 * 7
...
10000000000 (11 digits) => NON = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
10億を超えると数字を繰り返すことになります
于 2012-11-06T08:00:39.610 に答える
0
これを行うコードを次に示します。コード内のコメント。基本的な考え方は、最後にカウントされた数字の数字を一度に 1 つずつ反復し、すべての数字位置について、その位置より前の数字が同じで、現在の位置の数字が小さい数字を数えることです。関数は相互に構築されているため、cntSmaller最後の関数が実際に呼び出す関数であり、最も詳細なコメントも含まれています。私は、これが 30000 までのすべての引数のブルート フォース実装と一致することを確認しました。別の実装と広範囲にわたる比較を行ったので、このコードが正しいと確信しています。
from math import factorial
def take(n, r):
"""Count ways to choose r elements from a set of n without
duplicates, taking order into account"""
return factorial(n)/factorial(n - r)
def forLength(length, numDigits, numFirst):
"""Count ways to form numbers with length non-repeating digits
that take their digits from a set of numDigits possible digits,
with numFirst of these as possible choices for the first digit."""
return numFirst * take(numDigits - 1, length - 1)
def noRepeated(digits, i):
"""Given a string of digits, recursively compute the digits for a
number which is no larger than the input and has no repeated
digits. Recursion starts at i=0."""
if i == len(digits):
return True
while digits[i] in digits[:i] or not noRepeated(digits, i + 1):
digits[i] -= 1
for j in range(i + 1, len(digits)):
digits[j] = 9
if digits[i] < 0:
digits[i] = 9
return False
return True
def lastCounted(n):
"""Compute the digits of the last number that is smaller than n
and has no repeated digits."""
digits = [int(i) for i in str(n - 1)]
while not noRepeated(digits, 0):
digits = [9]*(len(digits) - 1)
while digits[0] == 0:
digits = digits[1:]
assert len(digits) == len(set(digits))
return digits
def cntSmaller(n):
if n < 2:
return 0
digits = lastCounted(n)
cnt = 1 # the one from lastCounted is guaranteed to get counted
l = len(digits)
for i in range(1, l):
# count all numbers with less digits
# first digit non-zero, rest all other digits
cnt += forLength(i, 10, 9)
firstDigits = set(range(10))
for i, d in enumerate(digits):
# count numbers which are equal to lastCounted up to position
# i but have a smaller digit at position i
firstHere = firstDigits & set(range(d)) # smaller but not duplicate
if i == 0: # this is the first digit
firstHere.discard(0) # must not start with a zero
cnt += forLength(l - i, 10 - i, len(firstHere))
firstDigits.discard(d)
return cnt
編集: cntSmaller(9876543211) 8877690 を返します。これは、繰り返さない数字で形成できる数字の最大数です。これが 10!=3628800 を超えるという事実にしばらく混乱しましたが、これは正しいです: シーケンスが長さ 10 にパディングされていると考えると、数値のどこかにゼロに加えて先行ゼロのシーケンスが許可されます。これにより、純粋な順列よりもカウントが増加します。
于 2012-11-06T11:19:20.600 に答える