[散分][分享]写了个C#的排列类

Question

由于项目中需要，就写了个排列类，代码如下：
//-----------------------------------------------------------------------------
//
// 算法：排列类
//
// 版权所有(C) Snowdust
// 个人博客    http://blog.csdn.net/snwodust & http://snowdust.cnblogs.com
// MSN & Email [email protected]
//
// 此源代码可免费用于各类软件（含商业软件）
// 允许对此代码的进一步修改与开发
// 但必须完整保留此版权信息
//
// 调用方法如下：
//
// 1.GetPermutation(T[], startIndex, endIndex)
// 返回从startIndex到endIndex的排列
//
// 2.GetPermutation(T[])
// 返回数组所有元素的全排列
//
// 版本历史：
// V0.1 2010-01-20 摘要：首次创建 
//
//-----------------------------------------------------------------------------using System;
using System.Collections.Generic;namespace Arithmetic
{
public class Permutation<T>
{
/// <summary>
/// 交换两个变量
/// </summary>
/// <param name="a">变量1</param>
/// <param name="b">变量2</param>
public static void Swap(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
} /// <summary>
/// 递归算法求排列(私有成员)
/// </summary>
/// <param name="list">返回的列表</param>
/// <param name="t">原始数组</param>
/// <param name="startIndex">起始标号</param>
/// <param name="endIndex">结束标号</param>
private static void GetPermutation(ref List<T[]> list, T[] t, int startIndex, int endIndex)
{
if (startIndex == endIndex)
{
if (list == null)
{
list = new List<T[]>();
}
T[] temp = new T[t.Length];
t.CopyTo(temp, 0);
list.Add(temp);
}
else
{
for (int i = startIndex; i <= endIndex; i++)
{
Swap(ref t[startIndex], ref t[i]);
GetPermutation(ref list, t, startIndex + 1, endIndex);
Swap(ref t[startIndex], ref t[i]);
}
}
} /// <summary>
/// 求数组的排列
/// </summary>
/// <param name="t">原始数组</param>
/// <param name="startIndex">起始标号</param>
/// <param name="endIndex">结束标号</param>
/// <returns>从起始标号到结束标号的排列</returns>
public static List<T[]> GetPermutation(T[] t, int startIndex, int endIndex)
{
if (startIndex < 0 || endIndex > t.Length - 1)
{
return null;
}
List<T[]> list = new List<T[]>();
GetPermutation(ref list, t, startIndex, endIndex);
return list;
} /// <summary>
/// 求数组的排列
/// </summary>
/// <param name="t">原始数组</param>
/// <returns>全排列</returns>
public static List<T[]> GetPermutation(T[] t)
{
return GetPermutation(t, 0, t.Length - 1);
}
}
}调用：int[] arr = new int[5];
for (int i = 0; i < arr.Length; i++)
{
arr[i] = i + 1;
}
List<int[]> list = Arithmetic.Permutation<int>.GetPermutation(arr);本人水平有限，不足之处恳请指正，另外如果有什么建议，请提出。由于N年前以前学习数据结构的时候根本没有用心，最近在研究C#描述的数据结构和算法，还写了一些小东西，比如计算24点、迷宫最短路径和计算表达式的算法，如果大家需要我将在整理之后帖出来[每帖300分]。

Answer 1

改正一点：MSN & Email [email protected]

Answer 2

现在基本上这方面的参考资料很少，有一本电子书叫<<数据结构(C#语言描述)>>，上面的例子很少，还有一本是英文的，其它就是C/C++的了。

Answer 3

using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApp {
public class SortHelper<T> where T:IComparable
{
public void BubbleSort(T[] array) {
int length = array.Length; for (int i = 0; i <= length - 2; i++) {
for (int j = length - 1; j >= 1; j--) {

// 对两个元素进行交换
if (array[j].CompareTo(array[j - 1]) < 0 ) {
T temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
} }
}
using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApp {
public class SuperCalculator{
public int SuperAdd(int x, int y) {
return 0;
} public int SuperMinus(int x, int y) {
return 0;
} public string SuperSearch(string key) {
return null;
} public void SuperSort(int[] array) {
} public void SpeedSort<T>(T[] array) where T : IComparable {
// CODE：实现略
}
}}using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApp {
public class Book :IComparable {
private int id;
private string title; public Book() { } public Book(int id, string title) {
this.id = id;
this.title = title;
} public int Id {
get { return id; }
set { id = value; }
} public string Title {
get { return title; }
set { title = value; }
}
public int CompareTo(object obj) {
Book book2 = (Book)obj;
return this.Id.CompareTo(book2.Id);
}
}
}using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;namespace ConsoleApp {
class Program {
static void Main(string[] args) { TestSorter(); Console.ReadKey();
} private static void TestSorter() {
Book[] bookArray = new Book[2]; Book book1 = new Book(124, "C# 3.0揭秘");
Book book2 = new Book(45, ".Net之美"); bookArray[0] = book1;
bookArray[1] = book2; SortHelper<Book> sorter = new SortHelper<Book>();
sorter.BubbleSort(bookArray); foreach (Book b in bookArray) {
Console.WriteLine("Id:{0}", b.Id);
Console.WriteLine("Title:{0}\n", b.Title);
}
} private static void TestCalculator() {
SuperCalculator calculator = new SuperCalculator();
Book[] bookArray = new Book[2]; Book book1 = new Book(124, "C# 3.0揭秘");
Book book2 = new Book(45, ".Net之美"); calculator.SpeedSort(bookArray);
}
}
}

Answer 4

楼主好阔气
我在这里使劲帮你顶
UP    UP     UPUPUPU
UP    UP     UP    UP
UP    UP     UPUPUPU
UP    UP     UP
  UPUP       UP

Answer 5

List<T>不是有个Sort的方法吗？我觉的楼主，可以参考Sort，挺好的，用委托的方法，

Answer 6

先来接分。
我认为算法，明白他们的 计算流程、执行步骤、存放方式就可以了。大部分我不能背出来。但是看到算法我能理解，好多时候 我都是在Google里找的。
顶一下。

Answer 7

排列和组合算法
           10!     10!    10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
10_P_4 = ------- = ---- = -------------------------------------- = 10 x 9 x 8 x 7 = 5040 
        (10 - 4)!   6!                     6 x 5 x 4 x 3 x 2 x 1                                                10_P_4      10!         10!
     10_C_4 = -------- = ------- = ----------
                 4!      4! x 6!    4!(10-4)!
               10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
            =  --------------------------------------
                4 x 3 x 2 x 1  (6 x 5 x 4 x 3 x 2 x 1)
              10 x 9 x 8 x 7    5040
            = -------------- = ------ = 210
               4 x 3 x 2 x 1     24 

Answer 8

UP    UP    UPUPUPU 
UP    UP    UP    UP 
UP    UP    UPUPUPU 
UP    UP    UP 
  UPUP      UP

Answer 9

GOOD ！
期盼公布 计算24点、迷宫最短路径和计算表达式的算法
让大家都来学习和进步。

Answer 10

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;namespace Combinations
{
    class Iterator
    {
        public static void RotateRight<T>(IList<T> sequence, int count)
        {
            T tmp = sequence[count - 1];
            sequence.RemoveAt(count - 1);
            sequence.Insert(0, tmp);
        }        private static void RotateLeft<T>(IList<T> sequence, int start, int count)
        {
            T tmp = sequence[start];
            sequence.RemoveAt(start);
            sequence.Insert(start + count - 1, tmp);
        }        public static IEnumerable<IList<T>> Permutations<T>(IList<T> sequence, int count)
        {
            if (count == 1) yield return sequence;
            else
            {
                for (int i = 0; i < count; i++)
                {
                    foreach (var perm in Permutations(sequence, count - 1))
                        yield return perm;
                    RotateRight(sequence, count);
                }
            }
        }        public static IEnumerable<IList<T>> Permutations<T>(IList<T> sequence)
        {
            return Permutations(sequence, sequence.Count);
        }        public static IEnumerable<IList<T>> Combinations<T>(IList<T> sequence, int start, int count, int choose)
        {
            if (choose == 0) yield return sequence;
            else
            {
                for (int i = 0; i < count; i++)
                {
                    foreach (var perm in Combinations(sequence, start + 1, count - 1 - i, choose - 1))
                        yield return perm;
                    RotateLeft(sequence, start, count);
                }
            }
        }        public static IEnumerable<IList<T>> Combinations<T>(IList<T> sequence, int choose)
        {
            return Combinations(sequence, 0, sequence.Count, choose);
        }
    }
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace Combinations
{
    class Program
    {
        static void Main(string[] args)
        {
            string line, s;
            int count;
            do
            {
                Console.WriteLine("Select Demo:");
                Console.WriteLine("1 - Combinations over integers.");
                Console.WriteLine("2 - Combinations over a string.");
                Console.WriteLine("3 - Combinations and permutations.");
                Console.WriteLine("q - Quit.");
                line = Console.ReadLine();
                if (line == "q") break;
                switch (line)
                {
                    case "1":
                        CombinationsOverIntegers();
                        break;
                    case "2":
                        if (!InputParameters(out s, out count))
                            continue;
                        CombinationsOverString(s, count);
                        break;
                    case "3":
                        if (!InputParameters(out s, out count))
                            continue;
                        CombinationsPermutations(s, count);
                        break;
                }
            } while (line != "q");
        }        private static bool InputParameters(out string s, out int count)
        {
            Console.WriteLine("Enter string:");
            s = Console.ReadLine();
            Console.WriteLine("How may characters to choose?");
            if (!int.TryParse(Console.ReadLine(), out count)) return false;
            return true;
        }        private static void CombinationsPermutations(string s, int count)
        {
            foreach (var comb in Iterator.Combinations(s.ToCharArray().ToList(), count))
            {
                foreach (var perm in Iterator.Permutations(comb, count))
                {
                    string r = new string(perm.Take(count).ToArray());
                    Console.Write("{0,-8}", r);
                }
            }
            Console.WriteLine();
        }        private static void CombinationsOverString(string s, int count)
        {
            foreach (var comb in Iterator.Combinations(s.ToCharArray().ToList(), count))
            {
                string r = new string(comb.Take(count).ToArray());
                Console.Write("{0,-8}", r);
            }
            Console.WriteLine();
        }        private static void CombinationsOverIntegers()
        {
            List<int> l = new List<int>() { 1, 2, 3, 4, 5, 6 };
            int count = 4;
            foreach (var comb in Iterator.Combinations(l, count))
            {
                string s = comb.Take(count).Aggregate<int, string>("", (x, y) => x + y);
                Console.Write("{0,-8}", s);
            }
            Console.WriteLine();
        }
    }
}
我再发个给大家学习啊，我以前的资料

Answer 11

UP    UP    UPUPUPU
UP    UP    UP    UP
UP    UP    UPUPUPU
UP    UP    UP
  UPUP      UP

Answer 12

UP    UP    UPUPUPU
UP    UP    UP    UP
UP    UP    UPUPUPU
UP    UP    UP
  UPUP      UP

Answer 13

UP    UP    UPUPUPU
UP    UP    UP    UP
UP    UP    UPUPUPU
UP    UP    UP
  UPUP      UP

Answer 14

改进的排列组合类：//-----------------------------------------------------------------------------
//
// 算法：排列组合类
//
// 版权所有(C) Snowdust
// 个人博客    http://blog.csdn.net/snowdust & http://snowdust.cnblogs.com
// MSN & Email [email protected]
//
// 此源代码可免费用于各类软件（含商业软件）
// 允许对此代码的进一步修改与开发
// 但必须完整保留此版权信息
//
// 调用方法如下：
//
// 1.GetPermutation(T[], startIndex, endIndex)
// 对startIndex到endIndex进行排列，其余元素不变
//
// 2.GetPermutation(T[])
// 返回数组所有元素的全排列
//
// 3.GetPermutation(T[], n)
// 返回数组中n个元素的排列
//
// 4.GetCombination(T[], n)
// 返回数组中n个元素的组合
//
// 版本历史：
// V0.1 2010-01-20 摘要：首次创建 
//
//-----------------------------------------------------------------------------using System;
using System.Collections.Generic;namespace Algorithms
{
public class PermutationAndCombination<T>
{
/// <summary>
/// 交换两个变量
/// </summary>
/// <param name="a">变量1</param>
/// <param name="b">变量2</param>
public static void Swap(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
} /// <summary>
/// 递归算法求数组的组合(私有成员)
/// </summary>
/// <param name="list">返回的范型</param>
/// <param name="t">所求数组</param>
/// <param name="n">辅助变量</param>
/// <param name="m">辅助变量</param>
/// <param name="b">辅助数组</param>
/// <param name="M">辅助变量M</param>
private static void GetCombination(ref List<T[]> list, T[] t, int n, int m, int[] b, int M)
{
for (int i = n; i >= m; i--)
{
b[m - 1] = i - 1;
if (m > 1)
{
GetCombination(ref list, t, i - 1, m - 1, b, M);
}
else
{
if (list == null)
{
list = new List<T[]>();
}
T[] temp = new T[M];
for (int j = 0; j < b.Length; j++)
{
temp[j] = t[b[j]];
}
list.Add(temp);
}
}
} /// <summary>
/// 递归算法求排列(私有成员)
/// </summary>
/// <param name="list">返回的列表</param>
/// <param name="t">所求数组</param>
/// <param name="startIndex">起始标号</param>
/// <param name="endIndex">结束标号</param>
private static void GetPermutation(ref List<T[]> list, T[] t, int startIndex, int endIndex)
{
if (startIndex == endIndex)
{
if (list == null)
{
list = new List<T[]>();
}
T[] temp = new T[t.Length];
t.CopyTo(temp, 0);
list.Add(temp);
}
else
{
for (int i = startIndex; i <= endIndex; i++)
{
Swap(ref t[startIndex], ref t[i]);
GetPermutation(ref list, t, startIndex + 1, endIndex);
Swap(ref t[startIndex], ref t[i]);
}
}
}

/// <summary>
/// 求从起始标号到结束标号的排列，其余元素不变
/// </summary>
/// <param name="t">所求数组</param>
/// <param name="startIndex">起始标号</param>
/// <param name="endIndex">结束标号</param>
/// <returns>从起始标号到结束标号排列的范型</returns>
public static List<T[]> GetPermutation(T[] t, int startIndex, int endIndex)
{
if (startIndex < 0 || endIndex > t.Length - 1)
{
return null;
}
List<T[]> list = new List<T[]>();
GetPermutation(ref list, t, startIndex, endIndex);
return list;
} /// <summary>
/// 返回数组所有元素的全排列
/// </summary>
/// <param name="t">所求数组</param>
/// <returns>全排列的范型</returns>
public static List<T[]> GetPermutation(T[] t)
{
return GetPermutation(t, 0, t.Length - 1);
} /// <summary>
/// 求数组中n个元素的排列
/// </summary>
/// <param name="t">所求数组</param>
/// <param name="n">元素个数</param>
/// <returns>数组中n个元素的排列</returns>
public static List<T[]> GetPermutation(T[] t, int n)
{
if (n > t.Length)
{
return null;
}
List<T[]> list = new List<T[]>();
List<T[]> c = GetCombination(t, n);
for (int i = 0; i < c.Count; i++)
{
List<T[]> l = new List<T[]>();
GetPermutation(ref l, c[i], 0, n - 1);
list.AddRange(l);
}
return list;
}
/// <summary>
/// 求数组中n个元素的组合
/// </summary>
/// <param name="t">所求数组</param>
/// <param name="n">元素个数</param>
/// <returns>数组中n个元素的组合的范型</returns>
public static List<T[]> GetCombination(T[] t, int n)
{
if (t.Length < n)
{
return null;
}
int[] temp = new int[n];
List<T[]> list = new List<T[]>();
GetCombination(ref list, t, t.Length, n, temp, n);
return list;
}
}
}