Haskell中的简单递归算法

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

我们首先定义特殊情况，即选择零元素。它产生一个单一的结果，这是一个空列表(即一个包含空列表的列表)。

对于n> 0, x遍历列表中的每一个元素xs是x之后的每一个元素。

Rest通过对组合的递归调用从xs中选取n - 1个元素。该函数的最终结果是一个列表，其中每个元素都是x: rest(即对于x和rest的每个不同值，x为头部，rest为尾部的列表)。

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

当然，由于Haskell是懒惰的，列表是根据需要逐渐生成的，因此您可以部分计算指数级的大组合。

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

基于java解决方案的短php算法返回k元素从n(二项式系数)的所有组合:

$array = array(1,2,3,4,5);

$array_result = NULL;

$array_general = NULL;

function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
    if($len == 0)
    {
        $general_array[] = $result_array;
        return;
    }

    for ($i = $start_position; $i <= count($array) - $len; $i++)
    {
        $result_array[$result_len - $len] = $array[$i];
        combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
    }
} 

combinations($array, 3, 0, $array_result, 3, $array_general);

echo "<pre>";
print_r($array_general);
echo "</pre>";

相同的解决方案，但在javascript:

var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];

function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
    if(len === 0) {
        var tempArray = [];
        resultArray.forEach(value => tempArray.push(value));
        arrayGeneral.push(tempArray);
        return;
    }
    for (var i = startPosition; i <= newArray.length - len; i++) {
        resultArray[resultLen - len] = newArray[i];
        combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
    }
} 

combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);

console.log(arrayGeneral);

Clojure版本:

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

我想提出我的解决方案。在next中没有递归调用，也没有嵌套循环。 代码的核心是next()方法。

public class Combinations {
    final int pos[];
    final List<Object> set;

    public Combinations(List<?> l, int k) {
        pos = new int[k];
        set=new ArrayList<Object>(l);
        reset();
    }
    public void reset() {
        for (int i=0; i < pos.length; ++i) pos[i]=i;
    }
    public boolean next() {
        int i = pos.length-1;
        for (int maxpos = set.size()-1; pos[i] >= maxpos; --maxpos) {
            if (i==0) return false;
            --i;
        }
        ++pos[i];
        while (++i < pos.length)
            pos[i]=pos[i-1]+1;
        return true;
    }

    public void getSelection(List<?> l) {
        @SuppressWarnings("unchecked")
        List<Object> ll = (List<Object>)l;
        if (ll.size()!=pos.length) {
            ll.clear();
            for (int i=0; i < pos.length; ++i)
                ll.add(set.get(pos[i]));
        }
        else {
            for (int i=0; i < pos.length; ++i)
                ll.set(i, set.get(pos[i]));
        }
    }
}

用法示例:

static void main(String[] args) {
    List<Character> l = new ArrayList<Character>();
    for (int i=0; i < 32; ++i) l.add((char)('a'+i));
    Combinations comb = new Combinations(l,5);
    int n=0;
    do {
        ++n;
        comb.getSelection(l);
        //Log.debug("%d: %s", n, l.toString());
    } while (comb.next());
    Log.debug("num = %d", n);
}

我在c++中为组合创建了一个通用类。 它是这样使用的。

char ar[] = "0ABCDEFGH";
nCr ncr(8, 3);
while(ncr.next()) {
    for(int i=0; i<ncr.size(); i++) cout << ar[ncr[i]];
    cout << ' ';
}

我的库ncr[i]从1返回，而不是从0返回。 这就是为什么数组中有0。 如果你想考虑订单，只需将nCr class改为nPr即可。 用法是相同的。

结果

美国广播公司 ABD 安倍 沛富 ABG ABH 澳洲牧牛犬 王牌 ACF ACG 呵呀 正面 ADF ADG 抗利尿激素 时 AEG AEH 二自由度陀螺仪 AFH 啊 BCD 公元前 供应量 波士顿咨询公司 BCH 12 快速公车提供 BDG BDH 性能试验 求 本· 高炉煤气 BFH 使用BGH CDE 提供 CDG 鼎晖 欧共体语言教学大纲的 CEG 另一 CFG CFH 全息 DEF 度 电气设施 脱硫 干扰 DGH EFG EFH EGH FGH

下面是头文件。

#pragma once
#include <exception>

class NRexception : public std::exception
{
public:
    virtual const char* what() const throw() {
        return "Combination : N, R should be positive integer!!";
    }
};

class Combination
{
public:
    Combination(int n, int r);
    virtual ~Combination() { delete [] ar;}
    int& operator[](unsigned i) {return ar[i];}
    bool next();
    int size() {return r;}
    static int factorial(int n);

protected:
    int* ar;
    int n, r;
};

class nCr : public Combination
{
public: 
    nCr(int n, int r);
    bool next();
    int count() const;
};

class nTr : public Combination
{
public:
    nTr(int n, int r);
    bool next();
    int count() const;
};

class nHr : public nTr
{
public:
    nHr(int n, int r) : nTr(n,r) {}
    bool next();
    int count() const;
};

class nPr : public Combination
{
public:
    nPr(int n, int r);
    virtual ~nPr() {delete [] on;}
    bool next();
    void rewind();
    int count() const;

private:
    bool* on;
    void inc_ar(int i);
};

以及执行。

#include "combi.h"
#include <set>
#include<cmath>

Combination::Combination(int n, int r)
{
    //if(n < 1 || r < 1) throw NRexception();
    ar = new int[r];
    this->n = n;
    this->r = r;
}

int Combination::factorial(int n) 
{
    return n == 1 ? n : n * factorial(n-1);
}

int nPr::count() const
{
    return factorial(n)/factorial(n-r);
}

int nCr::count() const
{
    return factorial(n)/factorial(n-r)/factorial(r);
}

int nTr::count() const
{
    return pow(n, r);
}

int nHr::count() const
{
    return factorial(n+r-1)/factorial(n-1)/factorial(r);
}

nCr::nCr(int n, int r) : Combination(n, r)
{
    if(r == 0) return;
    for(int i=0; i<r-1; i++) ar[i] = i + 1;
    ar[r-1] = r-1;
}

nTr::nTr(int n, int r) : Combination(n, r)
{
    for(int i=0; i<r-1; i++) ar[i] = 1;
    ar[r-1] = 0;
}

bool nCr::next()
{
    if(r == 0) return false;
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n-r+2+i) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++] + 1;
    return true;
}

bool nTr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        ar[i] = 1;
        if(--i == -1) return false;
        ar[i]++;
    }
    return true;
}

bool nHr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++];
    return true;
}

nPr::nPr(int n, int r) : Combination(n, r)
{
    on = new bool[n+2];
    for(int i=0; i<n+2; i++) on[i] = false;
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

void nPr::rewind()
{
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

bool nPr::next()
{   
    inc_ar(r-1);

    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        inc_ar(i);
    }
    while(i < r-1) {
        ar[++i] = 0;
        inc_ar(i);
    }
    return true;
}

void nPr::inc_ar(int i)
{
    on[ar[i]] = false;
    while(on[++ar[i]]);
    if(ar[i] != n+1) on[ar[i]] = true;
}

也许我错过了重点(你需要的是算法，而不是现成的解决方案)，但看起来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)