有一組數(shù)字[0,1,2,3,4,5,6,7,8,9],現(xiàn)給出一個數(shù)字,比如3,
要求從該組數(shù)字中選出相加等于3的組合(相加的數(shù)字3個),如0+0+3=3,0+1+2,3個相加的數(shù)字不能相同(如1+1+1就不行),無順序要求。
大概函數(shù)是這樣 fun(數(shù)組,和值,3) ,得到的是組合的個數(shù).
參數(shù)3是相加的數(shù)字個數(shù),這里規(guī)定是3,如0+0+3,這是3個數(shù)字
請參考以下 python 代碼實現(xiàn)
# -*- coding: utf-8 -*-
"""
author: 李毅
"""
from unittest import TestCase
def permutation(array, nsum):
''' 假設數(shù)組元素不重復。 '''
# 排序(升序)
sarray = sorted(array)
# 找出最大下標
max_idx = len(sarray)
for i, e in enumerate(sarray):
if e > nsum:
max_idx = i
break
# 窮舉
result = []
for i in range(max_idx):
for j in range(i, max_idx):
for k in range(j, max_idx):
if i == j and j == k:
continue
if sarray[i] + sarray[j] + sarray[k] == nsum:
result.append((sarray[i], sarray[j], sarray[k]))
return result
class Test(TestCase):
""" 單元測試 """
def test_permutation(self):
self.assertEqual(
permutation(range(10), 3),
[(0, 0, 3), (0, 1, 2)])
self.assertEqual(
permutation(range(10), 2),
[(0, 0, 2), (0, 1, 1)])
# 邊界值
self.assertEqual(
permutation(range(3), 3),
[(0, 1, 2)])
self.assertEqual(
permutation(range(1, 4), 4),
[(1, 1, 2)])
遞歸查找符合規(guī)則的元素集合:
部分邏輯是建立在認為集合中所有元素都是正數(shù)的基礎上
(() => {
var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(calc(arr, 3, 3)) // 0,1,2
console.log(calc(arr, 3, 1)) // 3
function calc (arr, total, count, feed = []) {
if (count === 1) { // check
return arr.includes(total) ? feed.concat(total) : null
} else if (count > 1) { // remove big number
arr = arr.filter(item => item < total)
} else if (count === 0) { // maybe too large
return total === 0 ? feed : null
} else if (total < 0 || count < 0) { // too large
return null
}
for (let [index, item] of Object.entries(arr)) {
let result = calc([
...arr.slice(0, index),
...arr.slice(index + 1)
], total - item, count - 1, feed.concat(item))
if (result) return result
}
return null
}
})()
<?php
/**
* @title
* @author start2004
* @since 2018/5/10
*/
/**
* 有一組數(shù)字[0,1,2,3,4,5,6,7,8,9],現(xiàn)給出一個數(shù)字,比如3,
* 要求從該組數(shù)字中選出相加等于3的組合(相加的數(shù)字3個),如0+0+3=3,0+1+2,3個相加的數(shù)字不能相同(如1+1+1就不行),無順序要求。
* 大概函數(shù)是這樣 fun(數(shù)組,和值,3) ,得到的是組合的個數(shù).
* 參數(shù)3是相加的數(shù)字個數(shù),這里規(guī)定是3,如0+0+3,這是3個數(shù)字
* https://segmentfault.com/q/1010000014767442?utm_source=tag-newest
*/
ini_set('memory_limit', '8M');
$arr = [0,1,2,3,4,5,6,7,8,9];
$sum = 2;
$num = 3;
$resultArray = calc($arr, $sum, $num);
//var_dump($resultArray);
/**
* @title 入口函數(shù)
* @param array $arr
* @param int $sum
* @param int $num
* @return array
*/
function calc($arr = [], $sum = 0, $num = 0){
$resultArray = main($arr, $sum, $num);
$listArray = [];
if($resultArray){
foreach ($resultArray as $rArray){
/**
* num>1
* 不能所有值一樣
* 去重后,數(shù)組長度大于1
*/
if ($num=1 OR (array_unique($rArray)) > 1){
/**
* 數(shù)組排序,去重返回
*/
sort($rArray);
if (in_array($rArray, $listArray) === false){
$listArray[] = $rArray;
echo implode(" + ", $rArray), " = {$sum}", PHP_EOL;
}
}
}
}
/**
* 沒有符合條件
*/
if (empty($listArray)){
echo "sum = {$sum}, num = {$num}, no result.", PHP_EOL;
}
return $listArray;
}
/**
* @title 執(zhí)行函數(shù)
* @param array $arr
* @param int $sum
* @param int $num
* @param array $feed
* @return array|bool
*/
function main($arr = [], $sum = 0, $num = 0, $feed = []){
if($num < 1){
return false;
} elseif($num == 1){
/**
* num=1,最后一個值是leftSum,且必須在arr中
*/
if(in_array($sum, $arr) !== false){
$feed[] = $sum;
echoLine($sum, $sum, 0, $feed);
return [$feed];
} else {
return false;
}
} else {
$listArray = [];
foreach ($arr as $val){
/**
* 只要小于sum,就執(zhí)行遞歸
*/
if($val <= $sum){
$leftSum = $sum-$val;
$leftNum = $num-1;
$leftFeed = array_merge($feed, [$val]);
echoLine($val, $leftSum, $leftNum, $leftFeed);
$resultArray = main($arr, $leftSum, $leftNum, $leftFeed);
if($resultArray){
foreach ($resultArray as $rArray){
$listArray[] = $rArray;
}
}
}
}
return $listArray;
}
}
/**
* @title 遞歸視圖輸出
* @param $key
* @param $sum
* @param $num
* @param $feed
*/
function echoLine($key, $sum, $num, $feed){
return ;
$prefix = str_repeat("│ ", count($feed)-1);
echo $prefix;
echo "├─key={$key}";
if($num>0){
echo ", sum={$sum}, num={$num}";
}
echo PHP_EOL;
}
/**
├─key=0, sum=2, num=2
│ ├─key=0, sum=2, num=1
│ │ ├─key=2
│ ├─key=1, sum=1, num=1
│ │ ├─key=1
│ ├─key=2, sum=0, num=1
│ │ ├─key=0
├─key=1, sum=1, num=2
│ ├─key=0, sum=1, num=1
│ │ ├─key=1
│ ├─key=1, sum=0, num=1
│ │ ├─key=0
├─key=2, sum=0, num=2
│ ├─key=0, sum=0, num=1
│ │ ├─key=0
*/
北大青鳥APTECH成立于1999年。依托北京大學優(yōu)質雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
北大青鳥中博軟件學院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網學院和江蘇省首批服務外包人才培訓基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團創(chuàng)建于1999年,經過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術與教育服務機構,發(fā)展為教育服務業(yè)的綜合性企業(yè)集團,成為集合面授教學培訓、網
達內教育集團成立于2002年,是一家由留學海歸創(chuàng)辦的高端職業(yè)教育培訓機構,是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
曾工作于聯(lián)想擔任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔任項目經理從事移動互聯(lián)網管理及研發(fā)工作,曾創(chuàng)辦藍懿科技有限責任公司從事總經理職務負責iOS教學及管理工作。
浪潮集團項目經理。精通Java與.NET 技術, 熟練的跨平臺面向對象開發(fā)經驗,技術功底深厚。 授課風格 授課風格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網頁制作和網頁游戲開發(fā)。
具有10 年的Java 企業(yè)應用開發(fā)經驗。曾經歷任德國Software AG 技術顧問,美國Dachieve 系統(tǒng)架構師,美國AngelEngineers Inc. 系統(tǒng)架構師。