问个题目:数字组合 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个题目:数字组合

问个题目:数字组合# JobHunting - 待字闺中

i*e2012-06-18 07:06

1 楼

设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个
0<=Ni <= N 且 sum(Ni : i from 0 to 9) = N
请中，有多少个由这些数字组成的数在范围[a, b]中, B的位数可能大于N（此时可随意
添加0的个数）
比如
1022, 其中有1 1个, 0 1个，2 2个
如果a= 1000, b = 20000则 1202, 2012, 10220, 12020等都是备选
不知道说清楚没

p*22012-06-18 07:06

2 楼

最简单的解法就是brute force，如果b不大的话。
要不就把所有的排列得出来，后边再加0。

i*e2012-06-18 07:06

3 楼

要是b很大呢，似乎两种方法都太耗时了

【在 p*****2 的大作中提到】

: 最简单的解法就是brute force，如果b不大的话。
: 要不就把所有的排列得出来，后边再加0。

p*22012-06-18 07:06

4 楼

你这题是从哪里来的？a,b的范围多大？

【在 i*****e 的大作中提到】

: 要是b很大呢，似乎两种方法都太耗时了

i*e2012-06-18 07:06

5 楼

一朋友问的，觉得是到数学题，呵呵
应该可以用排列组合的理论来解，但是想不到好方法
1<= a <= b <= 2^64 or 2^128

p*22012-06-18 07:06

6 楼

数学题我不擅长，等着数学博士过来看看吧。

【在 i*****e 的大作中提到】

: 一朋友问的，觉得是到数学题，呵呵
: 应该可以用排列组合的理论来解，但是想不到好方法
: 1<= a <= b <= 2^64 or 2^128

a*o2012-06-18 07:06

7 楼

二爷求加俱乐部！

【在 p*****2 的大作中提到】

:
: 数学题我不擅长，等着数学博士过来看看吧。

C*U2012-06-18 07:06

8 楼

可以这样。找到和a最接近但是比a大的组合。找到和b最接近但是比b小的组合
用nextpremutation来找出之间的数
找那两个数应该都用o(n)时间
加上nextpermutation们的时间

设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个0
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

【在 i*****e 的大作中提到】

: 设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个
: 0<=Ni <= N 且 sum(Ni : i from 0 to 9) = N
: 请中，有多少个由这些数字组成的数在范围[a, b]中, B的位数可能大于N（此时可随意
: 添加0的个数）
: 比如
: 1022, 其中有1 1个, 0 1个，2 2个
: 如果a= 1000, b = 20000则 1202, 2012, 10220, 12020等都是备选
: 不知道说清楚没

i*e2012-06-18 07:06

9 楼

恩，应该可以试一试
之前用python试了一把，python的permutation函数不区分重复数字，candidates太多.
..
貌似stl的next_permutation可以

【在 C***U 的大作中提到】

: 可以这样。找到和a最接近但是比a大的组合。找到和b最接近但是比b小的组合
: 用nextpremutation来找出之间的数
: 找那两个数应该都用o(n)时间
: 加上nextpermutation们的时间
:
: 设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个0
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite

g*s2012-06-18 07:06

10 楼

以前好像做过类似的，不过没有可以随便加０这个条件。
基本思路就是固定头几位，后面数字不影响的时候直接用排列公式来算。
例如０１２３５５，［１２４００１，３１５５０６］
１０＊全排除
１２［０３］＊全排除
１２５＊全ok 直接计算０３５的全排列树目。
２＊全ok 直接计算０１３５５的全排列树目。
３０＊全ok 直接计算１２５５的全排列树目。
３１０全ok
３１２全ok
３１５０
。。。
复杂度是数字的长度.
这题０可以随便加，指的是加到最后吧。一样的思路可以解。

【在 i*****e 的大作中提到】