С# Перестановка массива arraylists?

У меня есть 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

Означает ли это, чего я пытаюсь достичь? Я не могу придумать хороший способ сделать это (если есть).

Edit:
Я не уверен, что рекурсия будет мешать моему желанию форматировать вывод по-своему. Извините, я не упоминал до того, что мое форматирование было.

Я хочу создать массив строк [] из всех комбинаций, следующих за форматом, как показано ниже:

для перестановки "1 2 93"

Я хочу, чтобы выход был "val0 = 1; val1 = 2; val2 = 93;"

Сейчас я буду экспериментировать с рекурсией. Спасибо DrJokepu

Ответы

Ответ 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)

Ответ 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), который возвращает список, содержащий один элемент, пустую строку. Перестановка списка из n строковых массивов s1, s2,..., sN равна каждому члену sA1, предваряемому перестановке массивов строк n-1, s2,..., sN. В базовом случае есть что-то для каждого элемента sN, который должен быть конкатенирован.

Ответ 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);
    }
}

Ответ 4

Вы можете использовать factoradics для генерации перечисления перестановок. Попробуйте эту статью в MSDN для реализации на С#.

Ответ 5

Это будет работать независимо от того, сколько массивов вы добавляете в свой myList:

        static void Main(string[] args)
        {
            string[][] myList = new string[3][];
            myList[0] = new string[] { "1", "5", "3", "9" };
            myList[1] = new string[] { "2", "3" };
            myList[2] = new string[] { "93" };

            List<string> permutations = new List<string>(myList[0]);

            for (int i = 1; i < myList.Length; ++i)
            {
                permutations = RecursiveAppend(permutations, myList[i]);
            }

            //at this point the permutations variable contains all permutations

        }

        static List<string> RecursiveAppend(List<string> priorPermutations, string[] additions)
        {
            List<string> newPermutationsResult = new List<string>();
            foreach (string priorPermutation in priorPermutations)
            {
                foreach (string addition in additions)
                {
                    newPermutationsResult.Add(priorPermutation + ":" + addition);
                }
            }
            return newPermutationsResult;
        }

Обратите внимание, что это не очень рекурсивно. Вероятно, вводящее в заблуждение имя функции.

Вот версия, которая соответствует вашим новым требованиям. Обратите внимание на раздел, в котором я выводю на консоль, здесь вы можете сделать свое собственное форматирование:

static void Main(string[] args)
        {
            string[][] myList = new string[3][];
            myList[0] = new string[] { "1", "5", "3", "9" };
            myList[1] = new string[] { "2", "3" };
            myList[2] = new string[] { "93" };

            List<List<string>> permutations = new List<List<string>>();

            foreach (string init in myList[0])
            {
                List<string> temp = new List<string>();
                temp.Add(init);
                permutations.Add(temp);
            }

            for (int i = 1; i < myList.Length; ++i)
            {
                permutations = RecursiveAppend(permutations, myList[i]);
            }

            //at this point the permutations variable contains all permutations

            foreach (List<string> list in permutations)
            {
                foreach (string item in list)
                {
                    Console.Write(item + ":");
                }
                Console.WriteLine();
            }

        }

        static List<List<string>> RecursiveAppend(List<List<string>> priorPermutations, string[] additions)
        {
            List<List<string>> newPermutationsResult = new List<List<string>>();
            foreach (List<string> priorPermutation in priorPermutations)
            {
                foreach (string addition in additions)
                {
                    List<string> priorWithAddition = new List<string>(priorPermutation);
                    priorWithAddition.Add(addition);
                    newPermutationsResult.Add(priorWithAddition);
                }
            }
            return newPermutationsResult;
        }

Ответ 6

То, о чем вы просите, называется декартовым произведением. Как только вы узнаете, как его зовут, есть несколько похожих вопросов по переполнению стека. Все они, кажется, в конечном итоге указывают на ответ, который в конечном итоге был написан как сообщение в блоге:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

Ответ 7

Нерекурсивное решение:

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;
}

Ответ 8

Вот общая рекурсивная функция, которую я написал (и перегрузка, которая может быть удобна для вызова):

Public Shared Function GetCombinationsFromIEnumerables(ByRef chain() As Object, ByRef IEnumerables As IEnumerable(Of IEnumerable(Of Object))) As List(Of Object())
    Dim Combinations As New List(Of Object())
    If IEnumerables.Any Then
        For Each v In IEnumerables.First
            Combinations.AddRange(GetCombinationsFromIEnumerables(chain.Concat(New Object() {v}).ToArray, IEnumerables.Skip(1)).ToArray)
        Next
    Else
        Combinations.Add(chain)
    End If
    Return Combinations
End Function

Public Shared Function GetCombinationsFromIEnumerables(ByVal ParamArray IEnumerables() As IEnumerable(Of Object)) As List(Of Object())
    Return GetCombinationsFromIEnumerables(chain:=New Object() {}, IEnumerables:=IEnumerables.AsEnumerable)
End Function

И эквивалент в С#:

public static List<object[]> GetCombinationsFromIEnumerables(ref object[] chain, ref IEnumerable<IEnumerable<object>> IEnumerables)
{
List<object[]> Combinations = new List<object[]>();
if (IEnumerables.Any) {
    foreach ( v in IEnumerables.First) {
        Combinations.AddRange(GetCombinationsFromIEnumerables(chain.Concat(new object[] { v }).ToArray, IEnumerables.Skip(1)).ToArray);
    }
} else {
    Combinations.Add(chain);
}
return Combinations;
}

public static List<object[]> GetCombinationsFromIEnumerables(params IEnumerable<object>[] IEnumerables)
{
return GetCombinationsFromIEnumerables(chain = new object[], IEnumerables = IEnumerables.AsEnumerable);
}

Прост в использовании:

Dim list1 = New String() {"hello", "bonjour", "hallo", "hola"}
Dim list2 = New String() {"Erwin", "Larry", "Bill"}
Dim list3 = New String() {"!", ".."}
Dim result = MyLib.GetCombinationsFromIEnumerables(list1, list2, list3)
For Each r In result
    Debug.Print(String.Join(" "c, r))
Next

или в С#:

object list1 = new string[] {"hello","bonjour","hallo","hola"};
object list2 = new string[] {"Erwin", "Larry", "Bill"};
object list3 = new string[] {"!",".."};
object result = MyLib.GetCombinationsFromIEnumerables(list1, list2, list3);
foreach (r in result) {
Debug.Print(string.Join(' ', r));
}

Ответ 9

Вот версия, которая использует очень маленький код и является полностью декларативной

    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> collection) where T : IComparable
    {
        if (!collection.Any())
        {
            return new List<IEnumerable<T>>() {Enumerable.Empty<T>() };
        }
        var sequence = collection.OrderBy(s => s).ToArray();
        return sequence.SelectMany(s => GetPermutations(sequence.Where(s2 => !s2.Equals(s))).Select(sq => (new T[] {s}).Concat(sq)));
    }

Ответ 10

class Program
{
    static void Main(string[] args)
    {
        var listofInts = new List<List<int>>(3);
        listofInts.Add(new List<int>{1, 2, 3});
        listofInts.Add(new List<int> { 4,5,6 });
        listofInts.Add(new List<int> { 7,8,9,10 });

        var temp = CrossJoinLists(listofInts);
        foreach (var l in temp)
        {
            foreach (var i in l)
                Console.Write(i + ",");
            Console.WriteLine();
        }
    }

    private static IEnumerable<List<T>> CrossJoinLists<T>(IEnumerable<List<T>> listofObjects)
    {
        var result = from obj in listofObjects.First()
                     select new List<T> {obj};

        for (var i = 1; i < listofObjects.Count(); i++)
        {
            var iLocal = i;
            result = from obj  in result
                     from obj2 in listofObjects.ElementAt(iLocal)
                     select new List<T>(obj){ obj2 };
        }

        return result;
    }
}

Ответ 11

Здесь нерекурсивное, не Linq решение. Я не могу не чувствовать, что у меня может быть меньше циклов и вычислять позиции с разделением и по модулю, но я не могу полностью обвести вокруг себя.

static void Main(string[] args)
    {
        //build test list
        List<string[]> myList = new List<string[]>();
        myList.Add(new string[0]);
        myList.Add(new string[0]);
        myList.Add(new string[0]);
        myList[0] = new string[] { "1", "2", "3"};
        myList[1] = new string[] { "4", "5" };
        myList[2] = new string[] { "7", "8", "9" };

        object[][] xProds = GetProducts(myList.ToArray());
        foreach(object[] os in xProds)
        {
            foreach(object o in os)
            {
                Console.Write(o.ToString() + " ");
            }
            Console.WriteLine();
        }
        Console.ReadKey();
    }

    static object[][] GetProducts(object[][] jaggedArray){
        int numLists = jaggedArray.Length;
        int nProducts = 1;
        foreach (object[] oArray in jaggedArray)
        {
            nProducts *= oArray.Length;
        }
        object[][] productAry = new object[nProducts][];//holds the results
        int[] listIdxArray = new int[numLists];
        listIdxArray.Initialize();
        int listPtr = 0;//point to current list

        for(int rowcounter = 0; rowcounter < nProducts; rowcounter++)
        {
            //create a result row
            object[] prodRow = new object[numLists];
            //get values for each column
            for(int i=0;i<numLists;i++)
            {
                prodRow[i] = jaggedArray[i][listIdxArray[i]];
            }
            productAry[rowcounter] = prodRow;
            //move the list pointer
            //possible states
            // 1) in a list, has room to move down
            // 2) at bottom of list, can move to next list
            // 3) at bottom of list, no more lists left
            //in a list, can move down
            if (listIdxArray[listPtr] < (jaggedArray[listPtr].Length - 1))
            {
                listIdxArray[listPtr]++;
            }
            else
            {
                //can move to next column?
                //move the pointer over until we find a list, or run out of room
                while (listPtr < numLists && listIdxArray[listPtr] >= (jaggedArray[listPtr].Length - 1))
                {
                    listPtr++;
                }
                if (listPtr < listIdxArray.Length && listIdxArray[listPtr] < (jaggedArray[listPtr].Length - 1))
                {
                    //zero out the previous stuff
                    for (int k = 0; k < listPtr; k++)
                    {
                        listIdxArray[k] = 0;
                    }
                    listIdxArray[listPtr]++;
                    listPtr = 0;
                }
            }
        }
        return productAry;
    }

Ответ 12

Одна из проблем, с которыми я столкнулась, когда делала это для очень большого количества кодов, заключалась в том, что с примером, которым был предоставлен Брайан, у меня на самом деле закончилась нехватка памяти. Чтобы решить эту проблему, я использовал следующий код.

static void foo(string s, List<Array> x, int a)
    {
        if (a == x.Count)
        {
            // output here
            Console.WriteLine(s);
        }
        else
        {
            foreach (object y in x[a])
            {
                foo(s + y.ToString(), x, a + 1);
            }
        }
    }

static void Main(string[] args)
    {
        List<Array> a = new List<Array>();
        a.Add(new string[0]);
        a.Add(new string[0]);
        a.Add(new string[0]);
        a[0] = new string[] { "T", "Z" };
        a[1] = new string[] { "N", "Z" };
        a[2] = new string[] { "3", "2", "Z" };

        foo("", a, 0);
        Console.Read();
    }

Ответ 13

private static void GetP(List<List<string>> conditions, List<List<string>> combinations, List<string> conditionCombo, List<string> previousT, int selectCnt)
{
    for (int i = 0; i < conditions.Count(); i++)
    {
        List<string> oneField = conditions[i];
        for (int k = 0; k < oneField.Count(); k++)
        {
            List<string> t = new List<string>(conditionCombo);
            t.AddRange(previousT);
            t.Add(oneField[k]);

            if (selectCnt == t.Count )
            {
                combinations.Add(t);
                continue;
            }
            GetP(conditions.GetRange(i + 1, conditions.Count - 1 - i), combinations, conditionCombo, t, selectCnt);
        }

    }
}

List<List<string>> a = new List<List<string>>();
a.Add(new List<string> { "1", "5", "3", "9" });
a.Add(new List<string> { "2", "3" });
a.Add(new List<string> { "93" });
List<List<string>> result = new List<List<string>>();
GetP(a, result, new List<string>(), new List<string>(), a.Count);

Еще одна рекурсивная функция.