君ならどう書く? in 厶板

いろんなとこで行われている「君ならどう書く?」をム板でやってみませんか?既出?

良いコードを求めて出題しても良し。
自分がもっとも良いと思うコードを提示して他者に挑戦を
挑むも良し。

題材は
・パズル
・シェルスクリプトで自動化したくなった作業
・プログラム中で出くわしたちょっとした処理
など何でもOK。あまりにも規模の大きいものは遠慮してください。

使用言語等については出題者が指示すること。
ただし、あまりに条件の限定的なものはつまらなくなるので、他スレで。

巡回セールスマン問題の解法

じゃあ、
問題:
配列の要素をランダムにシャッフルするコード

配列じゃなくてリストなどでもOK

ついでに

問題:
ビット列をランダムにシャッフルするコード
もちろん立っているビットの数が変わってはいけない

extern int ビット数を数える(byte);

byte shuffle(byte target)
{
　static List<List<byte>> array;
　if (array == null){
　　array = new List<List<byte>>(sizeof(byte));
　
　　for(int i = 0; i < 255; i++)
　　{
　　　array[ビットを数える(i)].add(i);
　　}
　}

　List<int> backet = array[ビットを数える(target)];

　return backet[Math.Rand(backet.size)];
}

流れ的にこんな漢字化

35歳キモPG男が今年中に20代のアイドルPG女と添い遂げるプログラム書いてよ

まずはアイドルPGより仕事ができるかどうか
によるんじゃないかな？
その辺はif文で制御だな。

>>3
@array=sort{(int rand 3)-1}@array;

>>4って
ビット演算ですっきりやれないのかな？

>>4を逐次的にやるようにするとこんな感じかな。効率良くは無さそうだが。
# 言語指定が無いから擬似言語で失礼
procedure bitsuffle(BitArray bits)
  on  = pop(bits) // 立っているビットの数
  len = bits.length
  for i = [0, bits.length)
    if rand(len--) < on // 0 <= rand < len, rand ∈ Z
      bits[i] = 1
      on--
    else
      bits[i] = 0

１. ビット数の範囲内で表せる乱数を生成する
２. １の乱数とビット列をXORする
３. １で作った値を1ビットローテート
４． ２と３でXOR

でランダムにならないかな？ビット演算よくわかんないけど。

それだと立ってるビット数かわるんじゃね？

0b10010110 ... 0
0b00100100 ... 1
0b10110010 ... 2
0b01100101 ... 3
0b11010111 ... 4

>>4
完全にランダムにはならないけど、(32ビット整数の場合)

int n = rand() % 32;
x = (x >> n) | (x << (32-n));
x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF;
x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F;
x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3;
x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999;

これを何回か繰り返すとか。

テーブルがいいんじゃね？

真面目にテーブル作ったらめちゃくちゃ大きくなるような。

というか、問題がコア過ぎ(笑) >>4

自己出力プログラム

10 LIST

Q

>>4
コンパイル通してないけど、C にて。
一度ビット並びを配列に展開して、ランダムに組み立てなおすようにしてみた。

typedef unsigned int WORD;
#define BITLEN (sizeof(WORD) * 8)

WORD bit_shuffle(WORD x)
{
　WORD bittbl[BITLEN];
　int p;

　for(p = 0; p < BITLEN; p++) {
　　bittbl[p] = x & 1;
　　x >>= 1;
　}

　p = BITLEN;
　while(p > 1) {
　　int r = rand() % p;
　　x = (x | bittbl[r]) << 1;
　　bittbl[r] = bittbl[--p];
　}

　return x | bittbl[0];
}

>>16
Q

>>4
もう一個作ってみた。
0ビット目とランダムビット目を入れ替えていくのをループさせるタイプ。

typedef unsigned int WORD;
#define BITLEN (sizeof(WORD) * 8)
#define LOOPCNT 100

WORD bit_shuffle(WORD x)
{
　int c = LOOPCNT;
　do {
　　int r = rand()%(BITLEN-1)+1;
　　WORD b = (WORD)1 << r;
　　if(x & b) {
　　　if(!(x & 1)) x ^= b | 1;
　　}
　　else {
　　　if(x & 1) x ^= b | 1;
　　}
　} while(--c);

　return x;
}

>>3
そういやVCのSTLのは高速化ねらって厳密にランダムには並べ替えてないんだよね。
2つ以上要素があるとき、シャッフル前と同じ並びになることがない。
だから要素が少ないとき統計的に問題がある。

for(i = 1; i < length; i++) swap(p+i, p+random(i));
//randomは引数未満の正の整数をランダムに返す

みたいなのでいいんだっけか？自信ない

【ネガティブ派遣根性チェック】

3つ以上、思い当たる点があればアナタの性格はひん曲がっており、ネガティブ負け組人生を歩んでいます。

□派遣先の人事権のある社員の意見はたとえ間違っていてもマンセーする
□派遣先から「いつまでもここで仕事してくださいね(安い金でｗ)」と言われている
□自社に仕事を持ち帰れるように言われるとムカつく
□自社で仕事なんてできるわけがない
□派遣労働の問題点の話題が出ると感情剥き出しにする
□派遣労働の問題を指摘する人は嫌いだ
□派遣先には仕事だけでなく自分のプライベートについても指示して欲しい
□自分の月額金額を知らない
□派遣先社員より自分の生涯収入が低いのは当然だ
□派遣先に尻尾を振り、いつまでも派遣を続けることが大切だ

>>16
HQ

uint = 32bitかつrandが0から2^32までの値を生成すると仮定する。
理屈としては2,4,8,16,32とシャッフルする範囲を拡大していく方法でO(logN)
uint bit_shuffle(uint x){
    uint r1,r2;
    r1 = rand() & 0x55555555;
    r2 =   r1 ^ 0x55555555;
    x = (x & (r1|r1<<1) ) | (x>>1 & r2) | (x<<1 & r2<<1);
    r1 = rand() & 0x33333333;
    r2 =   r1 ^ 0x33333333;
    x = (x & (r1|r1<<2) ) | (x>>2 & r2) | (x<<2 & r2<<2);
    r1 = rand() & 0x0F0F0F0F;
    r2 =   r1 ^ 0x0F0F0F0F;
    x = (x & (r1|r1<<4) ) | (x>>4 & r2) | (x<<4 & r2<<4);
    r1 = rand() & 0x00FF00FF;
    r2 =   r1 ^ 0x00FF00FF;
    x = (x & (r1|r1<<8) ) | (x>>8 & r2) | (x<<8 & r2<<8);
    r1 = rand() & 0x0000FFFF;
    r2 =   r1 ^ 0x0000FFFF;
    x = (x & (r1|r1<<16)) | (x>>16& r2) | (x<<16 & r2<<16);
    return x;
}

俺は馬鹿か。
(a & m) | (b & ~m)  　　== 　　( (a ^ b) & m) ^ a
ということを、うっかり忘れてた。
これで十分だな。
uint bit_shuffle(uint x){
    uint y;
    y = (x ^ x>>1 ) & rand() & 0x55555555;
    x ^= y | y<<1;
    y = (x ^ x>>2 ) & rand() & 0x33333333;
    x ^= y | y<<2;
    y = (x ^ x>>4 ) & rand() & 0x0F0F0F0F;
    x ^= y | y<<4;
    y = (x ^ x>>8 ) & rand() & 0x00FF00FF;
    x ^= y | y<<8;
    y = (x ^ x>>16) & rand() & 0x0000FFFF;
    x ^= y | y<<16;
    return x;
}

>>27
すげー

でも仕事でこんなソース回ってきたら、なんの処理なのか理解できないかも・・・

VC++のrand()は線形合同で0〜32767だからうまく混ざらない。

>>27
品質が微妙な気がするがそれは速度重視？
4bits で、途中の rand の全パターンを計算してみる検算プログラム。
こっちが間違ってる？
#include <stdlib.h>
#include <stdio.h>
int main( void )
{
for ( int src = 0; src < 16; src++ ) {
for ( int i = 0; i < 4; i++ ) {
int x = src;
int y = (x ^ (x>>1) ) & ((i&2)*2+(i&1))/*0,1,4,5*/;
x ^= y | (y<<1);
for ( int j = 0; j < 4; j++ ) {
int y = (x ^ (x>>2) ) & j;
x ^= y | (y<<2);
printf( "%x -> %x (%x %x)\n", src, x, (i&2)*2+(i&1), j );
}
}
}
return 0;
}

アルゴリズム的には>>27はrandがちゃんと乱数なら
どのビットへも均等に1/32の確率で移動するよね。

>>30
randって2bit目は常に0なのか。2とか出ない、と。勉強になるなぁ。

>>27のコード、こう書いたほうが一時変数が1個少なくなるのに今気づいた。
x ^= y = (x ^ x >> 1 ) & rand & 0x55555555;
x ^= y << 1;
まぁ乱数の速度がほぼアルゴリズムの速度になるから殆ど意味ないけど

>>30
うん、自分は基本的に最適化厨だから速度重視。
アルゴリズム自身には偏りはないけど、
乱数の質の影響を思いっきり受けるコードだから、悪い乱数だと、品質がおもいっきり悪くなる。

まあ二人とも >30 を実行してシャッフル結果を見てご覧よ。
そんで、>30 のコードにミスがあったら指摘してくれよ。

>>31
>randって2bit目は常に0なのか。2とか出ない、と。勉強になるなぁ。
rand() & 5 だからね。

なるほど。
＞y = (x ^ x>>2 ) & rand() & 0x33333333;
は正しくは
tmp = rand() & 0x11111111; tmp |= tmp<<1;
y = = (x ^ x>>2 ) & tmp;
って感じか。2bitセットでon/offになるように。以下同様。

>>27
分割統治法だっけ？

>>30
3重ループの中のxがループ毎の変更にしているけどループの終了時に元の値に戻していない。
xに直接代入せずにint x2 = x ^ (y | y<<2)とかして表示しないと駄目。

逝ってくる

>>36
確かに。俺が悪かった。
ちゃんと均等になった。

randがちゃんと乱数ならば
もう一回randとったらビットもシャッフルされてないの?

ちゃんとした乱数なんてない

ビット単位のランダムシャッフルって、1の立ってるビットをカウントしたうえ
シャッフル結果を全通り列挙したテーブルを疑似乱数を使ってランダムにピックアップ
ってのはどう？

>>40
シャッフル結果の組み合わせは、整数のビット数をn,たっているビット数をmとしたとき
nCmだからテーブルが馬鹿でかくなりすぎると思う。