详解C#的排列组合

排列组合的概念

排列:从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列(Arrangement)。

组合:从m个不同的元素中,任取n(n≤m)个元素为一组,叫作从m个不同元素中取出n个元素的一个组合。

排列组合实现代码

上一个项目做的一个水路的路径规划时,用到了排列的数据结构。求任意N个点里M个点的不同顺序的组合个数。

这样求最优路径。下面贴一段不知道哪里找的排列组合的算法。

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;
 }
 }

    求组合:求5个数里任意3个数的组合

 static void Main(string[] args)
 {
 int[] IntArr = new int[] { 1, 2, 3, 4, 5 }; //整型数组
 List<int[]> ListCombination = PermutationAndCombination<int>.GetCombination(IntArr, 3); //求全部的3-3组合
 foreach(int[] arr in ListCombination)
 {
 foreach(int item in arr)
 {
 Console.Write(item + " ");
 }
 Console.WriteLine("");
 }
 Console.ReadKey();
 }

求排列:5个数取3个的任意排列

 int[] IntArr = new int[] { 1, 2, 3, 4, 5 }; //整型数组
 List<int[]> ListCombination = PermutationAndCombination<int>.GetPermutation(IntArr, 3); //求全部的5取3排列
 foreach(int[] arr in ListCombination)
 {
 foreach(int item in arr)
 {
 Console.Write(item + " ");
 }
 Console.WriteLine("");
 }

以上就是本文的全部内容,希望对大家有所帮助!

(0)

相关推荐

  • C#组合模式实例详解

    本文实例讲述了C#组合模式.分享给大家供大家参考.具体如下: Company.cs如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { public abstract class Company { protected string name; public Company(string name) { t

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • C#查找字符串所有排列组合的方法

    本文实例讲述了C#查找字符串所有排列组合的方法.分享给大家供大家参考.具体实现方法如下: // 1. remove first char // 2. find permutations of the rest of chars // 3. Attach the first char to each of those permutations. // 3.1 for each permutation, move firstChar in all indexes // to produce even

  • 使用php计算排列组合的方法

    前些天因为业务需要写了一段计算排列组合的代码,今天整理了一下,以备后用 复制代码 代码如下: <?php/** * 要解决的数学问题    :算出C(a,1) * C(b, 1) * ... * C(n, 1)的组合情况,其中C(n, 1)代表从n个元素里任意取一个元素 * * 要解决的实际问题样例:某年级有m个班级,每个班的人数不同,现在要从每个班里抽选一个人组成一个小组, *                       由该小组来代表该年级参加学校的某次活动,请给出所有可能的组合 *//*

  • C#组合函数的使用详解

    如下所示: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Text;namespace ConsoleApplication1{ class Class1    {        static string[] str = { "A", "B", "C", "D", "E" };        static voi

  • C#实现排列组合算法完整实例

    排列组合是常见的数学问题,本文就以完整实例形式讲述了C#实现排列组合算法的方法.分享给大家供大家参考之用.具体方法如下: 首先,数学中排列组合,可表示为:排列P(N,R) 其实排列实现了,组合也就实现了,组合C(N,R)就是P(N,R)/P(R,R) ,实现这一功能比较简单的是递归算法,但考虑到递归的性能,下面采用了2种非递归的方法,具体代码如下 using System; using System.Collections.Generic; namespace Test { class Prog

  • 详解C#的排列组合

    排列组合的概念 排列:从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列(Arrangement). 组合:从m个不同的元素中,任取n(n≤m)个元素为一组,叫作从m个不同元素中取出n个元素的一个组合. 排列组合实现代码 上一个项目做的一个水路的路径规划时,用到了排列的数据结构.求任意N个点里M个点的不同顺序的组合个数. 这样求最优路径.下面贴一段不知道哪里找的排列组合的算法. public class PermutationAndCombin

  • C语言中递归和排列组合详解

    目录 排列组合三大问题: 1.打印n个数的全排列 2.打印n个数中任意m个数的全排列 3.打印n个数中任意m个数的组合 完整代码如下: 总结 排列组合三大问题: 1.打印n个数的全排列2.打印n个数中任意m个数的全排列3.打印n个数中任意m个数的组合 1.打印n个数的全排列 这个题实际上是可以直接用STL中的next_permutation()函数,代码如下: #include<bits/stdc++.h> using namespace std; int main(){ int data[4

  • 算法之排列算法与组合算法详解

    1. 前言 本文介绍了常用的排列组合算法,包括全排列算法,全组合算法,m个数选n个组合算法等. 2. 排列算法 常见的排列算法有: (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 (E)递归法 介绍常用的两种: (1) 字典序法 对给定的字符集中的字符规定了一个先后关系,在此基础上按照顺序依次产生每个排列. [例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321. 生成给定全排列的下一个排列 所谓一个的

  • C语言详解Z字形变换排列的实现

    目录 方法一 方法二 题目链接:Z 字形变换 方法一 ——找规律模拟数组 题目要求构造一个从左到右的Z型矩阵. 通过分析,可以看出这个Z型矩阵的特点 Z型矩阵就是如图中的橙色,绿色这样部分组合在一起的,Z型矩阵就是由一个个这样相同周期组成的. 这里有一种情况需要特殊讨论,当矩阵只有一行时,直接返回原字符. 其余情况均可满足. 其周期的构成满足这样一个规律: 在第一列向下填写矩阵行数r个字符,接着向其右上部分共(r-2)列分别填写一个字符.Z型矩阵的周期t=r+r-2=2*r-2,每个周期会占用矩

  • JS 面向对象之继承---多种组合继承详解

    这一次要讲 组合.原型式.寄生式.寄生组合式继承方式. 1. 组合继承:又叫伪经典继承,是指将原型链和借用构造函数技术组合在一块的一种继承方式. 下面来看一个例子: function SuperType(name) { this.name = name; this.colors = ["red", "blue", "green"]; } SuperType.prototype.sayName = function() { alert(this.n

  • [js高手之路]从原型链开始图解继承到组合继承的产生详解

    于javascript原型链的层层递进查找规则,以及原型对象(prototype)的共享特性,实现继承是非常简单的事情 一.把父类的实例对象赋给子类的原型对象(prototype),可以实现继承 function Person(){ this.userName = 'ghostwu'; } Person.prototype.showUserName = function(){ return this.userName; } function Teacher (){} Teacher.protot

  • JSP 中Spring组合注解与元注解实例详解

    JSP 中Spring组合注解与元注解实例详解 摘要: 注解(Annotation),也叫元数据.一种代码级别的说明.它与类.接口.枚举是在同一个层次.它可以声明在包.类.字段.方法.局部变量.方法参数等的前面,用来对这些元素进行说明 1. 可以注解到别的注解上的注解称为元注解,被注解的注解称为组合注解,通过组合注解可以很好的简化好多重复性的注解操作 2. 示例组合注解 import org.springframework.context.annotation.ComponentScan; im

  • spring mvc 组合mybatis框架实例详解

    说明 本项目采用 maven 结构,主要演示了 spring mvc + mybatis,controller 获取数据后以json 格式返回数据. 项目结构 包依赖 与说明 pom文件: <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://

  • 详解MySQL子查询(嵌套查询)、联结表、组合查询

    一.子查询 MySQL 4.1版本及以上支持子查询 子查询:嵌套在其他查询中的查询. 子查询的作用: 1.进行过滤: 实例1:检索订购物品TNT2的所有客户的ID = + 一般,在WHERE子句中对于能嵌套的子查询的数目没有限制,不过在实际使用时由于性能的限制,不能嵌套太多的子查询. 注意:列必须匹配 --在WHERE子句中使用子查询(如这里所示),应该保证SELECT语句具有与WHERE子句中相同数目的列.通常,子查询将返回单个列并且与单个列匹配,但如果需要也可以使用多个列. 示例2:返回订购

  • Mysql之组合索引方法详解

    对于任何DBMS,索引都是进行优化的最主要的因素.对于少量的数据,没有合适的索引影响不是很大,但是,当随着数据量的增加,性能会急剧下降. 如果对多列进行索引(组合索引),列的顺序非常重要,MySQL仅能对索引最左边的前缀进行有效的查找.例如: 假设存在组合索引(c1,c2),查询语句select * from t1 where c1=1 and c2=2能够使用该索引.查询语句select * from t1 where c1=1也能够使用该索引.但是,查询语句select * from t1

随机推荐