最高のハイスコアを見つけるためのアルゴリズム。オンラインでアップロードするのを待ちますか??

この投稿は sibang によって最終編集されました: 2013-08-08 23:44:40

PHP アルゴリズム関数の文字列の組み合わせ

おおよそ次のように、文字列を再結合する関数の作成を手伝ってください:

/**参数:	$arr:原始Array	$len:组合后的长度/**/Function getArray($arr,$len){	//请帮忙写}$arr=Array('A','B','C');print_r(getArray($arr,2));$arr=Array('A','B','C','D','E','F');print_r(getArray($arr,4));

要件は次のとおりです。 :
タイプ 1: A、B、C
期待される組み合わせは次のとおりです: AB、AC、BC

タイプ 2: A、B、C、D (結果の長さはパラメーターによって制御できます。 2 または 3)
予想される組み合わせは次のとおりです: AB、AC、AD、BC、BD、CD または ABC、BCD、ACD、ABD


タイプ 3: A、B、C、D、E (結果は制御可能)パラメーターによる長さ (長さ 2、長さ 3 または 4 など)
期待される組み合わせは次のとおりです: AB、AC、AD、AE、BC、BD、BE、CD、CE、DE または ABC、BCD、CDE、ABD、ABE、ACD 、ACE、BDE、BCE、ADE または ABCD、BCDE、ABCE、ACDE、ABDE

4 番目のタイプ: A、B、C、D、E、F (結果の長さは、長さは 2; 3; 4 または 5)

予想される組み合わせは次のとおりです: 上記の組み合わせに基づいて推測できるため、ここでは引用しません

議論への返信 (解決策)

にはどのような組み合わせがありますか。順列?

とても面白そうです...不可能かもしれませんが、試してみましょう

アルゴリズムの専門家の助けを楽しみにしていますか?

申し訳ありませんが、本当にわかりません。 .. 考えてみたら、深さ優先探索を使ったほうが良いのかもしれないけど、どうやって書けばいいのかまだ考えていない…

少し進んだけど、できない。アルゴリズムについて話しますが、効率は非常に低いです! アイデアを広げるのに役立つことを願っています...

アイデア: 最初に順列を計算し、次に順列内の繰り返し箇所を削除して、組み合わせを実現します。

P.S: 私は途中で僧侶になり、1年以上PHPで働いていますが、データ構造とアルゴリズムがまったくわかりません...目の前のプロジェクトが完了したら必ず埋め合わせます。 ..

/*$arr = array("A","B","C");Function getArray($arr,$len=2){	$arr2 = array();    foreach ($arr as $y){		foreach($arr as $k){			if($y != $k){					$arr2[] = $y.$k;			}		}	}		$arr3 = array();		foreach($arr2 as $c){		$f = str_split($c);		if($arr3){			$i = 0;			foreach($arr3 as $d){				$e = str_split($d);				if(in_array($f[0],$e) && in_array($f[1],$e)){					$i++;				}			}			if(!$i){				$arr3[] = $c;			}		}else{			$arr3[] = $c;		}	}	return $arr3;}*/$arr = array("A","B","C","D");Function getArray($arr,$len=3){	$arr2 = array();    foreach ($arr as $y){   //$len是几,就循环几次,这里是一个变数		foreach($arr as $k){			foreach($arr as $v){				if($y != $k && $y != $v && $v != $k){   //$len个元素均不相同						$arr2[] = $y.$k.$v;				}			}		}	}		$arr3 = array();		foreach($arr2 as $c){		$f = str_split($c);		if($arr3){			$i = 0;			foreach($arr3 as $d){				$e = str_split($d);				if(in_array($f[0],$e) && in_array($f[1],$e) && in_array($f[2],$e)){    //$len个元素都在数组中的话,$i++ 如果$i大于0,这个记录就抛弃					$i++;				}			}			if(!$i){				$arr3[] = $c;			}		}else{			$arr3[] = $c;		}	}	return $arr3;}print_r(getArray($arr));

$ len の変更に基づく箇所は 3 か所あり、ABCD の 4 文字または ABCDE の 5 文字が正しい結果を得ることができます

つまり、$ でどのように判断して再帰するかが重要ですlen...

============== ================
この方法は非常に模倣的だといつも感じます、批判してください訂正してください

A B C D E F G 7 文字の配列、3 つの配置を取ります

上記を使用します このメソッドの結論は
Array ([0] => ABC [1] => ABD [2] => ABE [ 3] => ABF [4] => ACD [7] => ACG [10] ] => ADF [11] => AEF [14] => BCD [17] => BCF [18] => BDE [21] => BEF [24] = > BFG [25] => CDF [28] => CEG [31] => ; DEF [32] => DEG [33] => EFG )
35 が正しいはずです...

それを行う方法はたくさんあります。最初に「効率的な 10 動作の方法」を説明します。関数に名前を付けるときは、組み合わせを表す英語の単語を使用します。

function combination( $arr, $num=0) {  $len = count($arr);  if($num == 0) $num = $len;  $res = array();  for($i=1,$n=pow(2, $len);$i<$n;++$i) {    $tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);    $t = array();    for($j=0;$j<$len;++$j) {      if($tmp{$j} == '1') {        $t[] = $arr[$j];      }    }    if(count($t) == $num) $res[] = join('', $t);  }  return $res;}

は次のように呼び出します。 AC
[2] => AB
)

请帮忙写一个函数,用来重新组合字符串,大概如下:

/**参数:	$arr:原始Array	$len:组合后的长度/**/Function getArray($arr,$len){	//请帮忙写}$arr=Array('A','B','C');print_r(getArray($arr,2));$arr=Array('A','B','C','D','E','F');print_r(getArray($arr,4));

要求如下:
第1种: A,B,C
期望能够得到的组合是: AB,AC,BC

第2种: A,B,C,D(可通过参数控制结果长度,如长度为2或3)
期望能够得到的组合是: AB,AC,AD,BC,BD,CD或ABC,BCD,ACD,ABD

第3种: A,B,C,D,E(可通过参数控制结果长度,如长度为2;3或4)
期望能够得到的组合是: AB,AC,AD,AE,BC,BD,BE,CD,CE,DE或ABC,BCD,CDE,ABD,ABE,ACD,ACE,BDE,BCE,ADE或ABCD,BCDE,ABCE,ACDE,ABDE

第四种:A,B,C,D,E,F(可通过参数控制结果长度,如长度为2;3;4或5)
期望能够得到的组合是: 可根据上边的组合推演出来,在此不再例举

是否有重复字母？
还有AB，BA算不算不同的？
总得要具体说明一下吧

递归的写法

function combination($ar, $k, $m=0, $a=array()) {        static $ret = array();        if($m == 0) {                $m = count($ar);                $ret = array();        }        for($i=$m; $i>=$k; $i--) {                $a[$k-1] = $ar[$i-1];                if($k > 1) {                        combination(&$ar, $k-1, $i-1, $a);                }else {                        array_unshift ($ret, array_reverse($a));                }        }        return $ret;}

利用堆栈的写法

function combination($ar, $num) {        $control = range(0, $num-1);        $k = false;        $total = count($ar);        while($control[0] < $total-($num-1)) {                $t = array();                for($i=0; $i<$num; $i++) $t[] = $ar[$control[$i]];                $r[] = $t;                for($i=$num-1; $i>=0; $i--) {                        $control[$i]++;                        for($j=$i; $j<$num-1; $j++) $control[$j+1] = $control[$j]+1;                        if($control[$i] < $total-($num-$i-1)) break;                }        }        return $r;}

版大犀利

求问6#为甚么使用pow(2,$len)来做循环次数, 而为什么可以通过转化为2进制数来解决问题? 这一块应该是数学问题了吧.... 但是没想明白, 求点拨...

版大犀利

求问6#为甚么使用pow(2,$len)来做循环次数, 而为什么可以通过转化为2进制数来解决问题? 这一块应该是数学问题了吧.... 但是没想明白, 求点拨...

2进制那个简单的，你首先要明白的是$tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);这个得到的，他这个是根据取的长度在前面增加几个0，然后可以循环才能有
if($tmp{$j} == '1') {
$t[] = $arr[$j];
}
这个数组，这个数组的长度才能与$len相同，相同的话就组成字符串

版大犀利

求问6#为甚么使用pow(2,$len)来做循环次数, 而为什么可以通过转化为2进制数来解决问题? 这一块应该是数学问题了吧.... 但是没想明白, 求点拨...

2进制那个简单的，你首先要明白的是$tmp = str_pad(base_convert($i, 10, 2), $len, '0', STR_PAD_LEFT);这个得到的，他这个是根据取的长度在前面增加几个0，然后可以循环才能有
if($tmp{$j} == '1') {
$t[] = $arr[$j];
}
这个数组，这个数组的长度才能与$len相同，相同的话就组成字符串

大概略微有点头绪了

是不是二进制数010101之类的 恰好可以代表每个位置选中/未选中

pow(2,$len)可以大于等于所有的排列情况的数量,而小于它的数,每个数的2进制形式也都是不同的,所以恰好可以用这种方式来进行筛选?

还没想透,不知道如何证明或者反证这种巧妙的方法 .... 再纠结下

可参阅 http://blog.sina.com.cn/s/blog_605f5b4f0100vcwz.html

版大犀利

求问6#为甚么使用pow(2,$len)来做循环次数, 而为什么可以通过转化为2进制数来解决问题? 这一块应该是数学问题了吧.... 但是没想明白, 求点拨...

做了10?次循???,??下???效率最高,??了,感?xuzuning老大的?忙

function combination($ar, $num) {        $control = range(0, $num-1);        $k = false;        $total = count($ar);        while($control[0] < $total-($num-1)) {                $t = array();                for($i=0; $i<$num; $i++) $t[] = $ar[$control[$i]];                $r[] = $t;                for($i=$num-1; $i>=0; $i--) {                        $control[$i]++;                        for($j=$i; $j<$num-1; $j++) $control[$j+1] = $control[$j]+1;                        if($control[$i] < $total-($num-$i-1)) break;                }        }        return $r;}