我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由3个字母组成。
当前回答
如果你可以使用SQL语法——比如，如果你使用LINQ访问一个结构或数组的字段，或者直接访问一个数据库，其中有一个名为“Alphabet”的表，只有一个字符字段“Letter”，你可以适应以下代码:
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
这将返回所有3个字母的组合，不管你在表格“字母表”中有多少个字母(它可以是3,8,10,27等)。
如果你想要的是所有的排列，而不是组合(也就是说，你想要“ACB”和“ABC”被视为不同的，而不是只出现一次)，只需删除最后一行(and一行)，就完成了。
Post-Edit:重新阅读问题后，我意识到需要的是通用算法，而不仅仅是选择3个项目的特定算法。Adam Hughes的答案是完整的，不幸的是我还不能投票。这个答案很简单，但只适用于你想要三样东西的时候。
其他回答
你可以使用Asif算法来生成所有可能的组合。这可能是最简单和最有效的方法。你可以在这里查看媒体文章。
让我们看看JavaScript中的实现。
function Combinations( arr, r ) {
// To avoid object referencing, cloning the array.
arr = arr && arr.slice() || [];
var len = arr.length;
if( !len || r > len || !r )
return [ [] ];
else if( r === len )
return [ arr ];
if( r === len ) return arr.reduce( ( x, v ) => {
x.push( [ v ] );
return x;
}, [] );
var head = arr.shift();
return Combinations( arr, r - 1 ).map( x => {
x.unshift( head );
return x;
} ).concat( Combinations( arr, r ) );
}
// Now do your stuff.
console.log( Combinations( [ 'a', 'b', 'c', 'd', 'e' ], 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))))))))
So,
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>
And,
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>
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;
}
在第一个函数中，m表示还需要选择多少个，start表示必须从数组中的哪个位置开始选择。
https://gist.github.com/3118596
JavaScript有一个实现。它有函数来获得k组合和任意对象数组的所有组合。例子:
k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]
combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
我有一个用于project euler的排列算法，用python编写:
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
If
n<len(l)
你应该有所有你需要的组合，没有重复，你需要吗?
它是一个生成器，所以你可以这样使用它:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
