排列组合算法怎样写

Question

这叫做全排列。using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = "ABCD";
            List<string> list = new List<string>();
            foreach (var i in Combo(s, 4))
            {
                list = list.Union(Arrange(i)).ToList();
            }
            list.ForEach(x => Console.WriteLine(x));
        }
        static IEnumerable<string> Arrange(string source)
        {
            for (int i = 0; i < source.Length; i++)
            {
                if (source.Length == 1)
                {
                    yield return source;
                }
                else
                {
                    foreach (var x in Arrange(source.Substring(0, i) + source.Substring(i + 1)))
                    {
                        yield return source[i] + x;
                    }
                }
            }
        }        static IEnumerable<string> Combo(string source, int len)
        {
            int[] pos = new int[len];
            for (int i = 0; i < len; i++) pos[i] = i;
            while (pos[0] < source.Length - len)
            {
                string str = "";
                for (int i = 0; i < len; i++) str += source[pos[i]];
                for (int i = len - 1; i >= 0; i--)
                {
                    if (pos[i] < source.Length - len + i)
                    {
                        pos[i]++;
                        for (int j = i + 1; j <= len - 1; j++)
                        {
                            pos[j] = pos[i] + j - i;
                        }
                        break;
                    }
                    else
                    {
                        continue;
                    }
                }
                yield return str;
            }
            yield return source.Substring(source.Length - len);
        }
    }
}

Answer 1

来个数字的
  const int n = 6;
    protected void Page_Load(object sender, EventArgs e)
    {
        int[] a = new int[n];
        pai(a, 0, n);
    }
    private void printf(int[] a)
    {
        for (int i = 0; i < a.Length; i++)
            Response.Write(a[i].ToString());
        Response.Write("<br />");
    }
    private bool jiancha(int[] a, int t)
    {
        for (int i = 0; i < a.Length; i++)
            if (a[i] == t)
                return false;
        return true;
    }
    private void pai(int[] a, int i, int j)
    {
        if (i >= j)
            printf(a);
        for (int t = 1; t <= n; t++)
        {
            if (jiancha(a, t))
            {
                a[i] = t;
                pai(a, i + 1, j);
                a[i] = 0;
            }
        }
    }

Answer 2

简写一些#1楼的代码：using System;
using System.Collections.Generic;
using System.Linq;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            排列组合("ABC", 0, 3).ToList().ForEach(x => { Console.WriteLine(x); });
            Console.ReadKey();
        }        private static IEnumerable<string> 排列组合(string source, int fr, int len)
        {
            if (len == 1)
                yield return source.Substring(fr, 1);
            else if (len > 1)
            {
                foreach (var sub in 排列组合(source, fr + 1, len - 1))
                    for (var i = 0; i <= sub.Length; i++)
                        yield return sub.Insert(i, source.Substring(fr, 1));
            }
        }
    }
}

Answer 3

另外，写为Linq查询表达式也是一样的。因为Linq也会使用yield迭代器来延迟计算，所以不用担心Linq的效率问题。使用Linq看起来逻辑上更优雅：using System;
using System.Collections.Generic;
using System.Linq;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            排列组合("ABC", 0, 3).ToList().ForEach(x => { Console.WriteLine(x); });
            Console.ReadKey();
        }        private static IEnumerable<string> 排列组合(string source, int fr, int len)
        {
            if (len == 1)
                return new List<string> { source.Substring(fr, 1) };
            else
                return from sub in 排列组合(source, fr + 1, len - 1)
                       from i in Enumerable.Range(0, sub.Length + 1)
                       let first = source.Substring(fr, 1)
                       select sub.Insert(i, first);
        }
    }
}
很简单的查询，不用写一大堆麻烦的for循环之类的代码！

Answer 4

另外假设你需要同时打印排列序号，可以写排列组合("ABCD", 0, 4).Select((x, i) => new { i = i, s = x })
    .ToList()
    .ForEach(x => { Console.WriteLine("第{0:D2}个排列是:{1}", x.i + 1, x.s); });

Answer 5

你好，我刚接触C#，是个菜鸟，您这个是C#代码？麻烦可以用C#代码写个类给我吗？谢谢。

Answer 6

没事，sp1234写的代码无论lz看懂没看懂，都不要紧。因为已经给我很多启发。

Answer 7

排列组合在数学中，主要是利用这样的形式A(n,m)和C(n,m)以及高中或者大学学过的排列组合计算方法。实现函数A(n,m)和C(n,m)，然后直接计算就行了，比如A(2,3)*C(3,4)/A(2,2)

Answer 8

我使用的vs2005, Miscrosoft.NET Framework 版本 2.0.50727 SP2
这些版本支持，我在vs2005  总是报语法错误.请问是不是要在大于2.0版本之上才支持哦。谢！

Answer 9

C# 2.0的确不支持LINQ，但是我1L的代码还是可以用，因为yield已经支持。
只是调用部分略微需要修改下。

Answer 10

大多数算法基于数学归纳法，或者编程上就是简单的递归。假设 n-1 个字符的组合数是 P(n-1)，那么P(n)自然就是 n*P(n-1)，因为就是把最后增加第n个字符插入P(n-1)时的结果中的每一个可以插入字符的位置中。于是递推：
    P(n) = n * P(n-1)
    P(n-1) = (n-1) * P(n-2)
    .....
    P(1) = 1
结果自然就是: P(n) = n!

Answer 11

程序员应该有基本的代码变化的能力。比如将任何递归代码转换成非递归的版本的能力。简化布尔表达式和复杂算术表达式的能力。将任何同步的代码转换成异步，把异步代码转换成同步的能力。使用委托/事件模型改写具有大量分支判断的代码。将循环和函数调用内联合展开，或者将重复代码抽象成函数的能力。将一种语言语法不支持的参考程序转换成所用程序支持的等价形式的能力。模拟实现一种API中不具备的，在另一种系统中定义的系统函数的能力。总之一个优秀的程序员应该具有超越编译器和重构软件的，从更高层次上思考程序，并且在细节上任意操纵代码的能力。

Answer 12

验证完毕看来一定要好好学习Linq把很多东西都简化了

Answer 13

今天刚刚飘过，想知道 如果是"A""B""C""D"，这串字符的每个字符又包括若干不等的字母，想要把他们下面的那些字母排列组合，该怎么写呢 ，，，，