整数の力まかせ探索(ソースコード)

大抵のことは mask.hpp 単独でできます。
配列を対象にするなら maskex.hpp、mex-main.hpp、shuffle.hpp が追加で必要です。
配列をシャッフルするだけなら shuffle.hpp 単独でできます。
オプションのプログラムとして mex-recu.hpp、mex-mini.hpp が使用可能です。
これらのオプションプログラムは使い方や結果は同じですが、性能が違います。

基本プログラム mask.hpp
マスクをメモリ上に配列として列挙する maskex.hpp
マスクをメモリ上に配列として列挙する。既定の実装 mex-main.hpp
１個、または２個の配列をシャッフルする shuffle.hpp
(オプション)マスクをメモリ上に配列として列挙する。再帰呼び出しによる実装 mex-recu.hpp
(オプション)マスクをメモリ上に配列として列挙する。小さな実装 mex-mini.hpp

基本プログラム `mask.hpp`

/* mask.hpp : coded by Isaku WADA(isaku@pb4.so-net.ne.jp) 2025
Brute-force search for integers */
#if !defined(MASK_HPP)
 #define MASK_HPP

typedef unsigned char  byte;
typedef unsigned short word;
 #if !defined(_MSC_VER) && !defined(__BORLANDC__)
typedef          long long sqword;
typedef unsigned long long  qword;
 #else
typedef          __int64 sqword;
typedef unsigned __int64  qword;
 #endif
 #if defined(__x86_64__)
typedef  __int128_t sxword;
typedef __uint128_t  xword;
 #endif

struct minfo_t { byte BitCount,NumOfRun; char Bsr,Bsf; };
static minfo_t*NoInfo,DummyInfo;

enum {
DefLimitExp=62, MeError=-1,
MeNoError=0,          MeMaxWidthTooSmall,  MeMaxWidthTooBig,
MeMinBitCountTooSmall,MeMinBitCountTooBig,
MeMaxBitCountTooSmall,MeMaxBitCountTooBig, MeMaxBitCountLessThanMin,
MeMinLenOfRunTooSmall,MeMinLenOfRunTooBig,
MeMaxLenOfRunTooSmall,MeMaxLenOfRunTooBig, MeMaxLenOfRunLessThanMin,
MeMaxNumOfRunTooSmall,MeLimitOrSizeTooSmall,
MeMinNumOfRunTooSmall,MeMinNumOfRunTooBig, MeMaxNumOfRunLessThanMin,
MeNewFailed,
};

static const char*MeErrMsg[]={
"No Error",             "MaxWidth too small", "MaxWidth too big",
"MinBitCount too small","MinBitCount too big",
"MaxBitCount too small","MaxBitCount too big","MaxBitCount less than Min",
"MinLenOfRun too small","MinLenOfRun too big",
"MaxLenOfRun too small","MaxLenOfRun too big","MaxLenOfRun less than Min",
"MaxNumOfRun too small","Limit or size too small",
"MinNumOfRun too small","MinNumOfRun too big","MaxNumOfRun less than Min",
"new[] failed",
};

struct mconf_t {
    sqword Limit; mconf_t*Src; const char*ErrMsg;
    int MaxWidth,MinBitCount,MaxBitCount,MinNumOfRun,MaxNumOfRun;
    int MinLenOfRun,MaxLenOfRun,ErrCode,GenMsec,ShuffleMsec;
    void ClearInput(void)  {
        MaxWidth=MinNumOfRun=MaxNumOfRun=MinBitCount=MaxBitCount=0;
        MinLenOfRun=MaxLenOfRun=0; Limit=0;
    }
    void ClearOutput(void) { GenMsec=ShuffleMsec=0; }
    void ClearError(void) { ErrCode=0; ErrMsg=MeErrMsg[MeNoError]; }
    void CopyInput(const mconf_t&src) {
        Limit=src.Limit; MaxWidth=src.MaxWidth;
        MinNumOfRun=src.MinNumOfRun; MaxNumOfRun=src.MaxNumOfRun;
        MinBitCount=src.MinBitCount; MaxBitCount=src.MaxBitCount;
        MinLenOfRun=src.MinLenOfRun; MaxLenOfRun=src.MaxLenOfRun; 
    }
    int SetMerr0(int errcode) {
        if (ErrCode==0) { ErrCode=errcode; ErrMsg=MeErrMsg[errcode]; }
        return MeError;
    }
    void Reset(void) { ClearOutput(); ClearInput(); ClearError(); }
    mconf_t() {
        Src=0; Reset();
 #if defined(__BORLANDC__)
        NoInfo=NoInfo; DummyInfo=DummyInfo;
 #endif
    }
    void SetMerr(int errcode)   { Src->SetMerr0(errcode); }
    void Complete(mconf_t&src,int typewidth) {
        Src=&src; ClearError(); src.ClearError(); CopyInput(src);
        if (MaxWidth<=0) MaxWidth+=typewidth;
        if (MaxWidth<=0) SetMerr(MeMaxWidthTooSmall);
        if (MaxWidth>typewidth) SetMerr(MeMaxWidthTooBig);
        if (MinBitCount<0) SetMerr(MeMinBitCountTooSmall);
        if (MinBitCount>MaxWidth) SetMerr(MeMinBitCountTooBig);
        if (MaxBitCount<=0) MaxBitCount+=MaxWidth;
        if (MaxBitCount<1) SetMerr(MeMaxBitCountTooSmall);
        if (MaxBitCount<MinBitCount) SetMerr(MeMaxBitCountLessThanMin);
        if (MinLenOfRun==0) MinLenOfRun=1; 
        if (MinLenOfRun<1) SetMerr(MeMinLenOfRunTooSmall);
        if (MinLenOfRun>MaxWidth) SetMerr(MeMinLenOfRunTooBig);
        if (MaxLenOfRun<=0) MaxLenOfRun+=MaxWidth;
        if (MaxLenOfRun<=0) SetMerr(MeMaxLenOfRunTooSmall);
        if (MaxLenOfRun<MinLenOfRun) SetMerr(MeMaxLenOfRunLessThanMin);
        int max_run=(MaxWidth+1)/(MinLenOfRun+1);
        if (MaxNumOfRun==0) MaxNumOfRun=max_run;
        if (MaxNumOfRun<=0) SetMerr(MeMaxNumOfRunTooSmall);
        if (MinNumOfRun>max_run) SetMerr(MeMinNumOfRunTooBig);
        if (MaxNumOfRun>max_run) MaxNumOfRun=max_run;
        if (MinNumOfRun<0) SetMerr(MeMinNumOfRunTooSmall);
        if (MaxNumOfRun<MinNumOfRun) SetMerr(MeMaxNumOfRunLessThanMin);
        if (Limit==0) Limit=((sqword)1)<<DefLimitExp;
        if (Limit<0) SetMerr(MeLimitOrSizeTooSmall);
    }
};

template <typename T>
struct mstack_t { byte Count,Hi,Lo,Length; T Mask; };

template <typename T>
struct mnext_t {
    mstack_t<T>Stack[sizeof(T)*4+1],*StackPtr,*StackMin,*StackMax;
    mconf_t Mc; sqword Qnum; bool Zero;
    int Reset(mconf_t&conf);
    mnext_t(mconf_t&conf) { Reset(conf); }
    bool NextMask(T&mask,minfo_t&info=DummyInfo);
};

template <typename T>
int mnext_t<T>::Reset(mconf_t&conf) {
    Mc.Complete(conf,(int)sizeof(T)*8); Qnum=0;
    if (conf.ErrCode) { StackPtr=Stack; return MeError; }
    for (int i=0;i<(int)sizeof Stack;i++) ((char*)Stack)[i]=0;
    StackPtr=Stack+1; StackMin=Stack+Mc.MinNumOfRun;
    StackMax=Stack+Mc.MaxNumOfRun; Stack[1].Length=(byte)Mc.MaxWidth;
    Stack[1].Hi=(byte)(Mc.MinLenOfRun-1);
    Qnum=(sqword)(Zero=(!Mc.MinBitCount&&!Mc.MinNumOfRun)); return MeNoError;
}

template <typename T>
bool mnext_t<T>::NextMask(T&mask,minfo_t&info) {
    mstack_t<T>*sp=StackPtr;
    if (sp==Stack) return false;
    if (Zero) {
        if (&info!=&DummyInfo)
        { info.BitCount=info.NumOfRun=0; info.Bsr=info.Bsf=-1; }
        mask=0; Zero=false; return true;
    }
    int hi=sp->Hi,lo=sp->Lo,cnt=hi-lo+sp[-1].Count;
    for (;;) {
        if (sp<StackMax&&lo>Mc.MinLenOfRun&&cnt<Mc.MaxBitCount) {
            sp->Count=(byte)cnt; sp->Hi=(byte)hi; sp->Lo=(byte)lo;
            hi=Mc.MinLenOfRun; StackPtr=++sp; sp->Length=(byte)(lo-1); lo=0;
        } else lo--;
        cnt=hi-lo;
        while (lo<0||cnt>Mc.MaxLenOfRun) {
            if (hi<Mc.MinLenOfRun) { hi=Mc.MinLenOfRun; lo=0; cnt=hi; }
            else { hi++; cnt=Mc.MinLenOfRun; lo=hi-cnt; }
            if (hi<=sp->Length) break;
            StackPtr=--sp;
            if (sp==Stack) return false;
            hi=sp->Hi; lo=sp->Lo-1; cnt=hi-lo;
        }
        cnt+=sp[-1].Count;
        if (cnt>Mc.MaxBitCount) continue;
        sp->Mask=(T)(sp[-1].Mask-((T)1<<lo));
        if (hi<(int)sizeof(T)*8) sp->Mask=(T)(sp->Mask+((T)1<<hi));
        sp->Hi=(byte)hi; sp->Lo=(byte)lo;
        if (cnt>=Mc.MinBitCount&&sp>=StackMin) {
           if (Qnum==Mc.Limit) { StackPtr=Stack; return false; }
           Qnum++; mask=sp->Mask;
           if (&info!=&DummyInfo) {
               info.BitCount=(byte)cnt;
               info.NumOfRun=(byte)(sp-Stack);
               info.Bsr=(char)(Stack[1].Hi-1);
               info.Bsf=(char)lo;
           }
           return true;
        }
    }
}

/* bit==1:0-1   bit==2:0-3   bit==3:0-7   bit==4:0-f */
template <typename T>
char*mtoa(T m,int width=0,int bit=1) {
    static char buf[sizeof m*8+4],digit[]="0123456789abcdef";
    int i,k; enum { w=(int)sizeof(T)*8 };
    if (bit<1) bit=1; else if (bit>4) bit=4;
    if (width<=0||width>w) width=w;
    for (k=0,i=(width-1)/bit*bit;i>=0;i-=bit,k++)
        buf[k]=digit[(unsigned)(m>>i)&((1<<bit)-1)];
    buf[k]=0; return buf;
}
#endif

マスクをメモリ上に配列として列挙する `maskex.hpp`

/* maskex.hpp : coded by Isaku WADA(isaku@pb4.so-net.ne.jp) 2025
Brute-force search for integers
You need mask.hpp, mex-main.hpp and shuffle.hpp to use this program.
If you define SHUFFLE2 then you also need shuffle2.hpp.
If you define M_RECU then you also need mex-recu.hpp.
If you define M_MINI then you also need mex-mini.hpp.
*/
#if !defined(MASKEX_HPP)
 #define MASKEX_HPP
 #include <time.h>
 #define MsecClock() ((int)(clock()*(1000.0/CLOCKS_PER_SEC)))
 #include "mask.hpp"
 #include "shuffle.hpp"
 #if defined(M_MAIN)
  #include "mex-main.hpp"
 #endif
 #if defined(M_RECU)
  #include "mex-recu.hpp"
 #endif
 #if defined(M_MINI)
  #include "mex-mini.hpp"
 #endif
 #if !defined(M_MAIN) && !defined(M_RECU) && !defined(M_MINI)
  #include "mex-main.hpp"
 #endif
 #if defined(MEX_MAIN_HPP)
  #define MEX_NAME    "Main"
  #define NumOfMasks   NumOfMasksMain
  #define GenMasks     GenMasksMain
  #define GenMasksHeap GenMasksHeapMain
 #elif defined(MEX_RECU_HPP)
  #define MEX_NAME    "Recu"
  #define NumOfMasks   NumOfMasksRecu
  #define GenMasks     GenMasksRecu
  #define GenMasksHeap GenMasksHeapRecu
 #elif defined(MEX_MINI_HPP)
  #define MEX_NAME    "Mini"
  #define NumOfMasks   NumOfMasksMini
  #define GenMasks     GenMasksMini
  #define GenMasksHeap GenMasksHeapMini
 #endif

#endif

マスクをメモリ上に配列として列挙する。既定の実装 `mex-main.hpp`

/* mex-main.hpp : coded by Isaku WADA(isaku@pb4.so-net.ne.jp)2025
Brute-force search for integers
The 'GenMasks' and 'GenMasksHeap' functions generate masks and their
information. They store the results in an array. If a non-zero seed argument
is provided to 'GenMasks' or 'GenMasksHeap', the output array is shuffled.
To use this program, you need mask.hpp, maskex.hpp, and shuffle.hpp.
This reduces the number of function calles.
*/

#if !defined(MEX_MAIN_HPP)
 #define MEX_MAIN_HPP

template <typename T>
struct mex_main_t {
    mstack_t<T>Stack[sizeof(T)*4+1],*StackMin,*StackMax; mconf_t Mc;
    mex_main_t(mconf_t&conf);
};

template <typename T>
mex_main_t<T>::mex_main_t(mconf_t&conf) {
    Mc.Complete(conf,(int)sizeof(T)*8);
    for (int i=0;i<(int)sizeof Stack;i++) ((char*)Stack)[i]=0;
    StackMin=Stack+Mc.MinNumOfRun;
    StackMax=Stack+Mc.MaxNumOfRun;
    Stack[1].Length=(byte)Mc.MaxWidth;
    Stack[1].Hi=(byte)(Mc.MinLenOfRun-1);
}

template <typename T>
sqword NumOfMasksMain(mconf_t&conf) {
    mex_main_t<T>t(conf);
    if (conf.ErrCode) return MeError;
    mstack_t<T>*sp=t.Stack+1; int hi=sp->Hi,lo=sp->Lo,cnt=sp->Count;
    sqword num=(sqword)(!t.Mc.MinBitCount&&!t.Mc.MinNumOfRun);
    for (;;) {
        if (sp<t.StackMax&&lo>t.Mc.MinLenOfRun&&cnt<t.Mc.MaxBitCount) {
            sp->Hi=(byte)hi; sp->Lo=(byte)lo; sp->Count=(byte)cnt;
            hi=t.Mc.MinLenOfRun; sp++; sp->Length=(byte)(lo-1); lo=0;
        } else lo--;
        cnt=hi-lo;
        while (lo<0||cnt>t.Mc.MaxLenOfRun) {
            if (hi<t.Mc.MinLenOfRun)
            { hi=t.Mc.MinLenOfRun; lo=0; cnt=hi; }
            else { hi++; cnt=t.Mc.MinLenOfRun; lo=hi-cnt; }
            if (hi<=sp->Length) break;
            if (--sp==t.Stack) break;
            hi=sp->Hi; lo=sp->Lo-1; cnt=hi-lo;
        }
        if (sp==t.Stack) break;
        cnt+=sp[-1].Count;
        if (cnt>=t.Mc.MinBitCount&&cnt<=t.Mc.MaxBitCount&&sp>=t.StackMin) {
            if (num==t.Mc.Limit) break;
            num++;
        }
    }
    return num;
}

template <typename T>
int GenMasksMain(mconf_t&conf,T*tbl,int sz,minfo_t*info=0,unsigned seed=0) {
    if (sz==0) return 0;
    int num=0; conf.Limit=sz; mex_main_t<T>t(conf);
    if (conf.ErrCode) return MeError;
    if (conf.ShuffleMsec!=-1) conf.GenMsec=MsecClock();
    conf.ShuffleMsec=0;
    if (!t.Mc.MinBitCount&&!t.Mc.MinNumOfRun) {
        tbl[0]=0; num=1;
        if (info) {
            info->BitCount=info->NumOfRun=0;
            info->Bsr=info->Bsf=-1;
        }
    }
    mstack_t<T>*sp=t.Stack+1; int hi=sp->Hi,lo=sp->Lo,cnt=sp->Count;
    for (;;) {
        if (sp<t.StackMax&&lo>t.Mc.MinLenOfRun&&cnt<t.Mc.MaxBitCount) {
            sp->Hi=(byte)hi; sp->Lo=(byte)lo; sp->Count=(byte)cnt;
            hi=t.Mc.MinLenOfRun; sp++; lo=0; sp->Length=(byte)(sp[-1].Lo-1);
        } else lo--;
        cnt=hi-lo;
        while (lo<0||cnt>t.Mc.MaxLenOfRun) {
            if (hi<t.Mc.MinLenOfRun)
            { hi=t.Mc.MinLenOfRun; lo=0; cnt=hi; }
            else { hi++; cnt=t.Mc.MinLenOfRun; lo=hi-cnt; }
            if (hi<=sp->Length) break;
            if (--sp==t.Stack) break;
            hi=sp->Hi; lo=sp->Lo-1; cnt=hi-lo;
        }
        if (sp==t.Stack) break;
        cnt+=sp[-1].Count;
        if (cnt>t.Mc.MaxBitCount) continue;
        sp->Mask=(T)(sp[-1].Mask-((T)1<<lo));
        if (hi<(int)sizeof(T)*8) sp->Mask=(T)(sp->Mask+((T)1<<hi));
        if (cnt>=t.Mc.MinBitCount&&sp>=t.StackMin) {
            if (num>=sz) break;
            if (info) {
                sp->Hi=(byte)hi;
                info[num].BitCount=(byte)cnt;
                info[num].NumOfRun=(byte)(sp-t.Stack);
                info[num].Bsr=(char)(t.Stack[1].Hi-1);
                info[num].Bsf=(char)lo;
            }
            tbl[num++]=sp->Mask;
        }
    }
    if (conf.ErrCode)
    { conf.GenMsec=MsecClock()-conf.GenMsec; return MeError; }
    if (seed) {
        conf.ShuffleMsec=MsecClock();
        num=ShuffleArray(tbl,info, num,seed);
        if (num<0) conf.SetMerr0(MeNewFailed);
        conf.ShuffleMsec=MsecClock()-conf.ShuffleMsec;
    }
    conf.GenMsec=MsecClock()-conf.GenMsec; return num;
}

template <typename T>
int GenMasksMain(mconf_t&conf,T*tbl,int sz,unsigned seed,minfo_t*info=0)
{ return GenMasksMain(conf,tbl,sz,info,seed); }

template <typename T>
int GenMasksHeapMain(mconf_t&conf,T*&tbl,int sz,minfo_t*&info=NoInfo,
                     unsigned seed=0) {
    tbl=0; info=0;
    if (sz==0) return 0;
    conf.GenMsec=MsecClock(); conf.ShuffleMsec=-1; conf.Limit=sz;
    int num=(int)NumOfMasksMain<T>(conf);
    if (num<=0) {
        conf.GenMsec=MsecClock()-conf.GenMsec; conf.ShuffleMsec=0;
        return num;
    }
    try { tbl=new T[num]; } catch (...) { tbl=0; }
    if (tbl==0) {
        conf.GenMsec=MsecClock()-conf.GenMsec; conf.ShuffleMsec=0;
        return conf.SetMerr0(MeNewFailed);
    }
    if (&info!=&NoInfo) {
        try { info=new minfo_t[num]; } catch (...) { info=0; }
        if (info==0) {
            delete[]tbl; tbl=0; conf.GenMsec=MsecClock()-conf.GenMsec;
            conf.ShuffleMsec=0; return conf.SetMerr0(MeNewFailed);
        }
    }
    num=GenMasksMain(conf,tbl,num,info,seed);
    if (num<=0) { delete[]info; delete[]tbl; info=0; tbl=0; }
    return num;
}

template <typename T>
int GenMasksHeapMain(mconf_t&conf,T*&tbl,int sz,unsigned seed,
                     minfo_t*&info=NoInfo)
{ return GenMasksHeapMain(conf,tbl,sz,info,seed); }

#endif

１個、または２個の配列をシャッフルする `shuffle.hpp`

/* shuffle.hpp : coded by Isaku WADA(isaku@pb4.so-net.ne.jp)2025 */
#if !defined(SHUFFLE_HPP)
 #define SHUFFLE_HPP
 #if 0
    /* shuffle.cpp : An example of 'shuffle.hpp' */
    #include <stdio.h>
    #include "shuffle.hpp"
    int main(void) {
        enum { Num=10, Seed=1 };
        static int array[Num]={0,1,2,3,4,5,6,7,8,9};
        ShuffleArray(array,No2nd,Num,Seed);
        for (int i=0;i<Num;i++) printf(" %d",array[i]);
        fputc('\n',stdout); return 0;
    }
    /* results : 8 7 4 9 6 1 5 2 0 3 */
 #endif

/*
   Following BSIZE macro specifies shuffle block size.
   If BSIZE is defined as 1 then this program does Fisher-Yates
   shuffle. It is slow because of memory cache miss.
   if BSIZE is not defined as 1, this program does block based shuffle.
*/
 #if !defined(BSIZE)
  #define BSIZE 16
 #endif
 #if 2 * BSIZE -1 == -2
  #undef BSIZE
  #define BSIZE 1
 #endif

 #define No2nd ((char*)0)
 #define INIT_XSRAND_SEED(S) (S=((S)?(S)*0x6789abcd:~(unsigned)0))

static inline unsigned xsrand(unsigned*pseed)
{ unsigned x=*pseed; x^=x<<13; x^=x>>17; return*pseed=x^(x<<5); }

 #if BSIZE <= 1

/* Fisher-Yates shuffle */

template <typename T,typename U>
int ShuffleArray(T*a,U*b,int size,unsigned seed=1) {
    INIT_XSRAND_SEED(seed);
    for (int s=size-1;s>0;s--) {
         int i=(int)(xsrand(&seed)%(s+1));
         T t=a[s]; a[s]=a[i]; a[i]=t;
         if (b) { U u=b[s]; b[s]=b[i]; b[i]=u; }
    }
    return size;
}

 #else

/* block based shuffle */

template <typename T>
struct sblock_t { T x[BSIZE]; };

template <typename T,typename U>
union stmp_t { sblock_t<T>t; sblock_t<U>u; };

template <typename T,typename U>
void SwapModBlock(T*a,U*b,int r,int m,int w) {
    r*=BSIZE;
    for (int i=0;i<w;i++) { T t=a[r+i]; a[r+i]=a[m+i]; a[m+i]=t; }
    if (b==0) return;
    for (int i=0;i<w;i++) { U u=b[r+i]; b[r+i]=b[m+i]; b[m+i]=u; }
}

template <typename T,typename U>
void SwapBlock(T*a,U*b,int r,int m,stmp_t<T,U>*tmp) {
    r*=BSIZE;
    tmp->t=*(sblock_t<T>*)(a+r);
    *(sblock_t<T>*)(a+r)=*(sblock_t<T>*)(a+m); 
    *(sblock_t<T>*)(a+m)=tmp->t; 
    if (b==0) return;
    tmp->u=*(sblock_t<U>*)(b+r);
    *(sblock_t<U>*)(b+r)=*(sblock_t<U>*)(b+m); 
    *(sblock_t<U>*)(b+m)=tmp->u; 
}

/*
   If you define NO_LOCAL macro then
   this program does not shuffle inner of each block.
   Therfore shuffling becomes fast.
*/
  #if defined(NO_LOCAL)

template <typename T,typename U>
int ShuffleArray(T*a,U*b,int size,unsigned seed=1) {
    int n=size/BSIZE,m=n*BSIZE,mod=size%BSIZE; stmp_t<T,U>*tmp;
    try { tmp=new stmp_t<T,U>; } catch (...) { tmp=0; }
    if (tmp==0) return-1;
    INIT_XSRAND_SEED(seed);
    if (mod&&n) SwapModBlock(a,b,(int)(xsrand(&seed)%(n+1)),m,mod);
    for (n--,m-=BSIZE;n>0;n--,m-=BSIZE)
        SwapBlock(a,b,(int)(xsrand(&seed)%(n+1)),m,tmp);
    delete tmp; return size;
}

  #else

template <typename T,typename U>
void ShuffleLocal(T*a,U*b,int start,int end,unsigned*pseed) {
    for (int i=end;i>start;i--) {
        int j=start+(int)(xsrand(pseed)%(i-start+1));
        T t=a[i]; a[i]=a[j]; a[j]=t;
        if (b) { U u=b[i]; b[i]=b[j]; b[j]=u; }
    }
}

template <typename T,typename U>
int ShuffleArray(T*a,U*b,int size,unsigned seed=1) {
    int n=size/BSIZE,m=n*BSIZE,mod=size%BSIZE; stmp_t<T,U>*tmp;
    try { tmp=new stmp_t<T,U>; } catch (...) { tmp=0; }
    if (tmp==0) return-1;
    INIT_XSRAND_SEED(seed);
    for (int i=0;i<size;i+=BSIZE) {
        int end=(i+BSIZE<size)?(i+BSIZE-1):(size-1);
        ShuffleLocal(a,b,i,end,&seed);
    }
    if (mod&&n) {
        ShuffleLocal(a,b,size-BSIZE,size-1,&seed);
        SwapModBlock(a,b,(int)(xsrand(&seed)%(n+1)),m,mod);
    }
    for (n--,m-=BSIZE;n>0;n--,m-=BSIZE)
        SwapBlock(a,b,(int)(xsrand(&seed)%(n+1)),m,tmp);
    delete tmp; return size;
}
  #endif
 #endif
#endif

(オプション)マスクをメモリ上に配列として列挙する。再帰呼び出しによる実装 `mex-recu.hpp`

/* mex-recu.hpp : (recursive) coded by Isaku WADA(isaku@pb4.so-net.ne.jp)2025
Brute-force search for integers
The GenMasks and GenMasksHeap functions generate masks and their
information. They store the results in an array. If a non-zero seed argument
is provided to GenMasks or GenMasksHeap, the output array is shuffled.
To use this program, you need mask.hpp, maskex.hpp, and shuffle.hpp.  
This program is included by maskex.hpp when M_RECU is defined. It
utilizes recursive function calls and is designed for a small MaxNumOfRun.
*/

#if !defined(MEX_RECU_HPP)
 #define MEX_RECU_HPP
template <typename T>
struct mex_recu_t {
    mconf_t Mc; T*pTbl; minfo_t*pInfo;
    int Hi,Runs,IntNum,TblSz; sqword Qnum;
    mex_recu_t(T*tbl,minfo_t*info,int sz,mconf_t&conf);
    bool NumOfMasksHelpRecu(int length,int ocnt);
    bool GenMasksHelpRecu(int length,int ocnt,T omask);
};

template <typename T>
mex_recu_t<T>::mex_recu_t(T*tbl,minfo_t*info,int sz,mconf_t&conf) {
    Mc.Complete(conf,(int)sizeof(T)*8);
    pTbl=tbl; pInfo=info; Mc.Src=&conf; TblSz=sz; Hi=Runs=0;
    Qnum=IntNum=(int)(!Mc.MinBitCount&&!Mc.MinNumOfRun);
    (void)DummyInfo; (void)NoInfo;
}

template <typename T>
bool mex_recu_t<T>::NumOfMasksHelpRecu(int length,int ocnt) {
    Runs++;
    for (int hi=Mc.MinLenOfRun-1;hi<=length;hi++)
     for (int lo=hi-Mc.MinLenOfRun;lo>=0;lo--) {
         int cnt=hi-lo;
         if (cnt>Mc.MaxLenOfRun) break;
         cnt+=ocnt;
         if (cnt>Mc.MaxBitCount) break;
         if (cnt>=Mc.MinBitCount&&Runs>=Mc.MinNumOfRun) {
              if (Qnum==Mc.Limit) return false;
              Qnum++;
         }
         if (Runs<Mc.MaxNumOfRun&&cnt<Mc.MaxBitCount)
          if (!NumOfMasksHelpRecu(lo-1,cnt)) return false;
     }
    Runs--; return true;
}

template <typename T>
sqword NumOfMasksRecu(mconf_t&conf) {
    mex_recu_t<T>t((T*)0,(minfo_t*)0,0,conf);
    if (conf.ErrCode) return MeError;
    t.NumOfMasksHelpRecu(t.Mc.MaxWidth,0);
    if (conf.ErrCode) return MeError;
    return t.Qnum;
}

template <typename T>
bool mex_recu_t<T>::GenMasksHelpRecu(int length,int ocnt,T omask) {
    Runs++;
    for (int hi=Mc.MinLenOfRun-1;hi<=length;hi++) {
        if (Runs==1) Hi=hi;
        for (int lo=hi-Mc.MinLenOfRun;lo>=0;lo--) {
            int cnt=hi-lo;
            if (cnt>Mc.MaxLenOfRun) break;
            cnt+=ocnt;
            if (cnt>Mc.MaxBitCount) break;
            T mask=(T)(omask-((T)1<<lo));
            if (hi<(int)sizeof(T)*8) mask=(T)(mask+((T)1<<hi));
            if (cnt>=Mc.MinBitCount&&Runs>=Mc.MinNumOfRun) {
                 if (IntNum>=TblSz) return false;
                 if (pInfo) {
                     pInfo[IntNum].BitCount=(byte)cnt;
                     pInfo[IntNum].NumOfRun=(byte)Runs;
                     pInfo[IntNum].Bsr=(char)(Hi-1);
                     pInfo[IntNum].Bsf=(char)lo;
                 }
                 pTbl[IntNum++]=mask;
             }
            if (Runs<Mc.MaxNumOfRun&&cnt<Mc.MaxBitCount)
             if (!GenMasksHelpRecu(lo-1,cnt,mask)) return false;
        }
    }
    Runs--; return true;
}

template <typename T>
int GenMasksRecu(mconf_t&conf,T*tbl,int sz,
                 minfo_t*info=0,unsigned seed=0) {
    if (sz==0) return 0;
    conf.Limit=sz; mex_recu_t<T>t(tbl,info,sz,conf);
    if (conf.ErrCode) return MeError;
    if (conf.ShuffleMsec!=-1) conf.GenMsec=MsecClock();
    conf.ShuffleMsec=0;
    if (t.IntNum) {
        tbl[0]=0;
        if (info) {
            info[0].BitCount=0;
            info[0].NumOfRun=0;
            info[0].Bsr=(char)-1;
            info[0].Bsf=(char)-1;
        }
    }
    t.GenMasksHelpRecu(t.Mc.MaxWidth,0,(T)0);
    if (conf.ErrCode)
    { conf.GenMsec=MsecClock()-conf.GenMsec; return MeError; }
    if (seed) {
        conf.ShuffleMsec=MsecClock();
        t.IntNum=ShuffleArray(tbl,info, t.IntNum,seed);
        if (t.IntNum<0) conf.SetMerr0(MeNewFailed);
        conf.ShuffleMsec=MsecClock()-conf.ShuffleMsec;
    }
    conf.GenMsec=MsecClock()-conf.GenMsec; return t.IntNum;
}

template <typename T>
int GenMasksRecu(mconf_t&conf,T*tbl,int sz,
                 unsigned seed,minfo_t*info=0)
{ return GenMasksRecu(conf,tbl,sz,info,seed); }

template <typename T>
int GenMasksHeapRecu(mconf_t&conf,T*&tbl,int sz,
                     minfo_t*&info=NoInfo,unsigned seed=0) {
    tbl=0; info=0;
    if (sz==0) return 0;
    conf.GenMsec=MsecClock(); conf.ShuffleMsec=-1;
    conf.Limit=sz;
    int num=(int)NumOfMasksRecu<T>(conf);
    if (num<=0) { conf.GenMsec=MsecClock()-conf.GenMsec; return num; }
    try { tbl=new T[num]; } catch (...) { tbl=0; }
    if (tbl==0) {
        conf.GenMsec=MsecClock()-conf.GenMsec; conf.ShuffleMsec=0;
        return conf.SetMerr0(MeNewFailed);
    }
    if (&info!=&NoInfo) {
        try { info=new minfo_t[num]; } catch (...) { info=0; }
        if (info==0) {
            delete[]tbl; tbl=0; conf.GenMsec=MsecClock()-conf.GenMsec;
            conf.ShuffleMsec=0; return conf.SetMerr0(MeNewFailed);
        }
    }
    num=GenMasksRecu(conf,tbl,num,info,seed);
    if (num<=0) { delete[]info; delete[]tbl; info=0; tbl=0; }
    return num;
}

template <typename T>
int GenMasksHeapRecu(mconf_t&conf,T*&tbl,int sz,
                     unsigned seed,minfo_t*&info=NoInfo)
{ return GenMasksHeapRecu(conf,tbl,sz,info,seed); }

#endif

(オプション)マスクをメモリ上に配列として列挙する。小さな実装 `mex-mini.hpp`

/* mex-mini.hpp : (Simple) coded by Isaku WADA(isaku@pb4.so-net.ne.jp)2025
Brute-force search for integers
The GenMasks and GenMasksHeap functions generate masks and their
information. They store the results in an array. If a non-zero seed argument
is provided to GenMasks or GenMasksHeap, the output array is shuffled.
To use this program, you need mask.hpp, maskex.hpp, and shuffle.hpp.  
This program is included by maskex.hpp when M_MINI is defined.*/
#if !defined(MEX_MINI_HPP)
 #define MEX_MINI_HPP

template <typename T>
sqword NumOfMasksMini(mconf_t&conf) {
    T dummy; mnext_t<T>t(conf);
    if (conf.ErrCode) return MeError;
    while (t.NextMask(dummy)) { }
    return t.Qnum;
}

template <typename T>
int GenMasksMini(mconf_t&conf,T*tbl,int sz,
                 minfo_t*info=0,unsigned seed=0) {
    if (sz==0) return 0;
    conf.Limit=sz; mnext_t<T>t(conf); int num=0;
    if (conf.ErrCode) return MeError;
    if (conf.ShuffleMsec!=-1) conf.GenMsec=MsecClock();
    conf.ShuffleMsec=0;
    if (info==0) while (t.NextMask(tbl[num])) num++;
    else while (t.NextMask(tbl[num],info[num])) num++;
    if (seed) {
        conf.ShuffleMsec=MsecClock();
        num=ShuffleArray(tbl,info, num,seed);
        if (num<0) conf.SetMerr0(MeNewFailed);
        conf.ShuffleMsec=MsecClock()-conf.ShuffleMsec;
    }
    conf.GenMsec=MsecClock()-conf.GenMsec; return num;
}

template <typename T>
int GenMasksMini(mconf_t&conf,T*tbl,int sz,
                 unsigned seed,minfo_t*info=0)
{ return GenMasksMini(conf,tbl,sz,info,seed); }

template <typename T>
int GenMasksHeapMini(mconf_t&conf,T*&tbl,int sz,
                     minfo_t*&info=NoInfo,unsigned seed=0) {
    tbl=0; info=0;
    if (sz==0) return 0;
    conf.GenMsec=MsecClock(); conf.ShuffleMsec=-1;
    conf.Limit=sz;
    int num=(int)NumOfMasksMini<T>(conf);
    if (num<=0) {
        conf.GenMsec=MsecClock()-conf.GenMsec;
        conf.ShuffleMsec=0; return num;
    }
    try { tbl=new T[num]; } catch (...) { tbl=0; }
    if (tbl==0) {
        conf.GenMsec=MsecClock()-conf.GenMsec; conf.ShuffleMsec=0;
        return conf.SetMerr0(MeNewFailed);
    }
    if (&info!=&NoInfo) {
        try { info=new minfo_t[num]; } catch (...) { info=0; }
        if (info==0) {
            delete[]tbl; tbl=0; conf.GenMsec=MsecClock()-conf.GenMsec;
            conf.ShuffleMsec=0; return conf.SetMerr0(MeNewFailed);
        }
    }
    num=GenMasksMini(conf,tbl,num,info,seed);
    if (num<=0) { delete[]info; delete[]tbl; info=0; tbl=0; }
    return num;
}

template <typename T>
int GenMasksHeapMini(mconf_t&conf,T*&tbl,int sz,
                     unsigned seed,minfo_t*&info=NoInfo)
{ return GenMasksHeapMini(conf,tbl,sz,info,seed); }

#endif

整数の力まかせ探索(ソースコード)

目次

基本プログラム mask.hpp

マスクをメモリ上に配列として列挙する maskex.hpp

マスクをメモリ上に配列として列挙する。既定の実装 mex-main.hpp

１個、または２個の配列をシャッフルする shuffle.hpp

(オプション)マスクをメモリ上に配列として列挙する。再帰呼び出しによる実装 mex-recu.hpp

(オプション)マスクをメモリ上に配列として列挙する。小さな実装 mex-mini.hpp

基本プログラム `mask.hpp`

マスクをメモリ上に配列として列挙する `maskex.hpp`

マスクをメモリ上に配列として列挙する。既定の実装 `mex-main.hpp`

１個、または２個の配列をシャッフルする `shuffle.hpp`

(オプション)マスクをメモリ上に配列として列挙する。再帰呼び出しによる実装 `mex-recu.hpp`

(オプション)マスクをメモリ上に配列として列挙する。小さな実装 `mex-mini.hpp`