排列组合的算法问题

Question

有一个整型变量最大的取值范围是1到这个值
1、如a:=39时，它可能的取值有39个，从1、2、3...39
2、有一个动态数组 b: array of [0..9] 取值范围仅仅为0,1,2,3,4,5,6,7,8,9这十个数，如
length(b,3)
b[0]=3;
b[1]=7;
b[2]=9;
3、请问如何计算，在a所有的取值范围内，其值中不出现b中的数字，有多少个？
如此例中 a=1,a=2,a=4..a=25都是合要求的，而a=31是不合要求的，因为31中有3这个数字(b[0]=3) 有一个笨算法
k:=0;for i:=1 to 39 do begin
  isno:=false;
  for j:=low(b) to high(b) do begin
    if pos(inttostr(b[j]), inttsotr(i))>=1 then begin
       isno:=true;
       break;
    end;
  end;
  if isno=false then k:=k+1;
end;最后k就是结果

Answer 1

//看看这个算法可否满足楼主要求？function TestArray(a:Integer;b:array of Integer;len:Integer=10):Boolean;
var
     numset:set of 0..9;
     i:Integer;
begin
     numset:=[];
     for i:=0 to len-1 do
     begin
          numset:=numset+[b[i]];
     end;
     Result:=True;
     repeat
          if (a mod 10) in numset then
          begin
               Result:=False;
               break;
          end;
          a:=a div 10;
     until a=0;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
     b:array[0..9] of Integer;
begin
     b[0]:=3;
     b[1]:=7;
     b[2]:=9;
     if TestArray(21,b,3) then ShowMessage('ok');
end;

Answer 2

sorry,我曲解了你的意思，我重写算法。

Answer 3

{
     首先对问题做如下分析:
     假如从从 0 到 9 的扫描中只有a,b,c三个数满足要求，那么在接下来的判断中
     只用判断1a,1b,1c,2a,2b,2c,....9a,9b,9c几组数，很容易看出这组扫描中仍然只有
     aa,ab,ac,ba,bb,bc,ca,cb,cc几组满足要求，继续很容易发现只有包含a,b,c几个数字
     组成的数（在允许范围内）才有可能满足要求。
     所以不难得出如下算法。}function GetTheBaseNum(num,base:Integer):String;
begin
     if num<base then
          Result:=IntToStr(num)
     else
          Result:=GetTheBaseNum(num div base,base)+IntToStr((num mod base));
end;
function GetOkNum(a:Integer;b:array of Integer;len:Integer=10):Integer;
var
     numset:set of 0..9;
     tb:array[0..9] of Integer;
     astr,numstr:String;
     num,oknum,la,ma,l,i,j:Integer;
begin
     Result:=0;
     oknum:=0;
     numset:=[];
     la:=Length(IntToStr(a));
     for i:=0 to len-1 do
     begin
          numset:=numset+[b[i]];
     end;
     for i:=0 to 9 do
     begin
          if not (i in numset) then
          begin
               tb[oknum]:=i;//得到了一个从小到大的不包含在数组b中的数字序列。
               Inc(oknum);//为满足条件的数字计数
          end;
     end;
     i:=1;
     repeat
          astr:=GetTheBaseNum(i,oknum);
          la:=length(astr);
          numstr:='';
          for j:=1 to la do
          begin
               ma:=ord(astr[j])-ord('0');
               numstr:=numstr+inttostr(tb[ma]);
          end;
          inc(i);
     until strtoint(numstr)>a;
     Result:=i-1;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
     b:array[0..9] of Integer;
begin
     b[0]:=8;
     b[1]:=9;
     b[2]:=7;
     showmessage(IntToStr(GetOkNum(31236,b,3)));
end;

Answer 4

谢谢
wizardqi(男巫) 
您的算法我测试了一个
1、普通的情况结果值比我用笨办法计算的值大了1
2、没有考虑exclude为0 的情况: 如b[1]:=0
3、最致命的是，您的算法似乎不比笨办法快
     b[0]:=8;
     b[1]:=9;
     b[2]:=7;
     showmessage(IntToStr(GetOkNum(31236,b,3)));您的值是7672，而我的是7671     b[0]:=8;
     b[1]:=0;
     b[2]:=7;
     showmessage(IntToStr(GetOkNum(31236,b,3)));
您的值是4871，而我的是7671

Answer 5

你是否让087 和87作为数字有区别呀?
我觉得最大改进是有几种有效组合就循环几次，其实我早先作了个办法只是计算次数，但后来想想如果要输出这样数的序列就没法了，所以想了上面的办法。我使用了一个最精密的计数器来测量你我的代码的效率，你可以看看结果。计数器如下：
function GetCounter:Int64;
asm
dw 310fh;
end;

Answer 6

interfaceuses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls,Math;type
  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
    s1,s2:Int64;
  end;var
  Form1: TForm1;implementation{$R *.DFM}
function GetCounter:Int64;
asm
dw 310fh;
end;
function GetTheBaseNum(num,base:Integer):String;
begin
     if num<base then
          Result:=IntToStr(num)
     else
          Result:=GetTheBaseNum(num div base,base)+IntToStr((num mod base));
end;
function GetOkNum(a:Integer;b:array of Integer;len:Integer=10):Integer;
const
     num0asc=48;
var
     numset:set of 0..9;
     tb:array[0..9] of char;//Integer;
     numstr:array[0..15] of char;
     astr:String;
     num,oknum,la,ma,l,i,j:Integer;
begin
     Result:=0;
     oknum:=0;
     numset:=[];
     for i:=0 to len-1 do
     begin
          numset:=numset+[b[i]];
     end;
     for i:=0 to 9 do
     begin
          if not (i in numset) then
          begin
               tb[oknum]:=Char(i+num0asc);//得到了一个从小到大的不包含在数组b中的数字序列。
               Inc(oknum);//为满足条件的数字计数
          end;
     end;
     i:=1;
     repeat
          astr:=GetTheBaseNum(i,oknum);
          la:=length(astr);
          numstr[la]:=#0;
          for j:=1 to la do
          begin
               ma:=Byte(astr[j])-48;
               numstr[j-1]:=tb[ma];
          end;
          inc(i);
     until StrToInt(numstr)>a;
     Result:=i-1;
end;
function GetOkNum2(a:Integer;b:array of Integer;len:Integer=10):Integer;
var
i,j,k:Integer;
isno:Boolean;
begin
k:=0;for i:=1 to a do begin
  isno:=false;
  for j:=0 to len-1 do begin
    if pos(inttostr(b[j]), inttostr(i))>=1 then begin
       isno:=true;
       break;
    end;
  end;
  if isno=false then k:=k+1;
end;
Result:=k;
end;procedure TForm1.Button1Click(Sender: TObject);//使用我的算法
var
     b:array[0..9] of Integer;
begin
     b[0]:=8;
     b[1]:=1;
     b[2]:=7;
     s1:=GetCounter;
     showmessage(IntToStr(GetOkNum(9999999,b,3)));
     s1:=GetCounter-s1;
end;procedure TForm1.Button2Click(Sender: TObject);//使用楼主的算法
var
     b:array[0..9] of Integer;
begin
     b[0]:=8;
     b[1]:=1;
     b[2]:=7;
     s2:=GetCounter;
     showmessage(IntToStr(GetOkNum2(9999999,b,3)));
     s2:=GetCounter-s2;
end;procedure TForm1.Button3Click(Sender: TObject);//cpu时钟周期差
begin
     ShowMessage(IntToStr(s2-s1));
end;