C # Permutation d'un tableau d'arraylists?

Je suis surpris que personne n'a posté le LINQ solution.

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)

Je suis récemment tombé sur un problème similaire dans un projet de mine et je suis tombé sur cette question. J'avais besoin d'une non-solution récursive qui pourraient travailler avec des listes d'objets arbitraires. Voici ce que j'ai trouvé. Fondamentalement, je suis à la formation d'une liste d'agents recenseurs pour chacune des sous-listes et l'incrémentation eux de manière itérative.

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

Cela fonctionne, peu importe le nombre de tableaux que vous ajoutez à votre maliste:

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

Noter que ce n'est pas vraiment récursive. Probablement trompeuse nom de la fonction.

Ici est une version qui adhère à vos nouvelles exigences. Remarque la section où je l'ai sortie de la console, c'est où vous pouvez faire votre propre mise en forme:

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

Non-solution récursive:

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

Solution récursive:

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

Ici est une version qui utilise très peu de code, et est entièrement déclarative

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

Voici un non-récursive, non-Linq solution. Je peux pas m'empêcher de penser que je pourrais avoir moins de bouclage et de calculer les positions avec la division et le modulo, mais pas tout à envelopper ma tête autour de cela.

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