我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由3个字母组成。
当前回答
我正在为PHP寻找类似的解决方案，遇到了以下情况
class Combinations implements Iterator
{
protected $c = null;
protected $s = null;
protected $n = 0;
protected $k = 0;
protected $pos = 0;
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
}
foreach(new Combinations("1234567", 5) as $substring)
echo $substring, ' ';
源
我不确定这个类有多高效，但我只是把它用作种子程序。
其他回答
下面是Clojure版本，它使用了我在OCaml实现答案中描述的相同算法:
(defn select
([items]
(select items 0 (inc (count items))))
([items n1 n2]
(reduce concat
(map #(select % items)
(range n1 (inc n2)))))
([n items]
(let [
lmul (fn [a list-of-lists-of-bs]
(map #(cons a %) list-of-lists-of-bs))
]
(if (= n (count items))
(list items)
(if (empty? items)
items
(concat
(select n (rest items))
(lmul (first items) (select (dec n) (rest items)))))))))
它提供了三种调用方法:
(a)按问题要求，选出n项:
user=> (count (select 3 "abcdefgh"))
56
(b) n1至n2个选定项目:
user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))
(c)在0至所选项目的集合大小之间:
user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))
JavaScript，基于生成器，递归方法:
function *nCk(n,k){ for(var i=n-1;i>=k-1;--i) if(k===1) yield [i]; else for(var temp of nCk(i,k-1)){ temp.unshift(i); yield temp; } } function test(){ try{ var n=parseInt(ninp.value); var k=parseInt(kinp.value); log.innerText=""; var stop=Date.now()+1000; if(k>=1) for(var res of nCk(n,k)) if(Date.now()<stop) log.innerText+=JSON.stringify(res)+" "; else{ log.innerText+="1 second passed, stopping here."; break; } }catch(ex){} } n:<input id="ninp" oninput="test()"> >= k:<input id="kinp" oninput="test()"> >= 1 <div id="log"></div>
通过这种方式(减少i和unshift())，它以递减的顺序生成组合和组合内的元素，有点赏心悦目。 测试在1秒后停止，因此输入奇怪的数字是相对安全的。
下面是我的JavaScript解决方案，通过使用reduce/map，它消除了几乎所有变量，功能更强大
function combinations(arr, size) { var len = arr.length; if (size > len) return []; if (!size) return [[]]; if (size == len) return [arr]; return arr.reduce(function (acc, val, i) { var res = combinations(arr.slice(i + 1), size - 1) .map(function (comb) { return [val].concat(comb); }); return acc.concat(res); }, []); } var combs = combinations([1,2,3,4,5,6,7,8],3); combs.map(function (comb) { document.body.innerHTML += comb.toString() + '<br />'; }); document.body.innerHTML += '<br /> Total combinations = ' + combs.length;
我正在为PHP寻找类似的解决方案，遇到了以下情况
class Combinations implements Iterator
{
protected $c = null;
protected $s = null;
protected $n = 0;
protected $k = 0;
protected $pos = 0;
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
}
foreach(new Combinations("1234567", 5) as $substring)
echo $substring, ' ';
源
我不确定这个类有多高效，但我只是把它用作种子程序。
也许我错过了重点(你需要的是算法，而不是现成的解决方案)，但看起来scala已经开箱即用了(现在):
def combis(str:String, k:Int):Array[String] = {
str.combinations(k).toArray
}
使用这样的方法:
println(combis("abcd",2).toList)
会产生:
List(ab, ac, ad, bc, bd, cd)
