memo:順列作れと

ruby C

隣の部屋がつがい化したので、テルトウェイトの詠唱を始めようかと思います。

# -*- coding: utf-8 -*-

#いわゆる順列を作る僕の方法
#計算量が予想できる版
#世の中にはもっとかっこよい作り方をしているものはありますけど。。
#順列とはN**N通りの中から重複した要素を使っているものを抜けばいいのです。

N = 4 #１からNまでを使って。
$rets =[]

def bruise(ret = [])
	if(ret.length >= N)
		$rets << ret
	else
		for i in 1..N
			r = ret.dup	#rubyこの辺キモイと思うの。再帰の前にはdup
			r << i
			bruise(r)
		end
	end
end

bruise()

#そうだ、rubyにはuniqがあるじゃないか!イェイイェイ!
$rets = $rets.select do |x|
		x.uniq.length == x.length
end

p $rets
p "生成したものの要素数:#{$rets.length}"
p "nPn:#{(1..N).inject(1){|result,e| result *= e}}"


__END__
順列を生成して必要なテストを乗り切ったものを出力する、って状況があって、
僕は最初ランダムセレクトに頼り切ってこれでやったのです。
ともかく、ランダムに頼っているので計算量が意味分からん事になっていた。
悔しいですね。

def makeHa
	limitlen = 7 * 6 * 5 * 4 * 3 * 2
	ar = Array.new
	count = 0
	while (ar.length < limitlen) 
		count += 1
		ans = [1,2,3,4,5,6,7]
		a = ans[rand(ans.length)];ans.reject! do |x| x == a end;
		b = ans[rand(ans.length)];ans.reject! do |x| x == b end;
		c = ans[rand(ans.length)];ans.reject! do |x| x == c end;
		d = ans[rand(ans.length)];ans.reject! do |x| x == d end;
		e = ans[rand(ans.length)];ans.reject! do |x| x == e end;
		f = ans[rand(ans.length)];ans.reject! do |x| x == f end;
		g = ans[rand(ans.length)];ans.reject! do |x| x == g end;
		ret = a.to_s + b.to_s + c.to_s + d.to_s + e.to_s + f.to_s + g.to_s
		if nil == ar.index(ret) 
			ar << ret
#ここのように生成したはしから良きかな
#			if test({:a => a,:b => b,:c => c, :d => d,:e => e,:f => f,:g => g})
#				p ret
#				puts "試行回数#{count}"
#				return;
#			end
		end
	end
end

makeHa()


悶々としていたところ、先輩プログラマと飲む機会があったのでネタで振ってみた。
で、あれやこれや行ってるうちに正直に申しますと、二人でググりました。
http://rby-s.seesaa.net/article/2849352.html
にあるプログラム。
checked[p]がダサいですね。でもかなりカッコいい

#include<iostream>
#include<string>

using namespace std;

#define MAX 7
#define Length 7

int ans[MAX];
int checked[MAX];
int cou;


void trys(int i) {
  int p, q;

  if(i==Length) {
    for(q=0; q<Length; q++){
			printf("%d", ans[q] + 1);

		}
    printf("\n");
  }
  else {
    for(p=0; p<MAX; p++) {
      if(checked[p]==0) {
	checked[p] = 1;
	ans[i] = p;
	cou++;
	trys(i+1);
	checked[p] = 0;
      }
    }
  }
}

main() {
	cou = 0;
  memset(checked, 0, MAX*sizeof(int));
  trys(0);
	cout << "count:" << cou << endl;
  return 0;
}

これはかなり素晴らしくて、おしっこチビリそうです。

http://d.hatena.ne.jp/cesium133/20071109/1194591712
にはrubyのカッコ良すぎるやり方が載っていて、
これが正解ですし、再考だと思うのですが、
理解するパーワーが湧いてきませんでした。
というか眠くて寝た。


先輩プログラマはググる前、ループで生成すればいいじゃん!といっていのが頭に残っていました。で、寝ておきたら解決していたので僕なりのやり方を書きました。
あさ、寝ぼけながらやり方を思いついた時の幸福感は異常です。イェイイェイ

以上です。きっと動きます