C#排列一系列的arraylists？

Question

我有一个ArrayList [] myList,我正在尝试创建一个列表,列出数组中值的所有排列.

示例:(所有值均为字符串)

myList[0] = { "1", "5", "3", "9" };
myList[1] = { "2", "3" };
myList[2] = { "93" };

myList的计数可以变化,因此事先不知道它的长度.

我希望能够生成一个类似于以下所有排列的列表(但有一些额外的格式).

1 2 93
1 3 93
5 2 93
5 3 93
3 2 93
3 3 93
9 2 93
9 3 93

这是否理解我想要完成的事情？我似乎无法想出这样做的好方法,(如果有的话).

编辑:
我不确定递归是否会干扰我以自己的方式格式化输出的愿望.对不起我之前没有提到我的格式.

我想最终构建一个string []数组,其中包含如下格式的所有组合:

对于"1 2 93"排列

我希望输出为"val0 = 1; val1 = 2; val2 = 93;"

我现在将尝试递归.谢谢Dr.Jokepu

Answer 1

我很惊讶没有发布LINQ解决方案.

from val0 in new []{ "1", "5", "3", "9" }
from val1 in new []{ "2", "3" }
from val2 in new []{ "93" }
select String.Format("val0={0};val1={1};val2={2}", val0, val1, val2)

Answer 2

递归解决方案

    static List<string> foo(int a, List<Array> x)
    {
        List<string> retval= new List<string>();
        if (a == x.Count)
        {
            retval.Add("");
            return retval;
        }
        foreach (Object y in x[a])
        {
            foreach (string x2 in foo(a + 1, x))
            {
                retval.Add(y.ToString() + " " + x2.ToString());
            }

        }
        return retval;
    }
    static void Main(string[] args)
    {
        List<Array> myList = new List<Array>();
        myList.Add(new string[0]);
        myList.Add(new string[0]);
        myList.Add(new string[0]);
        myList[0] = new string[]{ "1", "5", "3", "9" };
        myList[1] = new string[] { "2", "3" };
        myList[2] = new string[] { "93" };
        foreach (string x in foo(0, myList))
        {
            Console.WriteLine(x);
        }

        Console.ReadKey();
    }

请注意,通过将返回更改为字符串列表列表并更改retval.add调用以使用列表而不是使用连接,返回列表或数组而不是字符串将非常容易.

这个怎么运作:

这是一种经典的递归算法.基本情况是foo(myList.Count, myList),它返回一个包含一个元素的List,即空字符串.n个字符串数组s1,s2,...,sN的列表的排列等于sA1的每个成员,其前缀为n-1个字符串数组的排列,s2,...,sN.基本情况就是为sN的每个元素提供连接的东西.

Answer 3

我最近在我的一个项目中遇到了类似的问题,偶然发现了这个问题.我需要一个可以处理任意对象列表的非递归解决方案.这就是我想出来的.基本上我正在为每个子列表形成一个枚举器列表,并迭代地递增它们.

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<IEnumerable<T>> lists)
{
    // Check against an empty list.
    if (!lists.Any())
    {
        yield break;
    }

    // Create a list of iterators into each of the sub-lists.
    List<IEnumerator<T>> iterators = new List<IEnumerator<T>>();
    foreach (var list in lists)
    {
        var it = list.GetEnumerator();
        // Ensure empty sub-lists are excluded.
        if (!it.MoveNext())
        {
            continue;
        }
        iterators.Add(it);
    }

    bool done = false;
    while (!done)
    {
        // Return the current state of all the iterator, this permutation.
        yield return from it in iterators select it.Current;

        // Move to the next permutation.
        bool recurse = false;
        var mainIt = iterators.GetEnumerator();
        mainIt.MoveNext(); // Move to the first, succeeds; the main list is not empty.
        do
        {
            recurse = false;
            var subIt = mainIt.Current;
            if (!subIt.MoveNext())
            {
                subIt.Reset(); // Note the sub-list must be a reset-able IEnumerable!
                subIt.MoveNext(); // Move to the first, succeeds; each sub-list is not empty.

                if (!mainIt.MoveNext())
                {
                    done = true;
                }
                else
                {
                    recurse = true;
                }
            }
        }
        while (recurse);
    }
}

Answer 4

非递归解：

foreach (String s1 in array1) {
    foreach (String s2 in array2) {
        foreach (String s3 in array3) {
            String result = s1 + " " + s2 + " " + s3;
            //do something with the result
        }
    }
}

递归解法：

private ArrayList<String> permute(ArrayList<ArrayList<String>> ar, int startIndex) {
    if (ar.Count == 1) {
        foreach(String s in ar.Value(0)) {
            ar.Value(0) = "val" + startIndex + "=" + ar.Value(0);
        return ar.Value(0);
    }
    ArrayList<String> ret = new ArrayList<String>();
    ArrayList<String> tmp1 ar.Value(0);
    ar.remove(0);
    ArrayList<String> tmp2 = permute(ar, startIndex+1);
    foreach (String s in tmp1) {
        foreach (String s2 in tmp2) {
            ret.Add("val" + startIndex + "=" + s + " " + s2);
        }
    }
    return ret;
}