部分集合を求めるプログラム

php

説明

授業の課題で部分集合を求めるプログラムを書いたので晒してみる。
{a,b,c}の部分集合は{},{a},{b},{c},{ab},{ac},{bc},{abc}の８つ。これを求めるプログラムを書きました。

他にもやり方があるのかもしれませんがここでは２進数のビット列に文字が対応することを利用します。
以下の表をみればやり方を理解してもらえると思います。

10進数 2 進 数 部分集合
c b a
0 0 0 0 φ
1 0 0 1 a
2 0 1 0 b
3 0 1 1 ab
4 1 0 0 c
5 1 0 1 ac
6 1 1 0 bc
7 1 1 1 abc

つまり部分集合の個数は、２の{文字の数}乗通り(上記の例では２の３乗＝８通り)あることになります。
以下のプログラムでは文字が3個以下の場合しか対応していません。4個以上に対応させるためにはifを増やす必要があります。
全然スマートじゃないのでもっとスマートなやり方知りたい…

プログラム

<?php

$data = array();
$str = array();
//部分集合を列挙したい文字列の長さ
$n=3;
//0〜$nまでの整数を２進数に置き換え、配列に格納する
for($i=0;$i<pow(2,$n);$i++){
array_push($data,decbin($i));
}

for($i=0;$i<pow(2,$n);$i++){
	//1桁目が1のとき
	if(substr($data[$i],strlen($data[$i])-1,1)=="1"){
		//nullじゃないなら文字列連結
		if(isset($str[$i])){
			$str[$i].="a";
		//$str[$i]がnullなら
		}else{
			$str[$i]="a";
		}
	}
	//桁数が2ケタ以上のとき
	if(strlen($data[$i])>1){
		//2桁目が1のとき
		if(substr($data[$i],strlen($data[$i])-2,1)=="1"){
			//nullじゃないなら文字列連結
			if(isset($str[$i])){
				$str[$i]=$str[$i]."b";
			//$str[$i]がnullなら
			}else{
				$str[$i]="b";
			}
		}
	}
	//桁数が3ケタ以上のとき
	if(strlen($data[$i])>2){
		//3桁目が1のとき
		if(substr($data[$i],strlen($data[$i])-3,1)=="1"){
			//nullじゃないなら文字列連結
			if(isset($str[$i])){
				$str[$i]=$str[$i]."c";
			//$str[$i]がnullならそのまま格納
			}else{
				$str[$i]="c";
			}
		}
	}
}
if(!isset($str[0])){
	$str[0]="φ";
}

print_r($str);
?>

追記

id=Kshi_Kshiが僕が書いたのよりも、もっとスマートなスクリプトをpythonで書いてくれたので僕もphpで書き直してみました。Kshi_Kshi君ありがとう。

彼の書いたスクリプトはこちらからご覧になれます。
部分集合を求めるスクリプト

僕が前に書いたスクリプトはfor文１つで部分集合を求めていたわけですが、それをやめてfor文の入れ子構造にして自動化しちゃえばいいよねって話。今考えるとなんであんな面倒くさいやり方したんだ俺ｗ

プログラム

<?php
$dec = array();
$result = array();
$input=array("a","b","c");
//部分集合を列挙したい文字列の長さ
$n=count($input);

//0〜$nまでの整数を２進数に置き換え、配列に格納する
for($i=0;$i<pow(2,$n);$i++){
array_push($dec,decbin($i));
}

//上記で生成した2進数を１つずつチェック
for($i=0;$i<pow(2,$n);$i++){
	//上記でチェックした2進数の１桁１桁をチェック
	for($j=0;$j<strlen($dec[$i]);$j++){
		//もし１ならその桁数目の文字を結合する
		if(substr($dec[$i],strlen($dec[$i])-1-$j,1)=="1"){
			$result[$i] = $result[$i].$input[$j];
		}
	}
	//空集合チェック
	if(!isset($result[$i])){
	$result[$i]="φ";
	}
}

print_r($result);
?>