全ての組み合わせ in PHP DouKaku?

全ての組み合わせ

2個以上のリストlist1, list2, list3...が与えられたときに、その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]

順番はこの通りでなくても構いません。返すものはリストと書きましたが、なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記：サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

post comment

Posted feedbacks - PHP

リストを配列と読替えて、文字列も配列へ変換してます。

<?php
function CrossProduct() {
	$n = func_num_args();
	foreach ( func_get_args() as $arg ) {
		if ( !is_array($arg) ) {
			$splt = array();
			for ( $i = 0; $i < strlen($arg); $i++ ) {
				$splt[] = substr($arg,$i,1);
			}
			$arg = $splt;
		}
		$args[] = $arg;
	}
	$max = count($args[0]);
	if ( $n > 1 ) {
		for ( $i = 1; $i < $n; $i++ ) {
			$max *= count($args[$i]);
		}
	}
	$pmax = $max;
	for ( $i = 0; $i < $n; $i++ ) {
		$pmax = $pmax / count($args[$i]);
		$cnt  = 0;
		$line = 0;
		$k    = 0;
		do {
			$cnt++;
			if ( $cnt > $pmax ) {
				$cnt = 1;
				$k++;
				if ( $k >= count($args[$i]) ) {
					$k = 0;
				}
			}
			$rtn[$line][] = $args[$i][$k];
			$line++;
		} while ( $line < $max );
	}
	return $rtn;
}

$a = array(0,1);
$b = "ab";
$c = array("Foo","Bar");
$d = "XYZ";
print_r(CrossProduct($a,$b,$c,$d));
?>

DouKaku?

全ての組み合わせ

Posted feedbacks - PHP

Index

Feed

Other

Link

Pathtraq