iT邦幫忙

0

排列組合的問題 (php)

以下兩個註解 小弟百思不解
因各位高手能解惑~~!
/images/emoticon/emoticon06.gif

$arr    = array(
    'a',
    'b',
    'c',
    'd'
);
$result = array();
$t      = getCombinationToString($arr, 4);
print_r($t);

function getCombinationToString($arr, $m)
{
    //沒這行 無法正常運行 但$m為數字四 應不會執行??
    if ($m == 1) {
        return $arr;
    }

    $result = array();
    
    $tmpArr = $arr;
    // 有這行不能展示所有組合,所以先註解掉
    // unset($tmpArr[0]);
    for ($i = 0; $i < count($arr); $i++) {
        $s   = $arr[$i];
        $ret = getCombinationToString(array_values($tmpArr), ($m - 1), $result);
        
        foreach ($ret as $row) {
            $result[] = $s . $row;
        }
    }
    
    return $result;
}
看更多先前的討論...收起先前的討論...
小魚 iT邦高手 1 級 ‧ 2019-07-23 07:41:14 檢舉
這是遞迴的概念吧
froce iT邦大師 6 級 ‧ 2019-07-23 07:54:10 檢舉
遞迴...
$m == 1是結束條件,然後不斷調用getCombinationToString這函數
fillano iT邦超人 1 級 ‧ 2019-07-23 10:55:20 檢舉
$m不需要吧,只要知道傳入的陣列長度就可以。另外在getCombinationToString裡面呼叫getCombinationToString的時候,多傳了一個參數?
QQ556 iT邦新手 5 級 ‧ 2019-07-23 22:46:19 檢舉
那請問為什麼$m那行程式碼不能刪除呢
不好意思...... 不太懂
1
淺水員
iT邦新手 3 級 ‧ 2019-07-23 15:27:17
最佳解答

下面是盡量保持原先的作法去修正的

<?php
$arr    = array(
    'a',
    'b',
    'c',
    'd'
);
$t      = getCombinationToString($arr);
print_r($t);

function getCombinationToString($arr)
{
    //$m 就是陣列長度,那麼可以直接用 count 取得就好
    //除了用在遞迴終止的判斷,也可以用在下面的 for 迴圈
    $m=count($arr);
    
    if ($m <= 1) {
        return $arr;
    }

    $result = array();
    
    //下面這個 for 迴圈直接把 $i 跟 $m 比較就可
    for ($i = 0; $i < $m; $i++) {
        $s   = $arr[$i];
        //下面這兩行應該要放在迴圈內才有意義
        $tmpArr = $arr; //複製 $arr 的值給 $tmpArr
        unset($tmpArr[$i]); //拿掉選擇的值
        $ret = getCombinationToString(array_values($tmpArr));
        
        foreach ($ret as $row) {
            $result[] = $s . $row;
        }
    }
    
    return $result;
}

下面這個是另外一個方法,可以減少頻繁產生新的陣列

<?php
$arr    = array(
    'a',
    'b',
    'c',
    'd'
);
$result=array();
getCombinationToString($arr,$result);
echo implode('<br>',$result);

function getCombinationToString(&$arr, &$result, $offset=0)
{
    $m=count($arr);
    
    if ($m == $offset) {
        $result[]=implode($arr);
        return;
    }
    
    for ($i = $offset; $i < $m; ++$i) {
        //透過「交換」取代原先的「拿掉」
        $tmp=$arr[$i];
        $arr[$i]=$arr[$offset];
        $arr[$offset]=$tmp;
        getCombinationToString($arr, $result, $offset+1);
        //還原
        $tmp=$arr[$i];
        $arr[$i]=$arr[$offset];
        $arr[$offset]=$tmp;
    }
}
QQ556 iT邦新手 5 級 ‧ 2019-07-24 00:39:17 檢舉

大大的解答 小弟的水準比較能了解
但也感謝各路大神的解答!!

0
浩瀚星空
iT邦大師 1 級 ‧ 2019-07-23 09:13:26

你這是一個組合。
所以至少需要2個以上的值才可以做組合。
當只剩下一個的話就不需要再跑組合了。也會出錯。

第二個我判斷它是為了要做清掉單一數值非組合的值才對。
不過這邊確實寫的不好。所以有點問題存在。

2
fillano
iT邦超人 1 級 ‧ 2019-07-23 11:09:35

來湊個數...用Javascript寫的話:

const a = ['a', 'b', 'c', 'd'];
console.log(combine(a));
function combine(a) {
	if(Array.isArray(a) && a.length > 0) {
		let result = [];
		if(a.length === 1) {
			result.push(a);
		} else {
			for(let i=0; i<a.length; i++) {
				let tmp = dup(a);
				let s = tmp.splice(i, 1)[0];
				combine(tmp).forEach(j => {
					//j.unshift(s);
					//result.push(j);
					result.push([s,...j]);
				});
			}
		}
		return result;
	} else {
		throw "The parameter 'a' must be a non-empty array."
	}
	function dup(a) {
		let tmp = [];
		for(let i=0; i<a.length; i++) {
			tmp[i] = a[i];
		}
		return tmp;
	}
}

輸出:

[ [ 'a', 'b', 'c', 'd' ],
  [ 'a', 'b', 'd', 'c' ],
  [ 'a', 'c', 'b', 'd' ],
  [ 'a', 'c', 'd', 'b' ],
  [ 'a', 'd', 'b', 'c' ],
  [ 'a', 'd', 'c', 'b' ],
  [ 'b', 'a', 'c', 'd' ],
  [ 'b', 'a', 'd', 'c' ],
  [ 'b', 'c', 'a', 'd' ],
  [ 'b', 'c', 'd', 'a' ],
  [ 'b', 'd', 'a', 'c' ],
  [ 'b', 'd', 'c', 'a' ],
  [ 'c', 'a', 'b', 'd' ],
  [ 'c', 'a', 'd', 'b' ],
  [ 'c', 'b', 'a', 'd' ],
  [ 'c', 'b', 'd', 'a' ],
  [ 'c', 'd', 'a', 'b' ],
  [ 'c', 'd', 'b', 'a' ],
  [ 'd', 'a', 'b', 'c' ],
  [ 'd', 'a', 'c', 'b' ],
  [ 'd', 'b', 'a', 'c' ],
  [ 'd', 'b', 'c', 'a' ],
  [ 'd', 'c', 'a', 'b' ],
  [ 'd', 'c', 'b', 'a' ] ]
看更多先前的回應...收起先前的回應...
dragonH iT邦高手 1 級 ‧ 2019-07-23 11:18:11 檢舉

看他的敘述

他要的好像是

可以重複的排列組合

可是又有這種

unset($tmpArr[0]);

切頭

奇怪的東西

這應該是取不能重複才會用到

感覺是東拼西湊

最後拼出了一個不知道是什麼東西/images/emoticon/emoticon06.gif

fillano iT邦超人 1 級 ‧ 2019-07-23 11:46:46 檢舉

PHP版:

<?php
$a = array('a', 'b', 'c', 'd');
print_r(combine($a));

function combine($a) {
	$result = array();
	if(count($a) == 1) {
		array_push($result, $a);
	} else {
		for($i=0; $i<count($a); $i++) {
			$tmp = dup($a);
			$s = array_splice($tmp, $i, 1)[0];
			foreach(combine($tmp) as $j) {
				array_unshift($j, $s);
				array_push($result, $j);
			}
		}
	}
	return $result;
}

function dup($a) {
	$ret = array();
	for($i=0; $i<count($a); $i++) {
		$ret[$i] = $a[$i];
	}
	return $ret;
}

結果:

Array
(
    [0] => Array
        (
            [0] => a
            [1] => b
            [2] => c
            [3] => d
        )

    [1] => Array
        (
            [0] => a
            [1] => b
            [2] => d
            [3] => c
        )

    [2] => Array
        (
            [0] => a
            [1] => c
            [2] => b
            [3] => d
        )

    [3] => Array
        (
            [0] => a
            [1] => c
            [2] => d
            [3] => b
        )

    [4] => Array
        (
            [0] => a
            [1] => d
            [2] => b
            [3] => c
        )

    [5] => Array
        (
            [0] => a
            [1] => d
            [2] => c
            [3] => b
        )

    [6] => Array
        (
            [0] => b
            [1] => a
            [2] => c
            [3] => d
        )

    [7] => Array
        (
            [0] => b
            [1] => a
            [2] => d
            [3] => c
        )

    [8] => Array
        (
            [0] => b
            [1] => c
            [2] => a
            [3] => d
        )

    [9] => Array
        (
            [0] => b
            [1] => c
            [2] => d
            [3] => a
        )

    [10] => Array
        (
            [0] => b
            [1] => d
            [2] => a
            [3] => c
        )

    [11] => Array
        (
            [0] => b
            [1] => d
            [2] => c
            [3] => a
        )

    [12] => Array
        (
            [0] => c
            [1] => a
            [2] => b
            [3] => d
        )

    [13] => Array
        (
            [0] => c
            [1] => a
            [2] => d
            [3] => b
        )

    [14] => Array
        (
            [0] => c
            [1] => b
            [2] => a
            [3] => d
        )

    [15] => Array
        (
            [0] => c
            [1] => b
            [2] => d
            [3] => a
        )

    [16] => Array
        (
            [0] => c
            [1] => d
            [2] => a
            [3] => b
        )

    [17] => Array
        (
            [0] => c
            [1] => d
            [2] => b
            [3] => a
        )

    [18] => Array
        (
            [0] => d
            [1] => a
            [2] => b
            [3] => c
        )

    [19] => Array
        (
            [0] => d
            [1] => a
            [2] => c
            [3] => b
        )

    [20] => Array
        (
            [0] => d
            [1] => b
            [2] => a
            [3] => c
        )

    [21] => Array
        (
            [0] => d
            [1] => b
            [2] => c
            [3] => a
        )

    [22] => Array
        (
            [0] => d
            [1] => c
            [2] => a
            [3] => b
        )

    [23] => Array
        (
            [0] => d
            [1] => c
            [2] => b
            [3] => a
        )

)
fillano iT邦超人 1 級 ‧ 2019-07-23 11:50:38 檢舉

他用unset,我猜是跟我程式裡面用array_splice這樣的意思。但是不可能只切頭就做出排列組合XD

dragonH iT邦高手 1 級 ‧ 2019-07-23 11:55:37 檢舉

fillano

對呀XD

所以感覺很奇怪/images/emoticon/emoticon01.gif

就是感覺只做一半

fillano iT邦超人 1 級 ‧ 2019-07-23 11:57:54 檢舉

也不對,在那個位置做unset好像沒意義XD

另外,在assign的時候php似乎會製作一個複本,所以不用呼叫dup。

淺水員 iT邦新手 3 級 ‧ 2019-07-23 15:47:52 檢舉

把 unset 丟到迴圈裡面就合理了...
unset($tmpArr[$i]);

我要發表回答

立即登入回答