c# - 在 C# 中生成 List>> 子集的排列

Question

请看下面的示例代码:

List<List<KeyValuePair<string, string>>> list = new List<List<KeyValuePair<string, string>>>();

list.Add(new List<KeyValuePair<string, string>>());
list[0].Add(new KeyValuePair<string, string>("Category 1", "Value A"));
list[0].Add(new KeyValuePair<string, string>("Category 1", "Value B"));

list.Add(new List<KeyValuePair<string, string>>());
list[1].Add(new KeyValuePair<string, string>("Category 2", "Value C"));
list[1].Add(new KeyValuePair<string, string>("Category 2", "Value D"));

list.Add(new List<KeyValuePair<string, string>>());
list[2].Add(new KeyValuePair<string, string>("Category 3", "Value E"));

也可以这样表示:

+---------------------------+---------------------------+
| ["Category 1", "Value A"] | ["Category 1", "Value B"] |
+---------------------------+---------------------------+
| ["Category 2", "Value C"] | ["Category 2", "Value D"] |
+---------------------------+---------------------------+
| ["Category 3", "Value E"] |                           |
+---------------------------+---------------------------+

我需要重新排列这些值，使每一列都包含一个唯一的类别，我必须 copy-and-swap 值，以便在给定类别限制的情况下实现所有可能的值排列。换句话说……

+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value A"] | ["Category 2", "Value C"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value B"] | ["Category 2", "Value D"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value B"] | ["Category 2", "Value C"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value A"] | ["Category 2", "Value D"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+

请注意，我已经交换了第一列中的第三个和第四个值以获得唯一的行。在考虑我的问题时请忽略使用哪一列，只要我最终在这个特定的列/类别顺序中得到唯一的行，交换哪些值并不重要。另外，正如我之前所说，这只是一个示例，我需要一些无论元素数量如何都能正常工作的东西。

这是我目前所拥有的(这里的变量列表与上面相同):

int elementAmount = list.Count;
int combinationAmount = list.Select(x => x.Count).Aggregate(1, (x, y) => x * y); //Multiply sublists element count

List<List<KeyValuePair<string, string>>> sortedList = new List<List<KeyValuePair<string, string>>>(combinationAmount);

for (int i = 0; i < combinationAmount; i++)
sortedList.Add(new List<KeyValuePair<string, string>>(elementAmount));

for (int j = 0; j < elementAmount; j++)
{
    for (int i = 0; i < combinationAmount; i++)
        sortedList[i].Add(list[j].Count > i ? list[j][i] : sortedList[i - list[j].Count][j]);
}

输出:

+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value A"] | ["Category 2", "Value C"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value B"] | ["Category 2", "Value D"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value A"] | ["Category 2", "Value C"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+
| ["Category 1", "Value B"] | ["Category 2", "Value D"] | ["Category 3", "Value E"] |
+---------------------------+---------------------------+---------------------------+

如果我提出了一个误导性的标题，我深表歉意，很难用一行来概括整个问题。请根据您的心意对其进行编辑。

编辑:我只是缺少交换。

Answer 1

首先是问题的答案。请注意，在那之后我将发布一些没有被数据结构混淆的东西，这些数据结构只是通过递归显示排列。

    private void button1_Click(object sender, EventArgs e)
    {
        List<List<KeyValuePair<string, string>>> list = new List<List<KeyValuePair<string, string>>>();

        list.Add(new List<KeyValuePair<string, string>>());
        list[0].Add(new KeyValuePair<string, string>("Category 1", "Value A"));
        list[0].Add(new KeyValuePair<string, string>("Category 1", "Value B"));

        list.Add(new List<KeyValuePair<string, string>>());
        list[1].Add(new KeyValuePair<string, string>("Category 2", "Value C"));
        list[1].Add(new KeyValuePair<string, string>("Category 2", "Value D"));

        list.Add(new List<KeyValuePair<string, string>>());
        list[2].Add(new KeyValuePair<string, string>("Category 3", "Value E"));

        List<List<KeyValuePair<string, string>>> sortedList = new List<List<KeyValuePair<string, string>>>();

        permutation(list, 0, new List<KeyValuePair<string, string>>());
    }


    private void permutation( List<List<KeyValuePair<string, string>>> options, int srcPos, List<KeyValuePair<string, string>> result)
    {
        if (result.Count == options.Count)
            WriteOne(result);
        else
        {
            foreach (KeyValuePair<string, string> opt in options[srcPos])
            {
                List<KeyValuePair<string, string>> theClone = new List<KeyValuePair<string, string>>(result); 
                theClone.Add(opt); 
                permutation(options, srcPos + 1, theClone);
            }
        }
    }

    private void WriteOne(List<KeyValuePair<string, string>> OneResult)
    {
        StringBuilder line = new StringBuilder(80);
        StringBuilder line2 = new StringBuilder(80);
        line.Append("|"); line2.Append("+");
        foreach (KeyValuePair<string, string> item in OneResult)
        {
            line.Append(" [");       line2.Append("--");
            line.Append(item.Key);   line2.Append(new string('-', item.Key.Length));
            line.Append(", ");       line2.Append("--");
            line.Append(item.Value); line2.Append(new string('-', item.Value.Length));
            line.Append("] |");     line2.Append("--+");
        }
        line.AppendLine(); line2.AppendLine();
        Console.WriteLine(line.ToString());
        Console.WriteLine(line2.ToString());
    }

现在更简单的事情是产生上面那个的东西。它是完全相同的算法，但通用列表符号不会混淆它。

    private void Test()
    {
        permutation(new string[] { "AB", "CD", "E" }, 0, "");
    }


    private void permutation(string[] options, int srcPos, string result)
    {
        if (result.Length == options.Length)
            Console.WriteLine(result);
        else
        {
            foreach (char opt in options[srcPos])
            {
                permutation(options, srcPos + 1, result + opt);
            }
        }
    }