1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
using System;
using System.Collections;
using System.Collections.Generic;
using AlgorithmCollection;
// 递归与分治算法
namespace AlgorithmCollection.Recursion
{
public static class RecursionHelper
{
#region 全排列，返回数据的所有组合
public static void Permutations<T>(List<T> data, ref List<List<T>> perms)
{
if (perms == null)
perms = new List<List<T>>();
foreach (List<T> perm in perms)
{
List<T> p = new List<T>(perm);
perms.Add(p);
}
}
// 生成器形式，每次返回一个组合
public static IEnumerable Permutations<T>(List<T> data)
{
foreach (var perm in _Permutations(data, 0, data.Count - 1))
{
yield return perm;
}
}
// 计算start~end范围内的全排列
private static IEnumerable _Permutations<T>(List<T> data, int start, int end, List<T> perm = null)
{
if (perm == null)
perm = new List<T>(data.Count);
if (start == end)
{
perm.Add(data[start]);
yield return perm;
perm.RemoveAt(perm.Count - 1);
}
else
{
for (int i = start; i <= end; ++i)
{
perm.Add(data[i]);
Algorithms.Swap(ref data, start, i);
IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator();
while (itor.MoveNext())
yield return itor.Current;
Algorithms.Swap(ref data, start, i);
perm.RemoveAt(perm.Count - 1);
}
}
}
#endregion
#region 分治
public static void DivideAndConquer()
{
}
#endregion
}
}
|
