[数学问题]如何得到组合数列表

Programming
1

从nums[1 2 3 4 5]里去n个组合，我不想知道有多少种组合，我只想得到组合过后的序列,(1 2) (1 3) (1 4) ...
如何去定义这个函数C(nums,n)呢

2

有些语言已经有实现了，没有自己随手写一个 dfs 也不是很费事吧。

ps 这个和数学有什么关系

3 
(defun combination (n lst)
  (labels ((combine-1 (n lst)
	     (if (eql 1 n)
		 (list (list (car lst)))
		 (mapcar #'(lambda (x) (cons (car lst) x))
			 (combination (1- n) (cdr lst)))))
	   (combine (n lst acc)
	     (if (eql n (length lst)) (nreverse (push lst acc))
		 (combine n (cdr lst)
			  (append (nreverse (combine-1 n lst)) acc)))))
    (combine n lst nil)))

以前做过的题，记得逻辑是模拟枚举法，现在自己都看不懂了

(combination 3 '(a b c d e f))
((a b c)
 (a b d)
 (a b e)
 (a b f)
 (a c d)
 (a c e)
 (a c f)
 (a d e)
 (a d f)
 (a e f)
 (b c d)
 (b c e)
 (b c f)
 (b d e)
 (b d f)
 (b e f)
 (c d e)
 (c d f)
 (c e f)
 (d e f))
4

这是哪种lisp方言

5

common lisp，但无所谓，elisp也能直接用

6 
     ∇ ssub←{                            
[1]        ∨/⍺=0 1:((⍺!⍵),⍺)⍴⍳⍵          
[2]        X←(⍳N)∘.>⍨,1↑⍉T←1+(⍺-1)∇ N←⍵-1
[3]        ((,X)/(⍴,X)⍴⍳N),(+/X)⌿T       
[4]    }                                 
     ∇ 

      7 ssub 12
1 2 3 4  5  6  7
1 2 3 4  5  6  8
1 2 3 4  5  7  8
1 2 3 4  6  7  8
1 2 3 5  6  7  8
1 2 4 5  6  7  8
...
1 7 8 9 10 11 12
2 7 8 9 10 11 12
3 7 8 9 10 11 12
4 7 8 9 10 11 12
5 7 8 9 10 11 12
6 7 8 9 10 11 12
      ⍴ 7 ssub 12
792 7
      7!12
792

强行写成一行也不是不行

      3{({((,X)/(⍴,X)⍴⍳N),(+/X←(,1↑⍉T)∘.>⍳N←I+≢⍉⍵)⌿T←1+⍵}⍣(⍺-1))⍪⍳1+I←⍵-⍺}5
1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5

用 April

CL-USER> (setf (symbol-function 'ssub) (april:april "{({((,X)/(⍴,X)⍴⍳N),(+/X←(T[;1])∘.>⍳N←I+≢⍉⍵)⌿T←1+⍵}⍣(⍺-1))⍪⍳1+I←⍵-⍺}"))
#<COMPILED-LEXICAL-CLOSURE #x30200158614F>
CL-USER> (ssub 5 3)
#2A((1 2 3)
    (1 2 4)
    (1 3 4)
    (2 3 4)
    (1 2 5)
    (1 3 5)
    (2 3 5)
    (1 4 5)
    (2 4 5)
    (3 4 5))
7

我觉得还是去学好算法再来写数学吧 :stuck_out_tongue:

8

有两种做法：

  1. 先计算 [1 2 3 4 5]所有子集，然后在这些子集里过滤出长度为n的那些子集，这个算法用递归很容易实现。

  2. 另一种方法，更高效（很可能是最优算法），方法是这样的：

    比方说：你有一个List nums是 [1 2 3 4 5]，求它的n组合（假定n=4）。你需要先生成一个初值[1,2,3,4]，然后不断的求它的后继，每一个后继就是一个组合。这个想法其实也很自然：

    初值是 [1,2,3,4]

    下一个值，就是动最后一位4->5，即： [1,2,3,5]

    再下一个值是 [1,2,3,6]，但6不属于nums，所以此时要动倒数第二位 3->4，即：[1,2,4,5]

    以此类推。。。

    当然，这个方法我自己也没有写过。你有兴趣的话，可以尝试以下，写好了给我看看，多谢（你如果不写的话，过几天我有时间的话，可能会写一下）

注：这两种算法求出来的序是一样的。

9

原问题等价于从 [0, 1, 2, …, n-1] 中选出所有不重复的 m 个元素，也就是 0<=a[0]<a[1]<a[2]<...<a[m-1]<n。所以实际上相当于一种特殊进制的数字不停+1。

#include <cstdio>
using namespace std;

const int MAXN = 100;
int N = 20, M = 5; // 从 N 个东西中选 M 个
int a[MAXN];

void print() {
    for (int i = 0; i < M; ++i)
        printf("\t%d", a[i]);
    puts("");
}

bool next() {
    for (int i = M-1; i >= 0; --i) {
        int b = N-M+i; // 当前位可取的最大的值
        if (a[i] < b) {
            a[i]++;
            for (int j = 1; i+j < M; ++j) {
                a[i+j] = a[i]+j; // 后面的全部设成能取到的最小值
            }
            return true;
        }
    }
    return false; // 已经到最大了
}

int main() {
    // 初始化
    for (int i = 0; i < M; ++i) {
        a[i] = i;
    }
    int ans = 0;
    // 求解
    do {
        ans++;
        print();
    } while (next());
    printf("total = %d\n", ans);
    return 0;
}
10

我感觉你的方法有些局限，我想要的方法是对任意一个nums取出n个进行组合
你的方法里好像nums太特殊化了

11

没关系啊，只要 nums 的元素可以遍历就行了

12

等价的，有了下标不就可以根据下标取元素了么。