我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
下面是一个使用宏的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)
...
由于默认情况下不存储组合,因此存储空间保持在最小值。选择主体代码而不是存储所有结果的可能性也提供了更大的灵活性。
其他回答
我可以给出这个问题的递归Python解决方案吗?
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
使用示例:
>>> len(list(choose_iter("abcdefgh",3)))
56
我喜欢它的简洁。
你可以使用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 ) );
也许我错过了重点(你需要的是算法,而不是现成的解决方案),但看起来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)
在Python中,利用递归的优势和所有事情都是通过引用完成的事实。对于非常大的集合,这将占用大量内存,但其优点是初始集合可以是一个复杂的对象。它只会找到唯一的组合。
import copy
def find_combinations( length, set, combinations = None, candidate = None ):
# recursive function to calculate all unique combinations of unique values
# from [set], given combinations of [length]. The result is populated
# into the 'combinations' list.
#
if combinations == None:
combinations = []
if candidate == None:
candidate = []
for item in set:
if item in candidate:
# this item already appears in the current combination somewhere.
# skip it
continue
attempt = copy.deepcopy(candidate)
attempt.append(item)
# sorting the subset is what gives us completely unique combinations,
# so that [1, 2, 3] and [1, 3, 2] will be treated as equals
attempt.sort()
if len(attempt) < length:
# the current attempt at finding a new combination is still too
# short, so add another item to the end of the set
# yay recursion!
find_combinations( length, set, combinations, attempt )
else:
# the current combination attempt is the right length. If it
# already appears in the list of found combinations then we'll
# skip it.
if attempt in combinations:
continue
else:
# otherwise, we append it to the list of found combinations
# and move on.
combinations.append(attempt)
continue
return len(combinations)
你可以这样使用它。传递'result'是可选的,所以你可以用它来获取可能组合的数量…尽管这样做效率很低(最好通过计算来完成)。
size = 3
set = [1, 2, 3, 4, 5]
result = []
num = find_combinations( size, set, result )
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)
您应该从测试数据中得到以下输出:
size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
如果你的集合是这样的,它也会工作得很好:
set = [
[ 'vanilla', 'cupcake' ],
[ 'chocolate', 'pudding' ],
[ 'vanilla', 'pudding' ],
[ 'chocolate', 'cookie' ],
[ 'mint', 'cookie' ]
]
下面是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))