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

假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:

8! / ((8 - 3)! * 3!) = 56

数组(或单词),每个数组由3个字母组成。


当前回答

算法:

从1数到2^n。 将每个数字转换为二进制表示。 根据位置,将每个“on”位转换为集合中的元素。

在c#中:

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };

    var kElement = 2;

    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

为什么它能起作用?

在n元素集的子集和n位序列之间存在双射。

这意味着我们可以通过数数序列来计算出有多少个子集。

例如,下面的四个元素集可以用{0,1}X {0,1} X {0,1} X{0,1}(或2^4)个不同的序列表示。

我们要做的就是从1数到2^n来找到所有的组合。(我们忽略空集。)接下来,将数字转换为二进制表示。然后将集合中的元素替换为“on”位。

如果只需要k个元素的结果,则只在k位为“on”时打印。

(如果你想要所有的子集,而不是k长度的子集,删除cnt/kElement部分。)

(有关证明,请参阅麻省理工学院免费课件计算机科学数学,雷曼等,第11.2.2节。https://ocw.mit.edu/courses/electrical -工程-和-计算机- science/6 - 042 j -数学- -计算机科学-下降- 2010/readings/)

其他回答

下面是我的Scala解决方案:

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)

说了这么多,做了这么多,这就是奥卡姆的代码。 算法是显而易见的代码..

let combi n lst =
    let rec comb l c =
        if( List.length c = n) then [c] else
        match l with
        [] -> []
        | (h::t) -> (combi t (h::c))@(combi t c)
    in
        combi lst []
;;

如果你可以使用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的答案是完整的,不幸的是我还不能投票。这个答案很简单,但只适用于你想要三样东西的时候。

下面的递归算法从有序集中选取所有k元素组合:

选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。

对集合中的每一个i进行上述迭代。

为了避免重复,您必须选择比i大的其余元素。这样[3,5]将只被选中一次,即[3]与[5]结合,而不是两次(该条件消除了[5]+[3])。没有这个条件,你得到的是变化而不是组合。

下面是我最近用Java写的一段代码,它计算并返回从“outOf”元素中“num”元素的所有组合。

// author: Sourabh Bhat (heySourabh@gmail.com)

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}