2進数を利用した組み合わせ(Combination)生成による与えられた文字列中の全ての文字列を返すコード

2進数を利用した、Combination生成による、与えられた文字列に含まれる全ての文字列を返すコード。

Combinationを求めるアルゴリズムは、技術評論社刊、「C言語による最新アルゴリズム辞典」（奥村晴彦　著）を参考にしました。（2進数を用いた非常に巧妙な方法です）

順序は入れ替わりません。

for terminal.

alice.c

#include    <stdio.h>
#include    <stdlib.h>
#include    <string.h>
int N; 
int K;
int t;
typedef unsigned long set;
char    word[1024];
#define first(n)    ((set) ((1U << (n)) -1U))

set nextset(set x)
{
        set smallest,ripple,new_smallest,ones;

    smallest = x & -x;
    ripple = x +smallest;
    new_smallest = ripple & -ripple;
    ones =((new_smallest /smallest) >>1)-1;
    return ripple| ones;
}
void printset(set s)
{
    int i;

    for(i=1;i<=N;i++) {
    if (s & 1) printf("%c",word[i-1]);
    s>>=1;
    }
    printf("\n");
}

void conv()
{
    int i;
    set x;

    x=first(K);
    while(! (x&~first(N))) {
        printf("%5d :",t); printset(x);
        x=nextset(x); t++;
    }
}
int main(int argc,char *argv[]) {

    if (argc!=2) {
        fprintf(stderr,"Usage alice word\n");
        exit(0);
        }

    sscanf(*(++argv),"%s",word);
    N=strlen(word);
    t=1;
    for(K=1;K<=N;K++) {
        conv();
        }
}

特に環境依存的なところはないので、Cの開発環境があれば、簡単にコンパイルができます。

To compile: cc alice.c -o alice
Usage: alice word
実行結果：

$ alice alice
    1 :a
    2 :l
    3 :i
    4 :c
    5 :e
    6 :al
    7 :ai
    8 :li
    9 :ac
   10 :lc
   11 :ic
   12 :ae
   13 :le
   14 :ie
   15 :ce
   16 :ali
   17 :alc
   18 :aic
   19 :lic
   20 :ale
   21 :aie
   22 :lie
   23 :ace
   24 :lce
   25 :ice
   26 :alic
   27 :alie
   28 :alce
   29 :aice
   30 :lice
   31 :alice
$