我想编写一个函数,该函数接受字母数组作为参数以及要选择的这些字母的数量。
比如你提供了一个由8个字母组成的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
由3个字母组成的返回数组(或单词)。
我想编写一个函数,该函数接受字母数组作为参数以及要选择的这些字母的数量。
比如你提供了一个由8个字母组成的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
由3个字母组成的返回数组(或单词)。
一个Lisp宏生成所有值r(每次取出)的代码
(defmacro txaat (some-list taken-at-a-time)
(let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
`(
,@(loop for i below taken-at-a-time
for j in vars
with nested = nil
finally (return nested)
do
(setf
nested
`(loop for ,j from
,(if (< i (1- (length vars)))
`(1+ ,(nth (1+ i) vars))
0)
below (- (length ,some-list) ,i)
,@(if (equal i 0)
`(collect
(list
,@(loop for k from (1- taken-at-a-time) downto 0
append `((nth ,(nth k vars) ,some-list)))))
`(append ,nested))))))))
所以,
CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))
(NTH B '(A B C D))
(NTH C '(A B C D))))))
T
CL-USER>
而且,
CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER>
这里有一个使用相同算法的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))
void combine(char a[], int N, int M, int m, int start, char result[]) {
if (0 == m) {
for (int i = M - 1; i >= 0; i--)
std::cout << result[i];
std::cout << std::endl;
return;
}
for (int i = start; i < (N - m + 1); i++) {
result[m - 1] = a[i];
combine(a, N, M, m-1, i+1, result);
}
}
void combine(char a[], int N, int M) {
char *result = new char[M];
combine(a, N, M, M, 0, result);
delete[] result;
}
#include <stdio.h>
unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;
if (k > 0) {
for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < (n - 1) - (k - 1) + i) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1] + 1;
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++) {
ar[i] = i;
}
}
}
return changed;
}
typedef void(*printfn)(const void *, FILE *);
void print_set(const unsigned int *ar, size_t len, const void **elements,
const char *brackets, printfn print, FILE *fptr)
{
unsigned int i;
fputc(brackets[0], fptr);
for (i = 0; i < len; i++) {
print(elements[ar[i]], fptr);
if (i < len - 1) {
fputs(", ", fptr);
}
}
fputc(brackets[1], fptr);
}
int main(void)
{
unsigned int numbers[] = { 0, 1, 2 };
char *elements[] = { "a", "b", "c", "d", "e" };
const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
const unsigned int n = sizeof(elements) / sizeof(const char*);
do {
print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
putchar('\n');
} while (next_combination(numbers, n, k));
getchar();
return 0;
}
def combinations[A](s: List[A], k: Int): List[List[A]] =
if (k > s.length) Nil
else if (k == 1) s.map(List(_))
else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)
短小快速的C语言实现
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
else { comb[++i] = comb[i - 1]; }
} else i--; }
}
要看它有多快,请使用此代码进行测试
#include <time.h>
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int c = 0; int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
/* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
if (i == p - 1) c++;
else { comb[++i] = comb[i - 1]; }
} else i--; }
printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}
在cmd.exe(Windows)中进行测试:
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.
c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in 5.781 second(s)
c:\Program Files\lcc\projects>
nCk
组合。假设集合元素从 1
到 n
。#include<stdio.h>
#include<stdlib.h>
int nCk(int n,int loopno,int ini,int *a,int k)
{
static int count=0;
int i;
loopno--;
if(loopno<0)
{
a[k-1]=ini;
for(i=0;i<k;i++)
{
printf("%d,",a[i]);
}
printf("\n");
count++;
return 0;
}
for(i=ini;i<=n-loopno-1;i++)
{
a[k-1-loopno]=i+1;
nCk(n,loopno,i+1,a,k);
}
if(ini==0)
return count;
else
return 0;
}
void main()
{
int n,k,*a,count;
printf("Enter the value of n and k\n");
scanf("%d %d",&n,&k);
a=(int*)malloc(k*sizeof(int));
count=nCk(n,k,0,a,k);
printf("No of combinations=%d\n",count);
}
Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
If PicksIndex < PicksArray.Length Then
For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
PicksArray(PicksIndex) = PoolArray(i)
CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
Next
Else
' completed combination. build your collections using PicksArray.
End If
End Sub
Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
Dim nPicks as UInteger = 5
Dim Picks(nPicks - 1) As UInteger
CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)
由于没有提到编程语言,我假设列表也可以。这里有一个适用于短列表(非尾递归)的OCaml版本。给定一个l元素为任何类型的列表和一个整数n,它将返回一个包含n个l元素的所有可能列表的列表,如果我们假设结果列表中的元素顺序被忽略,即列表['a';'b']与['b';'a']相同且只报告一次。因此,结果列表的大小将是((List.length l) Choose n)。
递归的直觉如下:您取出列表的头,然后进行两个递归调用:
为了合并递归结果,请使用奇怪的名称 list-multiply(请忍受)将列表头与 RC1 的结果进行 list-multiply,然后附加 (@) RC2 的结果。List-multiply 是以下操作 lmul
:
a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]
lmul
在下面的代码中实现为
List.map (fun x -> h::x)
当列表的大小等于您想要选择的元素数量时,递归终止,此时您只需返回列表本身。
因此,以下是一个使用OCaml实现上述算法的四行代码:
let rec choose l n = match l, (List.length l) with
| _, lsize when n==lsize -> [l]
| h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)
| [], _ -> []
以下是使用宏的Lisp方法。这适用于Common Lisp并应该适用于其他Lisp方言。
下面的代码创建了'n'个嵌套循环,并针对来自列表lst
的'n'个元素组合执行任意代码块(存储在body
变量中)。变量var
指向一个包含用于循环的变量的列表。
(defmacro do-combinations ((var lst num) &body body)
(loop with syms = (loop repeat num collect (gensym))
for i on syms
for k = `(loop for ,(car i) on (cdr ,(cadr i))
do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
finally (return k)))
(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))
(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
(LOOP FOR #:G3216 ON (CDR #:G3217) DO
(LOOP FOR #:G3215 ON (CDR #:G3216) DO
(LOOP FOR #:G3214 ON (CDR #:G3215) DO
(LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
(PROGN (PPRINT (MAPCAR #'CAR P))))))))
(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))
(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...
body
代码而不是存储所有结果的可能性也提供了更多的灵活性。