-- 作者:大红袍
-- 发布时间:2016/1/27 11:59:00
--
mark 排列组合 写一个规范一点的类
全局代码
Public Class PermutationAndCombination(Of T) \'\'\' <summary> \'\'\' 交换两个变量 \'\'\' </summary> \'\'\' <param name="a">变量1</param> \'\'\' <param name="b">变量2</param> Public Shared Sub Swap(ByRef a As T, ByRef b As T) Dim temp As T = a a = b b = temp End Sub
\'\'\' <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 Shared Sub GetCombination(ByRef list As List(Of T()), t As T(), n As Integer, m__1 As Integer, b As Integer(), M__2 As Integer) For i As Integer = n To m__1 Step -1 b(m__1 - 1) = i - 1 If m__1 > 1 Then GetCombination(list, t, i - 1, m__1 - 1, b, M__2) Else If list Is Nothing Then list = New List(Of T())() End If Dim temp As T() = New T(M__2 - 1) {} For j As Integer = 0 To b.Length - 1 temp(j) = t(b(j)) Next list.Add(temp) End If Next End Sub
\'\'\' <summary> \'\'\' 递归算法求排列(私有成员) \'\'\' </summary> \'\'\' <param name="list">返回的列表</param> \'\'\' <param name="t">所求数组</param> \'\'\' <param name="startIndex">起始标号</param> \'\'\' <param name="endIndex">结束标号</param> Private Shared Sub GetPermutation(ByRef list As List(Of T()), t As T(), startIndex As Integer, endIndex As Integer) If startIndex = endIndex Then If list Is Nothing Then list = New List(Of T())() End If Dim temp As T() = New T(t.Length - 1) {} t.CopyTo(temp, 0) list.Add(temp) Else For i As Integer = startIndex To endIndex Swap(t(startIndex), t(i)) GetPermutation(list, t, startIndex + 1, endIndex) Swap(t(startIndex), t(i)) Next End If End Sub
\'\'\' <summary> \'\'\' 求从起始标号到结束标号的排列,其余元素不变 \'\'\' </summary> \'\'\' <param name="t">所求数组</param> \'\'\' <param name="startIndex">起始标号</param> \'\'\' <param name="endIndex">结束标号</param> \'\'\' <returns>从起始标号到结束标号排列的范型</returns> Public Shared Function GetPermutation(t As T(), startIndex As Integer, endIndex As Integer) As List(Of T()) If startIndex < 0 OrElse endIndex > t.Length - 1 Then Return Nothing End If Dim list As New List(Of T())() GetPermutation(list, t, startIndex, endIndex) Return list End Function
\'\'\' <summary> \'\'\' 返回数组所有元素的全排列 \'\'\' </summary> \'\'\' <param name="t">所求数组</param> \'\'\' <returns>全排列的范型</returns> Public Shared Function GetPermutation(t As T()) As List(Of T()) Return GetPermutation(t, 0, t.Length - 1) End Function
\'\'\' <summary> \'\'\' 求数组中n个元素的排列 \'\'\' </summary> \'\'\' <param name="t">所求数组</param> \'\'\' <param name="n">元素个数</param> \'\'\' <returns>数组中n个元素的排列</returns> Public Shared Function GetPermutation(t As T(), n As Integer) As List(Of T()) If n > t.Length Then Return Nothing End If Dim list As New List(Of T())() Dim c As List(Of T()) = GetCombination(t, n) For i As Integer = 0 To c.Count - 1 Dim l As New List(Of T())() GetPermutation(l, c(i), 0, n - 1) list.AddRange(l) Next Return list End Function
\'\'\' <summary> \'\'\' 求数组中n个元素的组合 \'\'\' </summary> \'\'\' <param name="t">所求数组</param> \'\'\' <param name="n">元素个数</param> \'\'\' <returns>数组中n个元素的组合的范型</returns> Public Shared Function GetCombination(t As T(), n As Integer) As List(Of T()) If t.Length < n Then Return Nothing End If Dim temp As Integer() = New Integer(n - 1) {} Dim List As New List(Of T())() GetCombination(List, t, t.Length, n, temp, n) Return List End Function End Class
调用代码
Dim arr As String() = {"a", "b", "c"} \'求排列 Dim lst_Permutation As List(Of String()) = PermutationAndCombination(Of String).GetPermutation(arr, 2) \'求组合 Dim lst_Combination As List(Of String()) = PermutationAndCombination(Of String).GetCombination(arr, 2)
For Each ary As String() In lst_Permutation output.show(ary(0) & ary(1)) Next output.show("-------------------------") For Each ary As String() In lst_Combination output.show(ary(0) & ary(1)) next
|