组合创建者
本文关键字：创建者 组合 | 更新日期: 2023-09-27 17:59:20
我想向一个方法发送一个数字列表，并通过将数字放在一起来返回我从该列表生成的所有可能的数字组合。
例如，对于{1, 2, 3}的数字，我会给予回报：
{1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321}
例如，这段代码（我还没有完成）只"知道"处理包含3个数字的列表。
private static void M1()
{
var intList = new List<int>() { 1, 2, 3 };
var resultList = AllPossibleCombinations(intList);
}
private static object AllPossibleCombinations(List<int> List)
{
var result = new List<int>();
result.Add(List[0]);
result.Add(List[1]);
result.Add(List[2]);
result.Add(List[0] * 10 + List[1]);
result.Add(List[1] * 10 + List[2]);
result.Add(List[0] * 10 + List[2]);
result.Add(List[1] * 10 + List[0]);
result.Add(List[2] * 10 + List[1]);
result.Add(List[2] * 10 + List[0]);
return result;
}
我怎样才能写出更通用的东西？我如何获得一个包含不同元素数量的列表，并给出所有可能的组合？
这不一定是最有效的，但以下是如何使用返回IEnumerable<T>的非递归方法来实现这一点。这样的事情可能需要最少的内存，因为它不需要构建内存中的所有排列。相反，它只允许您一个接一个地迭代排列。
private static void Main()
{
var input1 = new[] {"1", "2", "3"};
foreach (var output in EnumeratePermutations(input1))
Debug.WriteLine(String.Join(",", output));
}
private static IEnumerable<T[]> EnumeratePermutations<T>(T[] input)
{
return from partCount in Enumerable.Range(1, input.Length)
let inputs = Enumerable.Repeat(input, partCount).ToArray()
from indices in EnumerateCrossjoinIndices(inputs)
where indices.Distinct().Count() == indices.Length
select indices.Select(n => input[n]).ToArray();
}
private static IEnumerable<int[]> EnumerateCrossjoinIndices(params Array[] arrays)
{
var arrayCount = arrays.Length;
if (arrayCount == 0)
yield break;
if (arrays.Any(a => a.Length == 0))
yield break;
var indexer = new int[arrayCount];
yield return (int[]) indexer.Clone();
for (var dimension = arrayCount - 1; dimension >= 0; --dimension)
{
++indexer[dimension];
if (indexer[dimension] == arrays[dimension].Length)
indexer[dimension] = 0;
else
{
yield return (int[]) indexer.Clone();
dimension = arrayCount;
}
}
}
EnumerateCrossjoinIndices采用长度可能不同的n数组，并生成交叉联接操作中使用的索引的枚举。例如，给定{"1","2"}和{"A","B","C"}，它将产生6个阵列{0,0}、{0,1}、{0,2}、{1,0}、{1,1}、{1,2}。请注意，此方法生成的数组包含输入数组中的索引，而不是这些索引处的元素。
CCD_ 12取一个数组并产生该数组的项的排列。它通过枚举将用于根据自身交叉连接数组的索引x次来实现这一点（其中x=1到n，其中n是数组中的项数）。然后，它过滤掉任何一组交叉连接索引，这些索引不是一个不同的集合。
试试这个示例代码：
private static List<int> AllPossibleCombinations(IList<int> alphabet)
{
List<int[]> combinations = new List<int[]>();
MakeCombination(combinations, alphabet.Count, new int[0]); // Start recursion
combinations.RemoveAt(0); // Remove empty combination
return combinations.ConvertAll(c => c.Aggregate(0, (sum, index) => sum * 10 + alphabet[index]));
}
private static void MakeCombination(List<int[]> output, int length, int[] usedIndices)
{
output.Add(usedIndices);
for (int i = 0; i < length; i++)
if (Array.IndexOf(usedIndices, i) == -1) // If the index wasn't used earlier
{
// Add element to the array of indices by creating a new one:
int[] indices = new int[usedIndices.Length + 1];
usedIndices.CopyTo(indices, 0);
indices[usedIndices.Length] = i;
if (length + 1 != indices.Length)
MakeCombination(output, length, indices); // Recursion
}
}
它使用递归生成所需的组合。
用法：
var t = AllPossibleCombinations(new[] { 1, 2, 3 });
解决方案1
更通用且与类型无关的方法是创建基于树的算法，该算法返回输入对象组合的集合。
代码：
public static class IEnumerableExtensions
{
private class Node<T>
{
public Node()
{
Children = new List<Node<T>>();
}
public T Value
{
get;
set;
}
public bool IsRoot
{
get;
set;
}
public List<Node<T>> Children
{
get;
private set;
}
public Node<T> Parent
{
get;
set;
}
public List<Node<T>> Path
{
get
{
List<Node<T>> Result = new List<Node<T>>();
Result.Add(this);
if (this.Parent.IsRoot == false)
{
Result.AddRange(this.Parent.Path);
}
return Result;
}
}
}
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> enumerable)
{
List<Node<T>> AllNodes = new List<Node<T>>();
// Create tree.
Node<T> Root = new Node<T>() { IsRoot = true };
Queue<Node<T>> Queue = new Queue<Node<T>>();
Queue.Enqueue(Root);
int CurrentLevel = 0;
int LevelsToCreate = enumerable.Count();
while (Queue.Count > 0)
{
var CurrentLevelNodes = Queue.ToList();
Queue.Clear();
foreach (var LoopNode in CurrentLevelNodes)
{
if (LoopNode.Children.Count == 0)
{
foreach (var LoopValue in enumerable)
{
var NewNode = new Node<T>() { Value = LoopValue, Parent = LoopNode };
AllNodes.Add(NewNode);
LoopNode.Children.Add(NewNode);
Queue.Enqueue(NewNode);
}
}
}
CurrentLevel++;
if (CurrentLevel >= LevelsToCreate)
{
break;
}
}
// Return list of all paths (which are combinations).
List<List<T>> Result = new List<List<T>>();
foreach (var LoopNode in AllNodes)
{
if (!LoopNode.IsRoot)
{
List<T> Combination = LoopNode.Path.Select(Item => Item.Value).ToList();
Result.Add(Combination);
}
}
return Result;
}
}
数字示例：
class Program
{
static void Main(string[] args)
{
List<int> Input = new List<int>() { 1, 2, 3 };
var Combinations = Input.Combinations();
}
}
字符串示例：
static void Main(string[] args)
{
var Input = new List<string>() { "a", "b" };
var Combinations = Input.Combinations();
foreach (var LoopCombination in Combinations)
{
string Combination = string.Join(String.Empty, LoopCombination);
Console.WriteLine(Combination);
}
Console.ReadKey();
}
解决方案2
第二个想法是不要使用基于树的算法，而是循序渐进地创建组合——这可能会更快。
代码：
public class Combinator<T>
{
private readonly Dictionary<int, T> _Pattern;
private readonly int _Min = 0;
private readonly int _Max;
private List<int> _CurrentCombination;
public Combinator(IEnumerable<T> pattern)
{
_Pattern = new Dictionary<int, T>();
for (int i = 0; i < pattern.Count(); i++)
{
_Pattern.Add(i, pattern.ElementAt(i));
}
_CurrentCombination = new List<int>();
_Max = pattern.Count() - 1;
}
public bool HasFinised
{
get;
private set;
}
public IEnumerable<T> Next()
{
// Initialize or increase.
if (_CurrentCombination.Count == 0)
{
_CurrentCombination.Add(_Min);
}
else
{
MyIncrease(_CurrentCombination.Count - 1);
}
if (_CurrentCombination.Count - 1 == _Max && _CurrentCombination.All(Key => Key == _Max))
{
HasFinised = true;
}
return _CurrentCombination.Select(Key => _Pattern[Key]).ToList();;
}
private void MyIncrease(int index)
{
if (index >= 0)
{
_CurrentCombination[index] = _CurrentCombination[index] + 1;
if (_CurrentCombination[index] > _Max)
{
_CurrentCombination[index] = _Min;
if (index - 1 < 0)
{
_CurrentCombination.Insert(0, -1);
index++;
}
MyIncrease(index - 1);
}
}
}
}
示例：
class Program
{
static void Main(string[] args)
{
var Pattern = new List<string>() { "a", "b", "c" };
Combinator<string> Combinator = new Combinator<string>(Pattern);
while (Combinator.HasFinised == false)
{
var Combined = Combinator.Next();
var Joined = string.Join("-", Combined);
Console.WriteLine(Joined);
}
Console.ReadKey();
}
}
如果您只想将项目与其他项目组合：
static void Main(string[] args)
{
Combinator<int> Combinator = new Combinator<int>(new List<int>() { 1, 2, 3 });
while (Combinator.HasFinised == false)
{
var NextCombination = Combinator.Next();
var DistinctCheck = NextCombination.ToList().Distinct();
if (DistinctCheck.Count() == NextCombination.Count())
{
Console.WriteLine(string.Join(String.Empty, NextCombination.Select(Item => Item.ToString())));
}
}
Console.ReadKey();
}