我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。

假设您提供了一个包含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的答案是完整的,不幸的是我还不能投票。这个答案很简单,但只适用于你想要三样东西的时候。

其他回答

像Andrea Ambu一样用Python写的,但不是硬编码来选择三个。

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            print [list[index] for index in seq]
            seq = get_next_combination(len(list), k, seq)

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1

            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1

            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None   

这里你有一个用c#编写的该算法的惰性评估版本:

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

及测试部分:

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

希望这对你有帮助!


另一种版本,迫使所有前k个组合首先出现,然后是所有前k+1个组合,然后是所有前k+2个组合,等等。这意味着如果你对数组进行排序,最重要的在最上面,它会把它们逐渐扩展到下一个——只有在必须这样做的时候。

private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
    if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
        return true;

    if (num[k - 1] + 1 == n)
        return false;

    ++num[k - 1];
    for (int i = 0; i < k - 1; ++i)
        num[i] = i;

    return true;
}

例如,如果你在k=3, n=5上运行第一个方法("nextCombination"),你会得到:

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

但如果你跑

int[] nums = new int[k];
for (int i = 0; i < k; ++i)
    nums[i] = i;
do
{
    Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));

你会得到这个(为了清晰起见,我添加了空行):

0 1 2

0 1 3
0 2 3
1 2 3

0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4

它只在必须添加时才添加“4”,而且在添加“4”之后,它只在必须添加时再添加“3”(在执行01、02、12之后)。

我有一个用于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 

另一种python递归解决方案。

def combination_indicies(n, k, j = 0, stack = []):   
    if len(stack) == k:            
        yield list(stack)
        return
        
    for i in range(j, n):
        stack.append(i)
        for x in combination_indicies(n, k, i + 1, stack):            
            yield x
        stack.pop()  
        
list(combination_indicies(5, 3))

输出:

[[0, 1, 2],
 [0, 1, 3],
 [0, 1, 4],
 [0, 2, 3],
 [0, 2, 4],
 [0, 3, 4],
 [1, 2, 3],
 [1, 2, 4],
 [1, 3, 4],
 [2, 3, 4]]

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>