形成多维笛卡尔乘积数组

Question

我有一个函数，它为我的生成笛卡尔乘积

var abcArray = new string[] { "a", "b", "c" };
var xyzArray = new string[] { "1", "2", "3" };
var combos = CartesianProductSmart(abcArray, xyzArray);
private static string[][] CartesianProductSmart(string[] arr1, string[] arr2)
{
return arr1.SelectMany(s1 => arr2, (s1, s2) => new string[] { s1, s2 })
.ToArray();
}

我的输出看起来像：

a,1
a,2
a,3
b,1
b,2
b,3
c,1
c,2
c,3

如何将此函数转换为更复杂的函数，例如形成多维数组：

array3 = [ {"A1", "B2", "C3"},
{"A1", "B3", "C2"},
{"A2", "B1", "C3"},
{"A2", "B3", "C1"}, 
{"A3", "B2", "C1"},
{"A3", "B1", "C2"}
]

我想要的是笛卡尔乘积，只使用两个数组的每个元素，并将其形成一个数组。(我知道数组的大小会因输入的不同而不同(。到目前为止，我的想法是做笛卡尔乘积，将第一个元素分配为第一个笛卡尔乘积结果，然后迭代其余的笛卡尔乘积，并通过检查是否没有重复，然后只选择唯一的成员来添加到新的数组中，但这似乎效率很低。

Answer 1

我的建议是，如果你使用复杂的结构，你不应该再使用标准结构，而是创建代表你建模的数据和你可以对这些对象执行的操作的类。

显然，你的程序有Matrix的概念(不确定你在英语数学中是否使用了相同的术语(

M乘N的矩阵有M列和N行。

我不确定把abcarray放在3乘1的矩阵中是否明智，或者你想把它放在一个特殊的类中，你会称之为Vector。也许向量是N乘1的矩阵的派生类？还是1乘N？

无论如何，显然你可以对两个矢量进行操作：

class Vector
{
public Matrix<T> CartesianProduct(Vector<T> v)
{
return CartesianProduct(this, v);
}
public static Matrix<T> CartesianProduct(Vector<T> x, Vector<T> y) {...}

用途为：

Vector<string> x = new Vector<string>(new string[] { "a", "b", "c" });
Vector<string> y = new Vector<string>(new string[] { "1", "2", "3" });
Matrix<string> m = x.CartesianProduct(y);

这对我来说已经足够整洁了，所以让我们继续走这条路。

Vector有一个Dimension。创建Vector对象时，必须指定Dimension。在Vector的生命周期内，您不能更改其Dimension。

矢量具有Coordinates，编号从0到Dimension-1。您可以获取并设置特定的坐标。为了简单起见，我们使用索引来访问坐标。

可以对矢量执行的操作：加/减/反/乘/。。。这有点超出了你的问题范围，所以我就不谈了。

class Vector<T> : IReadonlyCollection<T>
{
private readonly T[] coordinates;
public Vector(int dimension)
{
// TODO: check dimension > 0;
this.coordinates = new T[dimension];
}
public Vector(IEnumerable<T> data)
{
// TODO: check data != null; check data contains at least one element
this.Coordinates = data.ToArray();
}
// TODO: other constructors? ICloneable?
// TODO: Add / Subtract / Multiply with a number?
public T this[int index] 
{
get => this.coordinates[index];
set => this.coordinates[index] = value;
}
}

IReadOnlyCollection的实现相当简单：

public int Count => this.coordinates.Length;
public Enumerator<T> GetEnumerator()
{
return this.Coordinates.GetEnumerator();
}
IEnumerator Enumerable.GetEnumerator()
{
return this.GetEnumerator();
}

对于初始化，下面的扩展方法会很好。如果您不熟悉扩展方法，请阅读解密的扩展方法

public static Vector<T> AsVector<T>(IEnumerable<T> source)
{
return new Vector<T>(source.ToArray());
}

用法：

var abcArray = new string[] { "a", "b", "c" };
var abcVector = abcArray.AsVector();

我把矩阵设计成一个不可变的二维数组。

class Matrix<T>
{
private readonly T[,] elements;
public Matrix(int columnCount, int rowCount)
{
this.elements = new T[columnCount, rowCount];
}
public Matrix(T[,] elements)
{
this.elements = elements;
}
public int RolumnCount => this.elements.GetLength[0];
public int RowCount => this.elements.GetLength[1];
// etc, invent several other useful operations on matrices.
// addition, multiplication, linear transformation, ...
}

当然，如果你真的想把矩阵解释为二维数组：

public T[,] Elements => this.elements

最后是两个向量的笛卡尔乘积，返回一个矩阵。问题是，我们需要一个函数来"；"组合"；一个x坐标与一个"x"坐标；y"；坐标对于一个数字向量，这可能是一个乘法，对于一个字符串向量，你想使用串联。

public static Matrix<T> CartesianProduct(Vector<T> vectorX, Vector<T> vectorY, 
Func<T, T, T> combine)
{
// TODO: input not null; correct dimension
IEnumerable<T> combinations = vectorX.SelectMany(vectorY,
(xCoordinate, yCoordinate) => combine(xCoordinate, yCoordinate);
return new Matrix<T>(combinations);
}
Vector<string> abcArray = new Vector<string>(new string[] { "a", "b", "c" });
Vector<string> xyzArray = new Vector<string>(new string[] { "1", "2", "3" });
Matrix<string> m = Vector.CartesianProduct(abcArray, xyzArray, (x, y) => x + y);

Answer 2

使用扩展方法根据数组中的交换使用Heap算法生成排列(根据这个Stackoverflow答案(，您可以计算["1"、"2"、"3"]数组的排列，并使用LINQ将它们与["a"、"b"、"c"]数组合并。

这是排列的扩展方法：

public static class IEnumerableExt {
/// <summary>
/// From StackOverflow answer https://stackoverflow.com/a/36634935/2557128
/// EO: 2016-04-14
/// Generator of all permutations of an array of anything.
/// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
/// Heap's algorithm to find all permutations. Non recursive, more efficient.
/// </summary>
/// <param name="items">Items to permute in each possible ways</param>
/// <param name="funcExecuteAndTellIfShouldStop"></param>
/// <returns>Return true if cancelled</returns>
public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> itemsSrc) {
T[] items;
if (itemsSrc is T[] arrayOfItems)
items = arrayOfItems;
else
items = itemsSrc.ToArray();
/// <summary>
/// Swap 2 elements of same type
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Swap(ref T a, ref T b) {
T temp = a;
a = b;
b = temp;
}
int countOfItem = items.Length;
yield return items;
if (countOfItem <= 1)
yield break;
var indexes = new int[countOfItem];
for (int i = 1; i < countOfItem;) {
if (indexes[i] < i) {
if ((i & 1) == 1) // test if i odd: if (i % 2 == 1)  ... more efficient ??? At least the same.
Swap(ref items[i], ref items[indexes[i]]);
else
Swap(ref items[i], ref items[0]);
yield return items;
indexes[i]++;
i = 1;
}
else
indexes[i++] = 0;
}
}
}

现在你可以：

var ans1 = xyzArray.Permutations().Select(p => abcArray.Zip(p, (x,a) => x+a));

如果你喜欢一个数组，你可以把它添加到LINQ:中

var ans2 = xyzArray.Permutations().Select(p => abcArray.Zip(p, (x,a) => x+a).ToArray()).ToArray();