permutation

id:nuc:20060624:p2 より。

'1'から'7'までの数字を一回だけ使って作れる、7文字の文字列のすべての組み合わせを

出力するプログラムを、「できるだけ短く」書け。 (※1)

id:shinichiro_hさんが82Byteをたたき出した。(→id:shinichiro_h:20060626#1151302752)

i,k;main(t){for(;++i<1<<23;k?0:printf("%d\n",i))for(t=i,k=254;t;t/=10)k^=1<<t%10;}

原理は簡単で、i=0から大きな数までをぶん回し、10進数で考えたときにそれぞれの桁を調べて1から7の数字が1回ずつ出てきているのかを調べるというものだ。

ちなみに、上のプログラム中の 1<<23 = 8388608 で、条件を満たす数のうち一番大きな数である7654321よりわずかに(?)大きな2のn乗。254 = 11111110bである。

「k^=」の部分が巧妙で、「123456777」のような数字でもマッチしてしまいそうだが、実際は、i の値の範囲が上のように限られているため、これにはマッチしない。

しかし思うにPKU的には以下のように書いてさらに2バイト縮み80byteである。

i,k;main(t){for(;++i<1<<23;k=k?254:printf("%d\n",i))for(t=i;t;t/=10)k^=1<<t%10;}

printfの戻り値はvoidだが、これを0と仮定している。※1の条件を満たす数は連続した整数では有りえないので(証明略)、条件を満たす整数のひとつ前は条件を満たさない整数である。

よって条件を満たした次のループではkを0と初期化しても、iの各桁に1〜7の数を含んでいるなら結果kは非0になり(同じ数を偶数回含むケースについては略)、次のループでkは254に初期化される。iの各桁に1〜7の数を全く含まず結果kが0になる場合には、その次の数が※1の条件を満たすことはありえないので、次のループもkを0で初期化して良い。

こんなことが瞬間的に思いつく俺様、すげーぜ！！とか思っていたら、なんのことはなかった。id:kurimuraさんが75byteにしてしまった。(→id:kurimura:20060626)

i=1e7,k;

main(t){

  for(;t=--i;k||printf("%o\n",i))

    for(k=254;t;t/=8)k^=1<<t%8;

}

またもや敗北…(´ω`)